Random Digit Representation of Integers

Abstract : —Modular exponentiation, or scalar multiplication , is core to today's main stream public key cryptographic systems. In this article we generalize the classical fractional wNAF method for modular exponentiation-the classical method uses a digit set of the form {1, 3,. .. , m} which is extended here to any set of odd integers of the form {1, d2,. .. , dn}. We propose a general modular exponentiation algorithm based on a generalization of the frac-wNAF recoding and a new precomputation scheme. We also give general formula for the average density of non-zero therms in these representations, prove that there are infinitely many optimal sets for a given number of digits and show that the asymptotic behavior, when those digits are randomly chosen, is very close to the optimal case.
Type de document :
Communication dans un congrès
ARITH 23, Jul 2016, San Francisco, United States
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-univ-tln.archives-ouvertes.fr/hal-01311485
Contributeur : Nicolas Méloni <>
Soumis le : mercredi 4 mai 2016 - 11:50:07
Dernière modification le : mercredi 20 juin 2018 - 15:20:01
Document(s) archivé(s) le : mardi 15 novembre 2016 - 19:54:20

Fichier

randdigitscalmul.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01311485, version 1

Collections

Citation

Nicolas Méloni, M. Anwar Hasan. Random Digit Representation of Integers. ARITH 23, Jul 2016, San Francisco, United States. 〈hal-01311485〉

Partager

Métriques

Consultations de la notice

76

Téléchargements de fichiers

139