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



Origin of square-and-multiply algorithm
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](http://arxiv.org/abs/math/0703658). [Chandashaastra = Chandah-sutra]


