Random Digit Representation of Integers

Nicolas Méloni (1) , M. Anwar Hasan (2)

1 IMATH - Institut de Mathématiques de Toulon - EA 2134
2 University of Waterloo [Waterloo]

—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.

Domains: Cryptography and Security [cs.CR]; Computer Arithmetic

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