Prime Field Multiplication in Adapated Modular Number System using Lagrange Representation
Résumé
In SAC'04 Bajard et al. introduced a new system of representation for integer arithmetic modulo a prime integer p, the Modular Number System. The multiplication in the MNS consists of a multiplication of two polynomials and a reduction of the coefficients. In this paper, we propose to use a Lagrange Representation to perform the polynomial multiplication in the MNS Algorithm. This method provides a multiplier with a complexity of n multiplications and n(3log_2(n)+2) additions of computer words. In practice, our method becomes better than usual methods when the size of the fields are larger than 500bits.