Random Digit Representation of Integers - Archive ouverte HAL Access content directly
Conference Papers Year :

Random Digit Representation of Integers

(1) , (2)
1
2

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.
Fichier principal
Vignette du fichier
randdigitscalmul.pdf (286.1 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01311485 , version 1 (04-05-2016)

Identifiers

  • HAL Id : hal-01311485 , version 1

Cite

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

Collections

UNIV-TLN IMATH
85 View
219 Download

Share

Gmail Facebook Twitter LinkedIn More