Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the historical origins of the square-and-multiply algorithm, a crucial method for fast exponentiation in cryptography, by analyzing primary sources. It identifies Jamshid al-Kashi's fifteenth-century work, Miftah al-Hisab, as the first formal articulation of the algorithm, while also tracing earlier applications of successive squaring by al-Uqlidisi and al-Biruni. The research highlights that the conceptual groundwork for the algorithm can be traced back to Pingala's ancient Indian studies, revealing a rich intellectual lineage that informs its modern use.
The square-and-multiply algorithm's roots extend back to ancient India, challenging the narrative of its invention in the Islamic Golden Age.
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.