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.)
 A: 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]
