Signed bits and fast exponentiation
Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 1, pp. 27-41.

Nous donnons une analyse précise du gain obtenu en utilisant la représentation des entiers sous la forme non-adjacente, plutôt que la représentation binaire, lorsqu'il s'agit de calculer les puissances d'éléments dans un groupe dans lequel l'inversion est facile. En comptant le nombre de multiplications pour un exposant aléatoire ayant un nombre donné de bits dans son écriture binaire, nous obtenons une version précise du résultat asymptotique connu, selon lequel en moyenne, un parmi trois bits signés de la forme non-adjacente n'est pas nul. Cela montre que l'utilisation des bits signés réduit le coût de l'exponentiation d'un neuvième, par rapport à la méthode ordinaire consistant à des élévations au carré et à des multiplications répétées.

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.

@article{JTNB_2001__13_1_27_0,
     author = {Bosma, Wieb},
     title = {Signed bits and fast exponentiation},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {27--41},
     publisher = {Universit\'e Bordeaux I},
     volume = {13},
     number = {1},
     year = {2001},
     mrnumber = {1838068},
     zbl = {1060.11082},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_2001__13_1_27_0/}
}
TY  - JOUR
AU  - Bosma, Wieb
TI  - Signed bits and fast exponentiation
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2001
SP  - 27
EP  - 41
VL  - 13
IS  - 1
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_2001__13_1_27_0/
LA  - en
ID  - JTNB_2001__13_1_27_0
ER  - 
%0 Journal Article
%A Bosma, Wieb
%T Signed bits and fast exponentiation
%J Journal de théorie des nombres de Bordeaux
%D 2001
%P 27-41
%V 13
%N 1
%I Université Bordeaux I
%U http://archive.numdam.org/item/JTNB_2001__13_1_27_0/
%G en
%F JTNB_2001__13_1_27_0
Bosma, Wieb. Signed bits and fast exponentiation. Journal de théorie des nombres de Bordeaux, Tome 13 (2001) no. 1, pp. 27-41. http://archive.numdam.org/item/JTNB_2001__13_1_27_0/

[1] S. Arno, F.S. Wheeler, Signed digit representations of minimal Hamming weight. IEEE Transactions on Computers 42 (1993), 1007-1010.

[2] A.D. Booth, A signed binary multiplication technique. Quart. Journ. Mech. and Applied Math. 4 (1951), 236-240. | MR | Zbl

[3] D.M. Gordon, A survey of fast exponentiation methods. Journal of Algorithms 27 (1998), 129-146. | MR | Zbl

[4] R.L. Graham, A.C.-C. Yao, F.-F. Yao, Addition chains with multiplicative cost. Discrete Math. 23 (1978), 115-119. | MR | Zbl

[5] A.F. Horadam, Jacobsthal representation numbers. Fibonacci Quart. 34 (1996), 40-54. | MR | Zbl

[6] D.E. Knuth, The Art of Computer Programming 2: Seminumerical Algorithms (third edition), Reading: Addison Wesley, 1998. | MR | Zbl

[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. | MR | Zbl

[8] D.P. Mccarthy, Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains. Math. Comp. 46 (1976), 603-608. | MR | Zbl

[9] F. Morain, J. Olivos, Speeding up the computations on an elliptic curve using additionsubtraction chains. RAIRO Inform. Theory 24 (1990), 531-543. | Numdam | MR | Zbl

[10] N.J.A. Sloane, S. Plouffe, The encyclopedia of integer sequences. San Diego: Academic Press, 1995. http://www.research.att.com/ njas/sequences/ | MR | Zbl

[11] Hugo Volger, Some results on addition/subtraction chains. Information Processing Letters 20 (1985), 155-160. | MR | Zbl