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

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.

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.

@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},
     publisher = {Universit\'e Bordeaux I},
     volume = {13},
     number = {1},
     year = {2001},
     pages = {27-41},
     zbl = {1060.11082},
     mrnumber = {1838068},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2001__13_1_27_0}
}
Bosma, Wieb. Signed bits and fast exponentiation. Journal de théorie des nombres de Bordeaux, Volume 13 (2001) no. 1, pp. 27-41. http://www.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 41526 | Zbl 0043.12902

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

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

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

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

[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 1243654 | Zbl 0780.14018

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

[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 1082914 | Zbl 0724.11068

[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 1327059 | Zbl 0845.11001

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