Skip to main content
placeholder image

Modular number systems: Beyond the mersenne family

Conference Paper


Abstract


  • In SAC 2003, J. Chung and A. Hasan introduced a new class of specific moduli for cryptography, called the more generalized Mersenne numbers, in reference to J. Solinas' generalized Mersenne numbers proposed in 1999. This paper pursues the quest. The main idea is a new representation, called Modular Number System (MNS), which allows efficient implementation of the modular arithmetic operations required in cryptography. We propose a modular multiplication which only requires n2 multiplications and 3(2n 2 - n + 1) additions, where n is the size (in words) of the operands. Our solution is thus more efficient than Montgomery for a very large class of numbers that do not belong to the large Mersenne family. © Springer-Verlag Berlin Heidelberg 2005.

Publication Date


  • 2005

Citation


  • Bajard, J. C., Imbert, L., & Plantard, T. (2005). Modular number systems: Beyond the mersenne family. In Lecture Notes in Computer Science Vol. 3357 (pp. 159-169).

Scopus Eid


  • 2-s2.0-24144452461

Start Page


  • 159

End Page


  • 169

Volume


  • 3357

Abstract


  • In SAC 2003, J. Chung and A. Hasan introduced a new class of specific moduli for cryptography, called the more generalized Mersenne numbers, in reference to J. Solinas' generalized Mersenne numbers proposed in 1999. This paper pursues the quest. The main idea is a new representation, called Modular Number System (MNS), which allows efficient implementation of the modular arithmetic operations required in cryptography. We propose a modular multiplication which only requires n2 multiplications and 3(2n 2 - n + 1) additions, where n is the size (in words) of the operands. Our solution is thus more efficient than Montgomery for a very large class of numbers that do not belong to the large Mersenne family. © Springer-Verlag Berlin Heidelberg 2005.

Publication Date


  • 2005

Citation


  • Bajard, J. C., Imbert, L., & Plantard, T. (2005). Modular number systems: Beyond the mersenne family. In Lecture Notes in Computer Science Vol. 3357 (pp. 159-169).

Scopus Eid


  • 2-s2.0-24144452461

Start Page


  • 159

End Page


  • 169

Volume


  • 3357