Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Efficient Modular Arithmetic in Adapted Modular Number System Using Lagrange Representation
verfasst von : Christophe Negre, Thomas Plantard
Erschienen in: Information Security and Privacy
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.