FLINT3.7.0-dev
/
Algorithm

Multiplication by a fixed operand (Shoup)

Cost
One high product, two low products and one conditional subtraction per multiplication; one division per fixed operand.

When the same a and n are used for many products ab \bmod n, as in scaling a vector or applying a fixed twiddle factor in a number-theoretic transform, a quotient can be precomputed for a so that each product needs no division at all. The method was introduced in NTL by Shoup [Sho2021] and is analysed by Harvey [Har2014].

Throughout, B = 2^{\mathtt{FLINT\_BITS}} and the modulus satisfies n < B/2. This restriction is what makes the final correction a single comparison.

Multiplication#

The precomputed data for 0 \le a < n is \hat a = \lfloor aB/n \rfloor, which fits in a word because a < n. We write aB = \hat a n + \check a with 0 \le \check a < n.

Algorithm 1: Shoup multiplication

Input: a < n < B/2, \hat a = \lfloor aB/n \rfloor and any 0 \le b < B.

Output: ab \bmod n.

  1. p \gets \lfloor \hat a b / B \rfloor (the high word of \hat a b).
  2. c \gets (ab - pn) \bmod B (two low products).
  3. If c \ge n, set c \gets c - n. Return c.

Lemma 1. p = \lfloor ab/n \rfloor or p = \lfloor ab/n \rfloor - 1.

Proof. From aB = \hat a n + \check a we get \hat a b / B = ab/n - \check a b/(nB). Since 0 \le \check a < n and 0 \le b < B, the subtracted term lies in [0, 1), so ab/n - 1 < \hat a b / B \le ab/n. Taking floors gives the claim.

Theorem 2. Algorithm 1 returns ab \bmod n.

Proof. By Lemma 1, the exact value ab - pn equals either ab \bmod n or (ab \bmod n) + n. Both are less than 2n < B, so the computation modulo B in step 2 is exact, and the comparison in step 3 tells the two cases apart. If n were allowed to be as large as B, then c and c + n could not be distinguished after reduction modulo B.

Updating the precomputation#

To multiply by ab \bmod n repeatedly, for example when building a table of powers a, a^2, a^3, \ldots, we also need its precomputed quotient. n_mulmod_and_precomp_shoup computes it without a division. Now let also b < n and bB = \hat b n + \check b.

Algorithm 2: Product with its precomputed quotient

Input: a, b < n < B/2, \hat a, \check a and \hat b.

Output: c = ab \bmod n and \hat c = \lfloor cB/n \rfloor.

  1. Compute the two-word product \hat a b = p B + e.
  2. c \gets (ab - pn) \bmod B; if c \ge n, set c \gets c - n.
  3. q \gets \lfloor \hat b \check a / B \rfloor.
  4. h \gets (b \check a - qn) \bmod B; if h \ge n, set q \gets q + 1.
  5. Return c and \hat c = (e + q) \bmod B.

Theorem 3. Algorithm 2 is correct.

Proof. Steps 1 and 2 are Algorithm 1, so c = ab \bmod n. For the quotient,

\left\lfloor \frac{abB}{n} \right\rfloor = \left\lfloor \frac{(\hat a n + \check a) b}{n} \right\rfloor = \hat a b + \left\lfloor \frac{\check a b}{n} \right\rfloor.

Since c = ab - \lfloor ab/n \rfloor n, we have \lfloor cB/n \rfloor = \lfloor abB/n \rfloor - \lfloor ab/n \rfloor B, and so \lfloor cB/n \rfloor \equiv e + \lfloor \check a b/n \rfloor \pmod B. As c < n, the left side is less than B, so it equals the right side reduced modulo B.

It remains to see that steps 3 and 4 compute \lfloor \check a b / n \rfloor. This is Lemma 1 with the roles of a and b exchanged (valid because b < n): the value q of step 3 is the correct quotient or one less, and \check a b - qn < 2n detects which.

Use in FLINT#

The macro NMOD_CAN_USE_SHOUP(mod) tests the condition n < 2^{\mathtt{FLINT\_BITS} - 1} for an nmod_t. Besides the functions in ulong_extras, the method is used by:

On SIMD hardware the same multiply-by-a-constant pattern is usually handled in floating point instead (Modular arithmetic in floating point).

ulong n_mulmod_shoup(ulong a, ulong b, ulong a_precomp, ulong n)
void _nmod_vec_scalar_mul_nmod_shoup(nn_ptr res, nn_srcptr vec, slong len, ulong c, nmod_t mod)
void _nmod_vec_invert_shoup(nn_ptr res, nn_srcptr vec, ulong len, nmod_t mod)

Referenced from#

References#

Cite this page

The FLINT team, “Multiplication by a fixed operand (Shoup),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/arithmetic/shoup.html (generated 2026-10-20).