Signed bits and fast exponentiation

Wieb Bosma

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

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

Abstract

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

How to cite

top

Bosma, 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. [1] S. Arno, F.S. Wheeler, Signed digit representations of minimal Hamming weight. IEEE Transactions on Computers42 (1993), 1007-1010. 
  2. [2] A.D. Booth, A signed binary multiplication technique. Quart. Journ. Mech. and Applied Math.4 (1951), 236-240. Zbl0043.12902MR41526
  3. [3] D.M. Gordon, A survey of fast exponentiation methods. Journal of Algorithms27 (1998), 129-146. Zbl0915.11064MR1613189
  4. [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. [5] A.F. Horadam, Jacobsthal representation numbers. Fibonacci Quart.34 (1996), 40-54. Zbl0869.11013MR1371475
  6. [6] D.E. Knuth, The Art of Computer Programming 2: Seminumerical Algorithms (third edition), Reading: Addison Wesley, 1998. Zbl0895.68054MR378456
  7. [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. [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. [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. [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. [11] Hugo Volger, Some results on addition/subtraction chains. Information Processing Letters20 (1985), 155-160. Zbl0574.10052MR801983

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.