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 aa and nn are used for many products ab mod nab \bmod n, as in scaling a vector or applying a fixed twiddle factor in a number-theoretic transform, a quotient can be precomputed for aa 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=2FLINT_BITSB = 2^{\mathtt{FLINT\_BITS}} and the modulus satisfies n<B/2n < B/2. This restriction is what makes the final correction a single comparison.

Multiplication#

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

Algorithm 1: Shoup multiplication

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

Output: ab mod nab \bmod n.

  1. p←⌊a^b/B⌋p \gets \lfloor \hat a b / B \rfloor (the high word of a^b\hat a b).
  2. c←(ab−pn) mod Bc \gets (ab - pn) \bmod B (two low products).
  3. If c≥nc \ge n, set c←c−nc \gets c - n. Return cc.

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

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

Theorem 2. Algorithm 1 returns ab mod nab \bmod n.

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

Updating the precomputation#

To multiply by ab mod nab \bmod n repeatedly, for example when building a table of powers a,a2,a3,…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<nb < n and bB=b^n+bˇbB = \hat b n + \check b.

Algorithm 2: Product with its precomputed quotient

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

Output: c=ab mod nc = ab \bmod n and c^=⌊cB/n⌋\hat c = \lfloor cB/n \rfloor.

  1. Compute the two-word product a^b=pB+e\hat a b = p B + e.
  2. c←(ab−pn) mod Bc \gets (ab - pn) \bmod B; if c≥nc \ge n, set c←c−nc \gets c - n.
  3. q←⌊b^aˇ/B⌋q \gets \lfloor \hat b \check a / B \rfloor.
  4. h←(baˇ−qn) mod Bh \gets (b \check a - qn) \bmod B; if h≥nh \ge n, set q←q+1q \gets q + 1.
  5. Return cc and c^=(e+q) mod B\hat c = (e + q) \bmod B.

Theorem 3. Algorithm 2 is correct.

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

⌊abBn⌋=⌊(a^n+aˇ)bn⌋=a^b+⌊aˇbn⌋.\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−⌊ab/n⌋nc = ab - \lfloor ab/n \rfloor n, we have ⌊cB/n⌋=⌊abB/n⌋−⌊ab/n⌋B\lfloor cB/n \rfloor = \lfloor abB/n \rfloor - \lfloor ab/n \rfloor B, and so ⌊cB/n⌋≡e+⌊aˇb/n⌋(modB)\lfloor cB/n \rfloor \equiv e + \lfloor \check a b/n \rfloor \pmod B. As c<nc < n, the left side is less than BB, so it equals the right side reduced modulo BB.

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

Use in FLINT#

The macro NMOD_CAN_USE_SHOUP(mod) tests the condition n<2FLINT_BITS−1n < 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-11-02).