This manual describes how to use the MPM bignum modular arithmetic library.
Copyright 2002, 2007 Kevin Ryde
MPM is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version.
Nothing is built or installed by default, but a build can be done with
Since various GNU MP internals are used it's only possible to compile against a GNU MP build tree, but mpm.h and the resulting libmpm.a can then be used from anywhere. mpm.h provides all prototypes and defines.
#include <gmp.h> #include "mpm.h"
And an application should link against libmpm.a, for example with
gcc myprog.c libmpm.a -lgmp
Note that libmpm.a can only be used with the particular libgmp it was built for.
A modulus is represented by a type
mpm_t, and a residue by
The modulus should be initialized first (see Initializing Moduli), and then residues are initialized for use with that modulus (see Initializing Residues).
mpr_t can only be used with the particular modulus it was
initialized against (using the wrong modulus will have unpredictable results).
mpr_t can be cleared then and re-initialized for a new modulus.
mpr_t is passed as a parameter it's effectively
call-by-reference, meaning that any change to its value is made to the copy in
the caller as well. The usual way to return results from a function is to
designate certain parameters as outputs, and set their values in the function.
This is as per
mpz_t (see Parameter Conventions).
Note however that
mpr_init and friends are macros which operate only on
mpr_t, not in any caller. This is because
just a pointer which
mpr_init assigns to. This is different from how
mpz_t works, but it makes the implementation more efficient, and allows
the compiler to detect any
mpr_t variables used uninitialized.
const cannot be used with
mpr_t currently. Perhaps this will
mpm_initis not fast since it pre-computes various values associated with the modulus, for subsequent use in
mpr_divis not much more than a combination of
mpr_invertis quite slow, being effectively an extended GCD against the modulus. An application using the same divisor repeatedly is best off taking an inverse once then using that with
mpr_addmul_uiare good for small multipliers. In particular with REDC it's better to multiply by a small operand than to convert that to a residue.
mpr_add_ui is good in the plain division method, but for REDC it's best
to convert to an
mpr_t if the same
ui value is going to be used
Initialize m for operations modulo op.
Currently odd values use REDC (basecase or sub-quadratic according to the size), but even values only use a simple division method which may be less efficient. Special values 2^N and 2^N-1 are not noticed; if they're likely to occur then an application should check and use
Initialize m for operations mod 2^n-1.
Return a reference to the modulus value of m. The value must not be changed, but it can be used as a source operand for normal
Set rop to the value of op, both residues mod m.
Set rop to the value of op, converting it to a residue mod m.
Set rop from a null-terminated string str in the given base. The return value is 0 if the string is valid, or -1 if not. Parsing is the same as for
Get the value of op, a residue mod m, as an integer in the range 0 to m-1.
If the result is too big to fit an
unsigned longthen just the least significant bits that do fit are returned.
Set rop to the value of op, a residue mod m. rop will be in the range 0 to m-1.
Swap the values of op1 and op2, residues mod m.
Initialize rop and set it to the value of op, mod m.
Initialize rop and set its value from a null-terminated string str in the given base. The return value is 0 if the string is valid, or -1 if not. rop is still initialized if the string is invalid. Parsing is the same as for
Set rop to op1 + op2, mod m.
Set rop to rop + op1 times op2, mod m.
Set rop to op1 / op2, mod m. op2 and m must have no common factors for this result to exist and be unique, if there are common factors then the behaviour of this function is undefined.
Set rop to op1 / 2^op2, mod m. m must be odd, otherwise the behaviour of this function is undefined.
Set rop to 1 / op, mod m. If this inverse exists and is unique the return value is non-zero, if not then the return value is zero and rop is undefined. The inverse will exist whenever op and m have no common factors.
Set rop to op1 times op2, mod m.
Set rop to op1 times 2^op2, mod m.
Set rop to op1 to the power op2, mod m.
Set rop to op1 - op2, mod m.
Set rop to rop - op1 times op2, mod m.
Return non-zero if op1 and op2 are equal, mod m.
Return non-zero if op is equal to 1, 0 or -1, respectively, mod m.
Set rop to the greatest common divisor of op and the modulus m.
If op is zero then rop is set to m, otherwise rop is in the range 1 <= rop < m.
Return the value of the Jacobi symbol (op/m). m must be odd.
Return 1 if the modulus value m is a strong probable prime (sprp) to the given base b, or 0 if not.
For m written as m = e*2^k, with e odd, m is an sprp if either b^e = 1 mod m, or b^(e*2^i) = -1 mod m for some 0 <= i < k.
mpr_sprp_preturns 0, m is definitely composite. But when it returns 1, m is only “probably prime” because although all primes get a return of 1, a few composites (called strong pseudoprimes) do too. If base b is chosen randomly then
mpr_sprp_pis a single run of the Miller-Rabin primality testing algorithm.
REDC is Peter L. Montgomery's algorithm from “Modular Multiplication Without Trial Division”, Mathematics of Computation, volume 44, number 170, April 1985. Residues are kept in the range 0 to m-1 and for an input x the value held is x*R mod m, where R is a power of 2 chosen as the next whole number of limbs bigger than m.
The key to this representation is that it allows the reduction part of a modular multiplication to be implemented using an “exact remainder” style, which is simpler and a little faster, especially for smallish moduli.
For plain division, residues are also kept in the range 0 to m-1.
mpm_clear: Initializing Moduli
mpm_init: Initializing Moduli
mpm_init_2exp: Initializing Moduli
mpm_init_2expsub1: Initializing Moduli
mpm_init_str: Initializing Moduli
mpm_init_ui: Initializing Moduli
mpm_modref: Initializing Moduli
mpm_t: Types and Conventions
mpr_add: Residue Arithmetic
mpr_add_ui: Residue Arithmetic
mpr_addmul_ui: Residue Arithmetic
mpr_clear: Initializing Residues
mpr_div: Residue Arithmetic
mpr_div_2exp: Residue Arithmetic
mpr_equal: Residue Comparisons
mpr_equal_negone: Residue Comparisons
mpr_equal_one: Residue Comparisons
mpr_equal_ui: Residue Comparisons
mpr_equal_zero: Residue Comparisons
mpr_gcd: Number Theoretic Functions
mpr_get_ui: Assigning Residues
mpr_get_z: Assigning Residues
mpr_init: Initializing Residues
mpr_init_set: Simultaneous Residue Init & Assign
mpr_init_set_si: Simultaneous Residue Init & Assign
mpr_init_set_str: Simultaneous Residue Init & Assign
mpr_init_set_ui: Simultaneous Residue Init & Assign
mpr_init_set_z: Simultaneous Residue Init & Assign
mpr_invert: Residue Arithmetic
mpr_jacobi: Number Theoretic Functions
mpr_mul: Residue Arithmetic
mpr_mul_2exp: Residue Arithmetic
mpr_mul_si: Residue Arithmetic
mpr_mul_ui: Residue Arithmetic
mpr_neg: Residue Arithmetic
mpr_pow: Residue Arithmetic
mpr_pow_ui: Residue Arithmetic
mpr_set: Assigning Residues
mpr_set_si: Assigning Residues
mpr_set_str: Assigning Residues
mpr_set_ui: Assigning Residues
mpr_set_z: Assigning Residues
mpr_sprp_p: Number Theoretic Functions
mpr_sub: Residue Arithmetic
mpr_sub_ui: Residue Arithmetic
mpr_submul_ui: Residue Arithmetic
mpr_swap: Assigning Residues
mpr_t: Types and Conventions
mpr_ui_pow: Residue Arithmetic
mpr_ui_pow_ui: Residue Arithmetic
mpr_z_pow_ui: Residue Arithmetic