On the History of the Square and Multiply Algorithm
2026-05-31 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors studied the history of the square-and-multiply algorithm, a fast way to do repeated multiplication used in cryptography. They found that Jamshid al-Kashi in the 15th century clearly described it as a general method and claimed it as his own. Earlier, al-Uqlidisi and al-Biruni used parts of the idea for specific tasks but did not make it a general technique. Even earlier, around 200 BCE, Pingala’s work in ancient India hinted at the basic idea by using binary numbers. The paper shows how this important algorithm developed over time through these different contributions.
Square-and-Multiply AlgorithmBinary ExponentiationJamshid al-Kashial-Uqlidisial-BiruniPingalaBinary RepresentationRepeated SquaringCryptographyComputational Number Theory
Authors
Nuh Aydin, Mohammad K. Azarian, Omid Khormali, Ghaya Mtimet
Abstract
The square-and-multiply algorithm, also known as binary exponentiation or repeated squaring, is a technique for fast exponentiation commonly used in modern cryptography and computational number theory. Despite its prominence, the historical origins of the algorithm are not known with certainty. This paper critically examines the origins and formalization of the algorithm through primary source analysis. We focus on Jamshid al-Kashi's fifteenth-century Miftah al-Hisab where the algorithm is articulated explicitly as a general method and claimed by al-Kashi as his own innovation. To contextualize this, we trace earlier instances of successive squaring in the works of al-Uqlidisi and al-Biruni, who applied these techniques for specific calculations, but did not formalize them into a general procedure. The earliest known work on this method of computation is found in Pingala's prosodic studies in ancient India (c. 200 BCE). Even though it was not fully developed as a general technique, Pingala's work seems to contain the conceptual foundation of the algorithm which is to employ the binary representation of a positive integer. By mapping this intellectual progression, the paper illustrates the historical background of an algorithm that is prominent in modern computation.