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
- [1] J. Solinas, Generalized Mersenne Numbers, CACR Technical Report CORR 99-39, 1999.
- [2] G. M. Zaverucha, Generalized Mersenne Numbers in Pairing-Based Cryptography, MCS Thesis, Faculty of Computer Science, Dalhousie University, 2006. (PDF)
