Modular arithmetic with integers

These functions reduce, invert, exponentiate and take square roots of integers modulo an integer $m$ given as an fmpz_t. Each call is self-contained: no data about $m$ is kept between calls. They are the right choice for a few operations; for many operations with the same modulus the module fmpz_mod (which stores precomputed data in a context) or, for a word-size modulus, nmod.h is faster.

Residues#

fmpz_mod returns the residue in $[0, |m|)$, and fmpz_smod the symmetric residue $y$ with $-|m|/2 < y \le |m|/2$. Both require $m \ne 0$ without checking it. fmpz_mod_ui, fmpz_fdiv_ui and fmpz_get_nmod reduce modulo a word. For the results of fmpz_invmod, fmpz_powm and fmpz_sqrtmod, the inputs may be any integers; they are reduced first.

Inversion#

fmpz_invmod returns 1 and the inverse in $[0, |m|)$ if $\gcd(g, m) = 1$, and 0 otherwise, so it doubles as a coprimality test. Modulo $\pm 1$ every $g$ is invertible with inverse 0. Word-size moduli use n_gcdinv; larger ones GMP's mpz_invert, an extended GCD (Integer GCD). For a modulus whose factors are needed when the inverse does not exist, use fmpz_gcdinv or the extended GCD functions of GCD, LCM and Bézout coefficients.

Exponentiation#

fmpz_powm and fmpz_powm_ui require $m \ge 1$ and return $g^e \bmod m$ in $[0, m)$; for $m = 1$ the result is 0 even for $e = 0$. fmpz_powm also accepts $e < 0$ and then inverts $g$ first, raising an exception if $g$ is not invertible. The algorithm depends on the sizes:

• a word-size modulus with a word-size base: n_powmod2_ui_preinv (or GMP for an exponent that is not a word);
• a large base with a word-size modulus, or a large modulus below 70000 bits: GMP's mpz_powm and mpz_powm_ui, which use Montgomery reduction [Mon1985] with a sliding window;
• $m$ of at least 70000 bits, in builds with fft_small: binary or sliding-window exponentiation in the gr context of $\mathbb{Z}/m\mathbb{Z}$ (gr_ctx_init_fmpz_mod), where each modular multiplication is a product followed by a division with a precomputed inverse of $m$ (fmpz_fdiv_r_preinvn), so that both steps use FLINT's FFT multiplication (Callers and thresholds);
• exponents $e \le 4$ with a large modulus are done by one to three multiplications and reductions.

Square roots#

fmpz_sqrtmod computes a square root modulo a prime $p$. It returns 1 and a root if $a$ is a square modulo $p$ (0 and 1 are their own roots), and 0 with $b = 0$ otherwise. It chooses, as nmod_sqrt does for words (Square roots modulo a prime), between $a^{(p+1)/4}$ for $p \equiv 3 \pmod 4$, Atkin's formula for $p \equiv 5 \pmod 8$, Tonelli–Shanks when $2^s \| p - 1$ for $s < 32$, and Müller's Lucas sequence variant of the Cipolla–Lehmer method otherwise (Square roots modulo a prime). Primality of $p$ is not checked: for even $p$ and for perfect squares $p$ the function returns 0, and for other composite $p$ a return value of 1 does not guarantee anything.

Example#

Computations modulo the Mersenne prime $p = 2^{127} - 1$, and modulo 12:

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

int main(void)
{
    fmpz_t p, a, b, e, x;

    fmpz_init(p); fmpz_init(a); fmpz_init(b); fmpz_init(e); fmpz_init(x);

    /* p = 2^127 - 1 is prime */
    fmpz_one_2exp(p, 127);
    fmpz_sub_ui(p, p, 1);

    /* Fermat: 3^(p-1) = 1 mod p */
    fmpz_set_ui(a, 3);
    fmpz_sub_ui(e, p, 1);
    fmpz_powm(x, a, e, p);
    flint_printf("3^(p-1) mod p = "); fmpz_print(x); flint_printf("\n");

    /* inverses: 3^-1 mod p, and a negative exponent */
    fmpz_invmod(x, a, p);
    flint_printf("3^-1 mod p = "); fmpz_print(x); flint_printf("\n");
    fmpz_set_si(e, -2);
    fmpz_powm(b, a, e, p);
    fmpz_mul(x, x, x);
    fmpz_mod(x, x, p);
    flint_printf("3^-2 mod p agrees: %d\n", fmpz_equal(x, b));

    /* not invertible modulo 12 */
    fmpz_set_ui(b, 12);
    fmpz_set_si(a, -9);
    flint_printf("invmod(-9, 12) = %d\n", fmpz_invmod(x, a, b));
    fmpz_mod(x, a, b);
    flint_printf("-9 mod 12 = "); fmpz_print(x);
    fmpz_smod(x, a, b);
    flint_printf(", smod = "); fmpz_print(x); flint_printf("\n");

    /* square roots modulo p */
    fmpz_set_ui(a, 2);
    if (fmpz_sqrtmod(x, a, p))
    {
        fmpz_mul(b, x, x);
        fmpz_mod(b, b, p);
        flint_printf("sqrt(2) mod p = "); fmpz_print(x);
        flint_printf(", squared: "); fmpz_print(b); flint_printf("\n");
    }
    fmpz_set_si(a, -1);
    flint_printf("-1 is a square mod p: %d\n", fmpz_sqrtmod(x, a, p));

    fmpz_clear(p); fmpz_clear(a); fmpz_clear(b); fmpz_clear(e); fmpz_clear(x);
    return 0;
}

3^(p-1) mod p = 1
3^-1 mod p = 113427455640312821154458202477256070485
3^-2 mod p agrees: 1
invmod(-9, 12) = 0
-9 mod 12 = 3, smod = 3
sqrt(2) mod p = 18446744073709551616, squared: 2
-1 is a square mod p: 0

Since $2^{128} = 2 \cdot 2^{127} \equiv 2 \pmod p$, the root found is $2^{64}$. As $p \equiv 3 \pmod 4$, $-1$ is not a square.