Modular number systems: Beyond the Mersenne family

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 pro-posed in 1999. This paper pursues the quest. The main idea is a new representation, called Modular Number System (MNS), which allows ef-ficient implementation of the modular arithmetic operations required in cryptography. We propose a modular multiplication which only requires n2 multiplications and 3(2n2 − n + 1) additions, where n is the size (in words) of the operands. Our solution is thus more efficient than Mont-gomery for a very large class of numbers that do not belong to the large Mersenne family