Cryptology ePrint Archive: Report 2015/622

Random Digit Representation of Integers

Nicolas Méloni and M. Anwar Hasan

Abstract: Modular exponentiation is core to today's main stream public key cryptographic systems. In this article, we generalize the classical fractional $w$NAF method for modular exponentiation -- the classical method uses a digit set of the form $\{1,3,\dots,m\}$ which is extended here to any set of odd integers of the form $\{1,d_2,\dots, d_n\}$. We give a formula for the average density of non-zero terms in this new representation and discuss its asymptotic behavior when those digits are randomly chosen from a given set. We also propose a specific method for the precomputation phase of the exponentiation algorithm.

Category / Keywords: exponentiation, integer recoding

Date: received 23 Jun 2015

Contact author: nicolas meloni at univ-tln fr

Available format(s): PDF | BibTeX Citation

Version: 20150630:183406 (All versions of this report)

Short URL: ia.cr/2015/622

Discussion forum: Show discussion | Start new discussion