Efficient modular arithmetic in adapted modular number system using lagrange representation

Authors

Christophe Negre, University of Perpignan
Thomas Plantard, University of WollongongFollow

RIS ID

26125

Publication Details

Negre, C. & Plantard, T. (2008). Efficient modular arithmetic in adapted modular number system using lagrange representation. Australasian Conference on Information Security and Privacy (pp. 463-477). Berlin, Germany: Springer.

Abstract

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.