Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Nicolas Méloni Connect in order to contact the contributor
Submitted on : Wednesday, May 4, 2016 - 11:50:07 AM
Last modification on : Tuesday, December 7, 2021 - 3:16:02 PM
Long-term archiving on: : Tuesday, November 15, 2016 - 7:54:20 PM


Files produced by the author(s)


  • HAL Id : hal-01311485, version 1



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



Record views


Files downloads