Shoup multiplication
#include <flint/ulong_extras.h>Returns , the precomputed data for n_mulmod_shoup. Requires .
Returns given a_precomp from n_mulmod_precomp_shoup. Requires ; is arbitrary.
Compute both the quotient and the remainder , as needed by n_mulmod_and_precomp_shoup. The second function recovers the remainder from a known quotient.
void n_mulmod_precomp_shoup_quo_rem_preinv(ulong * a_pr_quo, ulong * a_pr_rem, ulong a, ulong n, ulong ninv)sourceSame 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 ; any .
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)sourceSets *ab to and *ab_precomp to its precomputed data , without a division. Requires . Useful for building tables of powers together with their precomputed data.
When many products share the same and , Shoup's method [Sho2021] computes the quotient 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 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 . This is what allows the final correction to be a single comparison.
- The fixed operand must be reduced, , so that fits in a word.
- The other operand of
n_mulmod_shoupmay be any word.n_mulmod_and_precomp_shouprequires .
Computing the precomputed quotient#
n_mulmod_precomp_shoup computes 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 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 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 from the quotient and remainder of and the quotient of , using one extra high product and two low products. The quotient and remainder of come from n_mulmod_precomp_shoup_quo_rem.
Example#
#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;
}a*v = 12345 24690 37035 987658 860447 powers: 398569 319545 771193 349025 700701
References#
- [Sho2021] V. Shoup, "Arithmetic software libraries", chapter 9 of Computational Cryptography, Cambridge University Press (2021), https://doi.org/10.1017/9781108854207.012
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).
@misc{flint-doc-ulong-extras-shoup,
author = {{The FLINT team}},
title = {{Shoup multiplication (ulong\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/ulong_extras/shoup.html},
note = {Generated 2026-11-20}
}