Multiplication with a precomputed inverse

These functions compute ab \bmod n for a word-size modulus n. They form the inner loop of most modular arithmetic in FLINT; the nmod module wraps them together with the modulus and its inverse in an nmod_t.

Choosing a function#

• n_mulmod2_preinv is the general-purpose function. Compute ninv = n_preinvert_limb(n) once per modulus.
• n_mulmod2 computes ninv itself and is only worth using for a single multiplication.
• n_mulmod_preinv saves a few operations by requiring the modulus to be normalised (top bit set) and the operands reduced. To use it with any n, work with n 2^s and operands shifted left by s bits, where s is the number of leading zero bits of n, and pass s as norm. Results then also come out shifted by s bits.

n_mulmod_precomp uses a double inverse instead and requires n < 2^{53}. When one operand is fixed, n_mulmod_shoup is faster still; see Choosing a method for modular arithmetic for all options.

Algorithm#

The product ab is computed as a two-word integer and reduced with one step of Möller–Granlund division: one full and one low multiplication by the precomputed inverse, followed by at most two corrections. n_mulmod_preinv performs exactly this step, since its operands are already shifted. n_mulmod2_preinv passes the product to n_ll_mod_preinv, which shifts it to normalise the modulus; if the operands are not reduced, the high word of the product may be at least n, and a second division step reduces it first.

Examples#

The most basic use:

#include <flint/flint.h>
#include <flint/ulong_extras.h>

int main(void)
{
    ulong a = 12345678, b = 87654321, n = 111111111;
    ulong ninv = n_preinvert_limb(n);

    flint_printf("%wu * %wu mod %wu = %wu\n", a, b, n,
                 n_mulmod2_preinv(a, b, n, ninv));
    return 0;
}

12345678 * 87654321 mod 111111111 = 23456790

The inverse pays off when the modulus is reused. This computes 1000! modulo a prime with 999 multiplications and checks the result against n_factorial_mod2_preinv:

#include <flint/flint.h>
#include <flint/ulong_extras.h>

int main(void)
{
    ulong p = 4294967291;               /* the largest prime below 2^32 */
    ulong pinv = n_preinvert_limb(p);   /* computed once, used 999 times */
    ulong f = 1, k;

    for (k = 2; k <= 1000; k++)
        f = n_mulmod2_preinv(f, k, p, pinv);

    flint_printf("1000! mod p = %wu\n", f);
    flint_printf("check       = %wu\n", n_factorial_mod2_preinv(1000, p, pinv));
    return 0;
}

1000! mod p = 444887038
check       = 444887038