# 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

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