A modulus sets the size of a finite arithmetic system: results wrap around after reaching it, and numbers with the same remainder are congruent. A 12-hour clock therefore treats 15 and 3 as equivalent modulo 12. Prime moduli support finite-field addition, multiplication, and modular inverses. section 2.1
Implementation treats the modulus as an explicit operand or as shared state. GMP’s mpz_mod reduces addition, subtraction, multiplication, and division results; modular division first computes an inverse and rejects a noninvertible divisor. Temporary result storage prevents overlapping inputs from being clobbered. section 2.3
The modulus controls several related computations:
- Integer arithmetic reduces every result to its remainder modulo n. section 2.3
- An irreducible polynomial acts as a polynomial modulus, reducing powers above the field degree and preserving pᵏ possible values. section 8.2
- Cryptographic programs switch modulus domains, using a torsion value for exponent computations and a curve prime for point multipliers. section 19.5.3
Tiny modular examples
On a 12-hour clock, 9 + 6 = 15 is congruent to 3 modulo 12. In a prime field modulo 43, counting wraps from 42 to 0, while 0 and 1 support field operations and every nonzero value has an inverse. section 2.1
Listing 2.1 Header: modulo.h
#include <stdio.h> #1 #include <stdlib.h> #1 #include <gmp.h> #1 void mod_add(mpz_t a, mpz_t b, mpz_t c, mpz_t n); #2 void mod_sub(mpz_t a, mpz_t b, mpz_t c, mpz_t n); #2 void mod_mul(mpz_t a, mpz_t b, mpz_t c, mpz_t n); #2 void mod_div(mpz_t a, mpz_t b, mpz_t c, mpz_t n); #2 void mod_neg(mpz_t a, mpz_t b, mpz_t n); #2 void minit(mpz_t m); #3 void mget(mpz_t mod); #3 void mset(mpz_t prm); void madd(mpz_t a, mpz_t b, mpz_t c); #4 void msub(mpz_t a, mpz_t b, mpz_t c); #4 void mmul(mpz_t a, mpz_t b, mpz_t c); #4 void mdiv(mpz_t a, mpz_t b, mpz_t c); #4 void minv(mpz_t a, mpz_t b); #4 void mneg(mpz_t a, mpz_t b); #4 int msqrt(mpz_t x, mpz_t a); #4 void mrand(mpz_t rand); #4 int msqr(mpz_t x); #4 void mpowi(mpz_t a, mpz_t b, long i); #4
Use the modulo.h interface to compare routines that receive a modulus directly with routines that use initialized shared modulus state. section 2.3
