Selected RNS Bases for Modular Multiplication

Jean-Claude Bajard 1 Marcelo Kaihara 2 Thomas Plantard 3
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : The selection of the elements of the bases in an RNS modular multiplication method is crucial and has a great impact in the overall performance. This work proposes specific sets of optimal RNS moduli with elements of Hamming weight three whose inverses used in the MRS reconstruction have very small Hamming weight. This property is exploited in RNS bases conversions, to completely remove and replace the products by few additions/subtractions and shifts, reducing the time complexity of modular multiplication. These bases are specially crafted to computation with operands of sizes 256 or more and are suitable for cryptographic applications such as the ECC protocols.
Type de document :
Communication dans un congrès
ARITH'2009: 19th Symposium on Computer Arithmetic, Jun 2009, Portland, Oregon, United States. IEEE, pp.25-35, 2009, 〈http://www.ac.usc.es/arith19〉. 〈10.1109/ARITH.2009.20〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394985
Contributeur : Jean Claude Bajard <>
Soumis le : samedi 13 juin 2009 - 16:50:12
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07

Identifiants

Collections

Citation

Jean-Claude Bajard, Marcelo Kaihara, Thomas Plantard. Selected RNS Bases for Modular Multiplication. ARITH'2009: 19th Symposium on Computer Arithmetic, Jun 2009, Portland, Oregon, United States. IEEE, pp.25-35, 2009, 〈http://www.ac.usc.es/arith19〉. 〈10.1109/ARITH.2009.20〉. 〈lirmm-00394985〉

Partager

Métriques

Consultations de la notice

76