PMNS for Efficient Arithmetic and Small Memory Cost
Fangan Yssouf Dosso, Jean-Marc Robert, Pascal Véron · IEEE Transactions on Emerging Topics in Computing · 2022
The Polynomial Modular Number System (PMNS) is an integer number system which aims to speed up arithmetic operations modulo a prime$p$. Such a system is defined by a tuple$(p, n, \gamma, \rho, E)$, where$p$,$n$,$\gamma$and$\rho$are positive integers,$E\in \mathbb {Z}[X]$, with$E(\gamma) \equiv 0 \pmod p$. In (Didier,et al.2020) conditions required to build efficient AMNS (PMNS with$E(X)=X^{n} - \lambda$, where$\lambda \in \mathbb {Z}\setminus \lbrace 0\rbrace$) are provided. In this paper, we generalise their approach for any monic polynomial$E\in \mathbb {Z}[X]$of degree$n$. We present new bounds and highlight a set of polynomials$E$for very efficient operations in the PMNS and low memory requirement. We also provide AMNS and PMNS modular multiplication implementations, for a prime of size 256 bits, in classic C. We also provide, for the same prime, the first implementation taking advantage of the SIMDAVX512instruction set. TheAVX512PMNS is 72 % faster than its AMNS counterpart (classical C version). This version presents a more than 60 % speed-up in comparison with the state-of-the-art Montgomery-CIOS modular multiplication of theGMPlibrary.