# Origin of square-and-multiply algorithm

I'm teaching an introductory course in cryptography and explained the square-and-multiply algorithm to the class.

http://en.wikipedia.org/wiki/Square-and-multiply_algorithm

Someone asked who discovered the algorithm, which I didn't know, so after a short web search that gave no answers, I thought I'd ask on MO. In particular, the above wikipedia article is not helpful, and I didn't see any MO questions that address the issue. This seems like something that Gauss and Euler, or even Fermat, might have known, and ditto for Indian and Chinese mathematicians centuries earlier, but I'm just speculating. Specific references would be appreciated. (Sorry if this isn't really a research level question, although maybe it qualifies as historical research.)

-
The logarithmic version of square-and-multiply is essentially what is often called the Russian peasant method for multiplying integers. This was already used in ancient times by Egyptians and Babylonians. – Franz Lemmermeyer Sep 22 '12 at 12:17
@Franz: Thanks. Do you have a reference? And by "log version", do you mean double-and-add? – Joe Silverman Sep 22 '12 at 14:18

This method is indeed over 2000 years old. The history, with references, is discussed by Donald Knuth in Seminumerical Algorithms, volume 2 of The Art of Computer Programming, page 441:

The method is quite ancient; it appeared before 200 B.C. in Pingala's Hindu classic Chandah-sutra [see B. Datta and A.N. Singh, History of Hindu Mathematics 1, 1935]; however, there seem to be no other references to this method outside of India during the next 1000 years. A clear discussion of how to compute $2^n$ efficiently for arbitrary $n$ was given by al-Uqlidisi of Damscus in 952 A.D.; see The Arithmetic of al-Uglidisi by A.S. Saidan (1975), p. 341-342, where the general ideas are illustrated for $n=51$. See also al-Biruni's Chronology of Ancient Nations (1879), p. 132-136; this eleventh-century Arabic work had great influence.

For a detailed discussion of the earliest history, see A. Kulkarni, Recursion and Combinatorial Mathematics in Chandashaastra. [Chandashaastra = Chandah-sutra]

-
Is this for square-and-multiply or double-and-add (en.wikipedia.org/wiki/Ancient_Egyptian_multiplication)? I thought that the Legendre formula $a^{(p-1)/2} \bmod p$ was originally thought impractical for lack of square-and-multiply. Note that the "mod $p$" part is essential, otherwise $a^n$ soon becomes so large that writing out $a^n$ in full becomes infeasible in any case. – Noam D. Elkies Sep 20 '12 at 19:42
this is the binary method for exponentiation, which is what is called the "square and multiply" method. – Carlo Beenakker Sep 20 '12 at 19:57
To be clear, square for even exponents, square and multiply one more for an odd exponent. Gerhard "Or Some Other Variation Thereupon" Paseman, 2012.09.20 – Gerhard Paseman Sep 20 '12 at 20:06
@Carlo: Thanks, that's just what I was looking for. – Joe Silverman Sep 21 '12 at 1:49
But is Chandah-sutra open access? – Kevin O'Bryant Sep 22 '12 at 0:13