9
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Franz Lemmermeyer
    Commented Sep 22, 2012 at 12:17
  • $\begingroup$ @Franz: Thanks. Do you have a reference? And by "log version", do you mean double-and-add? $\endgroup$
    – Joe Silverman
    Commented Sep 22, 2012 at 14:18

1 Answer 1

Reset to default
12
$\begingroup$

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]

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Noam D. Elkies
    Commented Sep 20, 2012 at 19:42
  • $\begingroup$ this is the binary method for exponentiation, which is what is called the "square and multiply" method. $\endgroup$
    – Carlo Beenakker
    Commented Sep 20, 2012 at 19:57
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Sep 20, 2012 at 20:06
  • $\begingroup$ @Carlo: Thanks, that's just what I was looking for. $\endgroup$
    – Joe Silverman
    Commented Sep 21, 2012 at 1:49
  • 1
    $\begingroup$ But is Chandah-sutra open access? $\endgroup$
    – Kevin O'Bryant
    Commented Sep 22, 2012 at 0:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .