# Signed bits and fast exponentiation

Journal de théorie des nombres de Bordeaux (2001)

- Volume: 13, Issue: 1, page 27-41
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topBosma, Wieb. "Signed bits and fast exponentiation." Journal de théorie des nombres de Bordeaux 13.1 (2001): 27-41. <http://eudml.org/doc/248706>.

@article{Bosma2001,

abstract = {An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that the use of signed bits (instead of bits for ordinary repeated squaring and multiplication) reduces the cost of exponentiation by one ninth.},

author = {Bosma, Wieb},

journal = {Journal de théorie des nombres de Bordeaux},

keywords = {signed bits; fast exponentiation; non-adjacent form; binary representation; redundant expansions},

language = {eng},

number = {1},

pages = {27-41},

publisher = {Université Bordeaux I},

title = {Signed bits and fast exponentiation},

url = {http://eudml.org/doc/248706},

volume = {13},

year = {2001},

}

TY - JOUR

AU - Bosma, Wieb

TI - Signed bits and fast exponentiation

JO - Journal de théorie des nombres de Bordeaux

PY - 2001

PB - Université Bordeaux I

VL - 13

IS - 1

SP - 27

EP - 41

AB - An exact analysis is given of the benefits of using the non-adjacent form representation for integers (rather than the binary representation), when computing powers of elements in a group in which inverting is easy. By counting the number of multiplications for a random exponent requiring a given number of bits in its binary representation, we arrive at a precise version of the known asymptotic result that on average one in three signed bits in the non-adjacent form is non-zero. This shows that the use of signed bits (instead of bits for ordinary repeated squaring and multiplication) reduces the cost of exponentiation by one ninth.

LA - eng

KW - signed bits; fast exponentiation; non-adjacent form; binary representation; redundant expansions

UR - http://eudml.org/doc/248706

ER -

## References

top- [1] S. Arno, F.S. Wheeler, Signed digit representations of minimal Hamming weight. IEEE Transactions on Computers42 (1993), 1007-1010.
- [2] A.D. Booth, A signed binary multiplication technique. Quart. Journ. Mech. and Applied Math.4 (1951), 236-240. Zbl0043.12902MR41526
- [3] D.M. Gordon, A survey of fast exponentiation methods. Journal of Algorithms27 (1998), 129-146. Zbl0915.11064MR1613189
- [4] R.L. Graham, A.C.-C. Yao, F.-F. Yao, Addition chains with multiplicative cost. Discrete Math.23 (1978), 115-119. Zbl0391.10039MR523407
- [5] A.F. Horadam, Jacobsthal representation numbers. Fibonacci Quart.34 (1996), 40-54. Zbl0869.11013MR1371475
- [6] D.E. Knuth, The Art of Computer Programming 2: Seminumerical Algorithms (third edition), Reading: Addison Wesley, 1998. Zbl0895.68054MR378456
- [7] Neal Koblitz, CM-curves with good cryptographic properties, in: Feigenbaum (ed), Advances in Cryptology — Proceedings of Crypto '91, Lecture Notes in Computer Science 576, (1991), 279-296. Zbl0780.14018MR1243654
- [8] D.P. McCarthy, Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains. Math. Comp.46 (1976), 603-608. Zbl0608.68027MR829630
- [9] F. Morain, J. Olivos, Speeding up the computations on an elliptic curve using additionsubtraction chains. RAIRO Inform. Theory24 (1990), 531-543. Zbl0724.11068MR1082914
- [10] N.J.A. Sloane, S. Plouffe, The encyclopedia of integer sequences. San Diego: Academic Press, 1995. http://www.research.att.com/njas/sequences/ Zbl0845.11001MR1327059
- [11] Hugo Volger, Some results on addition/subtraction chains. Information Processing Letters20 (1985), 155-160. Zbl0574.10052MR801983

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.