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 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.
References