Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Generalised Mersenne numbers revisited

Authors: Robert Granger and Andrew Moss
Journal: Math. Comp. 82 (2013), 2389-2420
MSC (2010): Primary 12Y05, 11T71, 11Y16
Published electronically: May 8, 2013
MathSciNet review: 3073207
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Generalised Mersenne Numbers (GMNs) were defined by Solinas in 1999 and feature in the NIST (FIPS 186-2) and SECG standards for use in elliptic curve cryptography. Their form is such that modular reduction is extremely efficient, thus making them an attractive choice for modular multiplication implementation. However, the issue of residue multiplication efficiency seems to have been overlooked. Asymptotically, using a cyclic rather than a linear convolution, residue multiplication modulo a Mersenne number is twice as fast as integer multiplication; this property does not hold for prime GMNs, unless they are of Mersenne's form. In this work we exploit an alternative generalisation of Mersenne numbers for which an analogue of the above property -- and hence the same efficiency ratio -- holds, even at bitlengths for which schoolbook multiplication is optimal, while also maintaining very efficient reduction. Moreover, our proposed primes are abundant at any bitlength, whereas GMNs are extremely rare. Our multiplication and reduction algorithms can also be easily parallelised, making our arithmetic particularly suitable for hardware implementation. Furthermore, the field representation we propose also naturally protects against side-channel attacks, including timing attacks, simple power analysis and differential power analysis, which is essential in many cryptographic scenarios, in constrast to GMNs.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 11T71, 11Y16

Retrieve articles in all journals with MSC (2010): 12Y05, 11T71, 11Y16

Additional Information

Robert Granger
Affiliation: School of Mathematical Sciences, University College Dublin, Ireland

Andrew Moss
Affiliation: School of Computing, Blekinge Institute of Technology, Sweden

Keywords: Prime fields, high-speed arithmetic, elliptic curve cryptography, generalised Mersenne numbers, cyclotomic primes, generalised repunit primes
Received by editor(s): August 15, 2011
Received by editor(s) in revised form: February 23, 2012
Published electronically: May 8, 2013
Additional Notes: The first author was supported by the Claude Shannon Institute, Science Foundation Ireland Grant No. 06/MI/006.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society