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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
exponentiationinteger recoding
Contact author(s)
nicolas meloni @ univ-tln fr
History
2015-06-30: received
Short URL
https://ia.cr/2015/622
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/622,
      author = {Nicolas Méloni and M.  Anwar Hasan},
      title = {Random Digit Representation of Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2015/622},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/622}},
      url = {https://eprint.iacr.org/2015/622}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.