Generalised Mersenne Numbers Revisited

Mathematics – Number Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

32 pages. Accepted to Mathematics of Computation

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Generalised Mersenne Numbers Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalised Mersenne Numbers Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalised Mersenne Numbers Revisited will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-302311

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.