GMNT: Generalized Mersenne Number Toolbox

I had hoped the GMNT would eventually be a collection of tools for working with generalized Mersenne numbers. At the moment there is only the one tool, mrw.

Comments, questions, bugs and suggestions are welcome, contact Greg Zaverucha (gzaveruc@cs.uwaterloo.ca).


mrw

mrw generates C code to perform modular reduction for a (somewhat) arbitrary generalized Mersenne (GM) modulus. It can also be used to compute the modular reduction weight (MRW) of a given polynomial.

GM numbers have the form N = f(2^k) where f is a polynomial of the form
    f(t) = t^d - c_1*t^{d-1} - c_2*t^{d-2} - ... - c_d
for integers c_i. For this software, k must be a multiple of 32. Examples of GM primes are NIST primes reccomended for elliptic curve cryptography. For more information about GM numbers see [1], for information about the performance of modular arithmetic with GM numbers, see [1].

Essentially mrw automates the methods described in [Solinas 1999] to compute the MRW and determine the reduction function. The MRW is the number of add/subtract operations required to implement the reduction function. The output is three files, a C file and corresponding header and a test program to make sure the reduction routine works correctly.

Additional documentation is available in the included README.


Download mrw-1.0.tgz
Requires Perl and GMP ( and optionally PARI/GP)

References


Last updated: October, 2011