Advertisement
Published in:
2008 | OriginalPaper | Chapter
Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation
Authors : Christophe Negre, Thomas Plantard
Published in: Information Security and Privacy
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.