Efficient modular arithmetic in adapted modular number system using lagrange representation
In 2004, Bajard, Imbert and Plantard introduced a new system of representation to perform arithmetic modulo a prime integer p, the Adapted Modular Number System (AMNS). In this system, the elements are seen as polynomial of degree n − 1 with the coefficients of size p 1/n . The best method for multiplication in AMNS works only for some specific moduli p. In this paper, we propose a novel algorithm to perform the modular multiplication in the AMNS. This method works for any AMNS, and does not use a special form of the modulo p. We also present a version of this algorithm in Lagrange Representation which performs the polynomial multiplication part of the first algorithm efficiently using Fast Fourier Transform.
Please refer to publisher version or contact your library.