PMNS for cryptography: A guided tour
Nicolas Méloni, François Palma, Pascal Véron · Advances in Mathematics of Communications · 2023
The Polynomial Modular Number System (PMNS) offers an alternative to the conventional binary multi-precision representation system for large integers. Its effectiveness has been demonstrated for various cryptosystems using prime field arithmetic [2,4,6], with prime sizes ranging from 256 to 736 bits. However, as the size of $ p $ increases, the relative performance of PMNS compared to standard arithmetic diminishes. Furthermore, the generation process of a PMNS has a worst-case complexity of $ {\mathcal O}(2^n) $, where $ n $ denotes the number of symbols used to represent an integer modulo $ p $ in this representation system. In this paper, we present several alternatives and improvements to the construction and implementation processes of PMNS, which are tailored to the size of $ p $.