Prime Field Multiplication in Adapated Modular Number System using Lagrange Representation - Archive ouverte HAL Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2006

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.
Fichier principal
Vignette du fichier
lramns.pdf (161.55 Ko) Télécharger le fichier

Dates et versions

hal-00079454 , version 1 (13-06-2006)
hal-00079454 , version 2 (13-06-2006)
hal-00079454 , version 3 (14-06-2007)
hal-00079454 , version 4 (14-06-2007)

Identifiants

  • HAL Id : hal-00079454 , version 2

Citer

Christophe Negre, Thomas Plantard. Prime Field Multiplication in Adapated Modular Number System using Lagrange Representation. 2006. ⟨hal-00079454v2⟩
201 Consultations
351 Téléchargements

Partager

Gmail Facebook X LinkedIn More