Paper 2011/378
A generalization of the Lucas addition chains
Amadou TALL
Abstract
In this paper, we give a generalization of Lucas addition chains, where subtraction is allowed. We call them ''Lucas addition-subtraction chain''. We also show that this new method gives minimal addition-subtraction chains for infinitely many integers. This new method will also be used to prove that Lucas addition chains are optimal for many integers. Moreover, we show that Lucas addition chains give minimal addition chains for all integers of Hamming weight $3$, like the \emph{binary method}. Finally, we give a theorem to get short (and many times minimal) Lucas addition-subtraction chains.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Addition chains, exponentiation
- Keywords
- addition chainaddition-subtraction chainLucas chains
- Contact author(s)
- tallamad @ hotmail com
- History
- 2011-07-24: revised
- 2011-07-12: received
- See all versions
- Short URL
- https://ia.cr/2011/378
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/378,
author = {Amadou TALL},
title = {A generalization of the Lucas addition chains},
howpublished = {Cryptology ePrint Archive, Paper 2011/378},
year = {2011},
note = {\url{https://eprint.iacr.org/2011/378}},
url = {https://eprint.iacr.org/2011/378}
}
