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
make mpm
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
mpr_t
.
The modulus should be initialized first (see Initializing Moduli), and then residues are initialized for use with that modulus (see Initializing Residues).
An mpr_t
can only be used with the particular modulus it was
initialized against (using the wrong modulus will have unpredictable results).
An mpr_t
can be cleared then and re-initialized for a new modulus.
When an 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
the local mpr_t
, not in any caller. This is because mpr_t
is
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
change.
mpm_init
is not fast since it pre-computes various values associated
with the modulus, for subsequent use in mpr
operations.
mpr_div
is not much more than a combination of mpr_invert
and
mpr_mul
, and mpr_invert
is 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_mul
as required.
mpr_mul_ui
, mpr_mul_si
and mpr_addmul_ui
are 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
repeatedly.
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
mpm_init_2exp
ormpm_init_2expsub1
below.
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
mpz
functions.
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
mpz_set_str
.
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 long
then 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
mpz_set_str
.
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.
When
mpr_sprp_p
returns 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 thenmpr_sprp_p
is 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 Modulimpm_init
: Initializing Modulimpm_init_2exp
: Initializing Modulimpm_init_2expsub1
: Initializing Modulimpm_init_str
: Initializing Modulimpm_init_ui
: Initializing Modulimpm_modref
: Initializing Modulimpm_t
: Types and Conventionsmpr_add
: Residue Arithmeticmpr_add_ui
: Residue Arithmeticmpr_addmul_ui
: Residue Arithmeticmpr_clear
: Initializing Residuesmpr_div
: Residue Arithmeticmpr_div_2exp
: Residue Arithmeticmpr_equal
: Residue Comparisonsmpr_equal_negone
: Residue Comparisonsmpr_equal_one
: Residue Comparisonsmpr_equal_ui
: Residue Comparisonsmpr_equal_zero
: Residue Comparisonsmpr_gcd
: Number Theoretic Functionsmpr_get_ui
: Assigning Residuesmpr_get_z
: Assigning Residuesmpr_init
: Initializing Residuesmpr_init_set
: Simultaneous Residue Init & Assignmpr_init_set_si
: Simultaneous Residue Init & Assignmpr_init_set_str
: Simultaneous Residue Init & Assignmpr_init_set_ui
: Simultaneous Residue Init & Assignmpr_init_set_z
: Simultaneous Residue Init & Assignmpr_invert
: Residue Arithmeticmpr_jacobi
: Number Theoretic Functionsmpr_mul
: Residue Arithmeticmpr_mul_2exp
: Residue Arithmeticmpr_mul_si
: Residue Arithmeticmpr_mul_ui
: Residue Arithmeticmpr_neg
: Residue Arithmeticmpr_pow
: Residue Arithmeticmpr_pow_ui
: Residue Arithmeticmpr_set
: Assigning Residuesmpr_set_si
: Assigning Residuesmpr_set_str
: Assigning Residuesmpr_set_ui
: Assigning Residuesmpr_set_z
: Assigning Residuesmpr_sprp_p
: Number Theoretic Functionsmpr_sub
: Residue Arithmeticmpr_sub_ui
: Residue Arithmeticmpr_submul_ui
: Residue Arithmeticmpr_swap
: Assigning Residuesmpr_t
: Types and Conventionsmpr_ui_pow
: Residue Arithmeticmpr_ui_pow_ui
: Residue Arithmeticmpr_z_pow_ui
: Residue Arithmetic