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.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-univ-tln.archives-ouvertes.fr/hal-01311485
Contributor : Nicolas Méloni <>
Submitted on : Wednesday, May 4, 2016 - 11:50:07 AM
Last modification on : Wednesday, June 20, 2018 - 3:20:01 PM
Long-term archiving on : Tuesday, November 15, 2016 - 7:54:20 PM

File

randdigitscalmul.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

111

Files downloads

241