FLINT3.7.0-dev

Shoup multiplication

Synopsis#include <flint/ulong_extras.h>
ulong n_mulmod_precomp_shoup(ulong a, ulong n)source

Returns ⌊aB/n⌋\lfloor a B / n \rfloor, the precomputed data for n_mulmod_shoup. Requires a<na < n.

ulong n_mulmod_shoup(ulong a, ulong b, ulong a_precomp, ulong n)source

Returns ab mod nab \bmod n given a_precomp from n_mulmod_precomp_shoup. Requires a<na < n; bb is arbitrary.

void n_mulmod_precomp_shoup_quo_rem(ulong * a_pr_quo, ulong * a_pr_rem, ulong a, ulong n)source
ulong n_mulmod_precomp_shoup_rem_from_quo(ulong a_pr_quo, ulong n)source

Compute both the quotient ⌊aB/n⌋\lfloor aB/n \rfloor and the remainder aB mod naB \bmod n, as needed by n_mulmod_and_precomp_shoup. The second function recovers the remainder from a known quotient.

ulong n_mulmod_precomp_shoup_preinv(ulong a, ulong n, ulong ninv)source
void n_mulmod_precomp_shoup_quo_rem_preinv(ulong * a_pr_quo, ulong * a_pr_rem, ulong a, ulong n, ulong ninv)source

Same as n_mulmod_precomp_shoup and n_mulmod_precomp_shoup_quo_rem, given ninv from n_preinvert_limb(n) (the ninv of an nmod_t). They use multiplications instead of a hardware division: much faster where the division is slow (e.g. Skylake or Cascade Lake, and 64-bit ARM), about as fast on recent x86-64 processors. Require a<na < n; any n≠0n \ne 0.

void n_mulmod_and_precomp_shoup(ulong * ab, ulong * ab_precomp, ulong a, ulong b, ulong a_pr_quo, ulong a_pr_rem, ulong b_precomp, ulong n)source

Sets *ab to ab mod nab \bmod n and *ab_precomp to its precomputed data ⌊(ab mod n)B/n⌋\lfloor (ab \bmod n) B / n \rfloor, without a division. Requires a,b<na, b < n. Useful for building tables of powers a,a2,a3,…a, a^2, a^3, \ldots together with their precomputed data.

When many products abi mod na b_i \bmod n share the same aa and nn, Shoup's method [Sho2021] computes the quotient a^=⌊a2FLINT_BITS/n⌋\hat a = \lfloor a 2^{\mathtt{FLINT\_BITS}} / n \rfloor once, after which each product needs one high and two low multiplications and a single comparison, with no reduction step. This is the fastest way to multiply modulo nn in FLINT when it applies: scaling vectors and matrices, and multiplying by fixed roots of unity in number-theoretic transforms.

Requirements#

  • The modulus must satisfy n<2FLINT_BITS−1n < 2^{\mathtt{FLINT\_BITS} - 1}. This is what allows the final correction to be a single comparison.
  • The fixed operand must be reduced, a<na < n, so that a^\hat a fits in a word.
  • The other operand bb of n_mulmod_shoup may be any word. n_mulmod_and_precomp_shoup requires b<nb < n.

Computing the precomputed quotient#

n_mulmod_precomp_shoup computes a^\hat a with a two-word by one-word hardware division. Its cost varies widely between processors: it is a few multiplications' worth on recent x86-64, but tens of cycles on older ones such as Skylake and Cascade Lake, and 64-bit ARM has no two-word division instruction (FLINT then divides in software). When the precomputed inverse of nn is at hand, as mod.ninv in an nmod_t, n_mulmod_precomp_shoup_preinv and n_mulmod_precomp_shoup_quo_rem_preinv give the same results with multiplications only. On recent x86-64 processors the division is fast and runs alongside multiplications, so the two versions are close and the division can even win in code that is busy multiplying. The nmod modules choose between the two per target with _nmod_mulmod_precomp_shoup (Low-level macros).

Tables of powers#

To multiply by a,a2,a3,…a, a^2, a^3, \ldots in turn, each power needs its own precomputed quotient. Computing it with n_mulmod_precomp_shoup would cost a division per power. n_mulmod_and_precomp_shoup instead obtains the quotient of ab mod nab \bmod n from the quotient and remainder of aa and the quotient of bb, using one extra high product and two low products. The quotient and remainder of aa come from n_mulmod_precomp_shoup_quo_rem.

AlgorithmMultiplication by a fixed operand (Shoup)Computes ab mod nab \bmod n for fixed aa and nn with two low products, one high product and one comparison, using the precomputed quotient ⌊aB/n⌋\lfloor aB/n \rfloor.

Example#

Exampleshoup_basic.cchecked by make checkdoc
#include <flint/flint.h>
#include <flint/ulong_extras.h>

int main(void)
{
    ulong n = 1000003, a = 12345;      /* n < 2^(FLINT_BITS - 1), a < n */
    ulong a_pre = n_mulmod_precomp_shoup(a, n);
    ulong v[5] = { 1, 2, 3, 1000002, 4000000000 };
    ulong quo, rem, pw, pw_pre;
    int i;

    /* scale a vector by a; the entries need not be reduced */
    for (i = 0; i < 5; i++)
        v[i] = n_mulmod_shoup(a, v[i], a_pre, n);
    flint_printf("a*v = %wu %wu %wu %wu %wu\n", v[0], v[1], v[2], v[3], v[4]);

    /* powers of a, each with its precomputed quotient, without divisions */
    n_mulmod_precomp_shoup_quo_rem(&quo, &rem, a, n);
    pw = a;
    pw_pre = quo;
    flint_printf("powers:");
    for (i = 2; i <= 6; i++)
    {
        n_mulmod_and_precomp_shoup(&pw, &pw_pre, a, pw, quo, rem, pw_pre, n);
        flint_printf(" %wu", pw);
        if (pw_pre != n_mulmod_precomp_shoup(pw, n))
            flint_printf("(bad quotient)");
    }
    flint_printf("\n");
    return 0;
}
Output
a*v = 12345 24690 37035 987658 860447
powers: 398569 319545 771193 349025 700701

References#

Cite this page

The FLINT team, “Shoup multiplication (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/shoup.html (generated 2026-11-20).