GNU Multiple Precision Arithmetic Library (GMP) provides arbitrary-precision arithmetic for integers, rational numbers, and floating-point values. Here, its mpz_* integer functions support finite-field and cryptographic calculations involving very large integers. section 2.0 section 2.3
Finite-field code wraps GMP operations with modular addition, subtraction, multiplication, division, negation, inversion, square roots, random values, squaring, and exponentiation. APIs place the output first, matching the model a = b op c modulo n. section 2.3
Reliable GMP-based modular routines follow a small set of implementation rules:
- Initialize temporary mpz_t values with mpz_init(), use them for intermediate results, and release them with mpz_clear(). section 2.3
- Protect aliased inputs by computing into a separate result before assigning the reduced value. section 2.3
Modular addition and division
A modular addition wrapper initializes rslt, computes mpz_add(rslt, b, c), reduces it with mpz_mod(a, rslt, n), and clears the temporary. Modular division first computes c's inverse modulo n, reports failure if inversion fails, multiplies that inverse by b, and reduces the product.
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
Browse the C header defining explicit-modulus mod_* routines, shared-modulus m* routines, square-root helpers, random generation, and exponentiation. section 2.3
