On the History of the Square and Multiply Algorithm
arXiv:2606.00958v1 [math.HO] 31 May 2026
Nuh Aydin1,∗ Mohammad K. Azarian2 Ghaya Mtimet2
Omid Khormali2
1 Department of Mathematics and Statistics, Kenyon College, Gambier, OH 43022, USA
Email: [email protected] 2 Department of Mathematics, University of Evansville, Evansville, IN 47722, USA
Emails: [email protected], [email protected], [email protected]
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 Jamshı̄d al-Kāshı̄’s fifteenth-century Miftāh. al-H . isāb where the algorithm is articulated explicitly as a general method and claimed by al-Kāshı̄ as his own innovation. To contextualize this, we trace earlier instances of successive squaring in the works of al-Uqlı̄dı̄sı̄ and al-Bı̄rūnı̄, 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 Pingāla’s prosodic studies in ancient India (c. 200 BCE). Even though it was not fully developed as a general technique, Pingāla’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.
Keywords: Square-and-multiply algorithm, Binary exponentiation, History of mathematics, Al-Kāshı̄, Miftāh. al-H . isāb, Medieval Islamic mathematics, Ancient Indian mathematics, Pingāla, Cryptography
1
Introduction
The square-and-multiply algorithm is a commonly used computational technique in modern cryptography since it is a critical element for a practical implementation of several cryp∗
Corresponding author: [email protected]
1
tosystems. These include many well-known public key cryptosystems such as RSA, DiffieHellman, ElGamal, and elliptic curve protocols for classical computers. Moreover, it plays a key role in many primality testing algorithms, as well as quantum algorithms like Shor’s algorithm to factor large integers and solve the discrete logarithm problem [37]. It is also an important computational aspect of security analysis of various cryptosystems, for example in the context of side-channel attacks. Due to its prominence in cryptography and number theory (more details in Section 2), the algorithms is discussed in almost every book on cryptography and many books on number theory. See, for example, [35, p. 244], [26, p. 71], [18, p. 69-70], [41, p. 194-198]. The importance of this topic motivates us to study its history. Despite its prominence in modern mathematics, the historical origins of this algorithm are not fully known. The question of who first discovered or used this algorithm turns out to be more complicated than one might expect. A useful starting point is Knuth [23], one of the most authoritative references in computer science, who provides a brief historical sketch of the algorithm ([23, p. 461]). He attributes an early appearance of the method to Pingāla’s Chandahśastra (Rule of Metrics) before 400 AD, then Knuth credits al-Uqlı̄dı̄sı̄ of Damascus in 952 AD with giving a clear discussion of how to compute 2n efficiently for arbitrary n, and Knuth finally states that the great calculator al-Kāshı̄ explicitly described the general right-to-left binary method for exponentiation in 1427 AD ([23, p. 462]). This sketch naturally raises the question of what exactly these earlier sources contain and how they relate to each other, which is the central motivation of this work. A number of other sources, ranging from educational websites and blog posts to some academic publications [38, 19, 22, 30, 15, 14, 36, 34], also attribute the algorithm to Pingāla, who lived around the second century BCE. If true, this would mean the algorithm has a much older history than is generally recognized. Knuth already states that “this method is quite ancient” and he says it appeared in Pingāla’s Chandahśastra. We analyze the relevant evidence and primary sources to clarify the historical trajectory of the square-and-multiply algorithm. Since al-Kāshı̄ claims to have invented the algorithm in the fifteenth century, we start by looking into his work. Al-Kāshı̄ (1380–1429) presents the method quite explicitly in his comprehensive book Miftāh. al-H . isāb [4, 5, 6], which can be translated as Calculator’s Key or Key to Arithmetic (we prefer the latter translation, henceforth Miftāh.). He introduces it across two rules in the algebra treatise of Miftāh. [6], first in the context of computing the sum of a geometric series, and then in a rule devoted entirely to computing large powers efficiently. Notably, al-Kāshı̄ frames these contributions as rules he deduced himself, suggesting he viewed the method as his own contribution. This makes Miftāh. al-H . isāb one of the clearest and most explicit early treatments of the algorithm that we have found in the literature. More on al-Kāshı̄’s broader mathematical contributions and the content of Miftāh. can be found in [4, 5, 6, 7, 8, 9, 10, 11, 12, 13]. It turns out that two earlier Islamic scholars, al-Uqlı̄dı̄sı̄ (920-980) and al-Bı̄rūnı̄ (973-1048), both used techniques of successive squaring several centuries before al-Kāshı̄. Al-Uqlı̄dı̄sı̄, who was active in the tenth century [33], developed a systematic procedure for finding the 2
amount in any cell of a doubling sequence using repeated squaring. Al-Bı̄rūnı̄, in the next century [2], applied a similar chain of squarings to solve the classical chess problem, computing 264 through four successive squaring steps. Neither of them, however, presented the method as a standalone general method the way al-Kāshı̄ did. There was no explicitly named concept of “algorithm” in the fifteenth century or before, but al-Kāshı̄ called it a “rule”. It appears like before al-Kāshı̄ the technique was embedded in specific problems rather than stated as a general rule. This paper investigates these historical threads. Section 2 discusses the importance and modern applications of the algorithm. Section 3 examines al-Kāshı̄’s treatment of the algorithm in detail. Section 4 looks at the earlier relevant works of al-Uqlı̄dı̄sı̄ and al-Bı̄rūnı̄, as well as Pingāla’s work on this topic. Section 5 offers concluding remarks on what the available evidence suggests about the origins of the algorithm.
2
The Importance of the Algorithm
The algorithm known variously as square and multiply, binary exponentiation, exponentiation by squaring, repeated squaring, and double and add in the setting of elliptic curves, is a broadly applied technique in computational number theory and modern cryptography. The core idea behind all these names is actually the same. By writing the exponent in binary and performing a sequence of squarings and conditional multiplications, the number of operations needed to compute an drops from O(n) all the way down to O(log(n)). Computationally, this reduction is highly significant. Since this is a number theoretical algorithm, the size of the input is log(n), rather than n. The naive algorithm computes an by performing the sequence of computations a2 = a · a, a3 = a · a2 , . . . , an = a · an−1 . Therefore, its complexity is O(n) which is exponential time because n = 2log(n) , whereas the square-and-multiply algorithm is linear in the size of the input, hence it is an efficient algorithm. To demonstrate the difference this makes in practice, we include the outputs of actual computations from two different computer algebra systems, Maple and Magma, using the naive algorithm versus the efficient algorithm. The following examples show that while modern computer algebra systems cannot handle the computation when the command to do the computation uses the naive method, they instantly compute the result when the efficient method is called.
Figure 1: Calculation of ae mod n in Maple using the naive method.
3
Figure 2: Calculation of ae mod n in Maple using the efficient method.
Figure 3: Calculation of ae mod n in Magma using the naive method.
4
Figure 4: Calculation of ae mod n in Magma using the efficient method.
Knuth gives a thorough treatment of this algorithm in [23], and Schneier’s Applied Cryptography [35] describes it as a cornerstone of practical implementation of several public key cryptosystems. The algorithm shows up in many important areas, some of which we summarize below. One of the most important uses of the algorithm is in computing modular exponentiation ae (mod n), which is the core arithmetic operation in the RSA cryptosystem [32] and the Diffie–Hellman key exchange [17]. Without this technique, RSA encryption and decryption with 2048-bit keys would simply not be feasible in practice. The algorithm is also needed in the ElGamal cryptosystem and the Digital Signature Algorithm (DSA), both of which rely on computing large modular powers efficiently. The algorithm also plays a central role in primality testing. Both the Fermat primality test and the Miller–Rabin primality test [27, 31] need to compute an−1 (mod n) for large values of n. Without fast modular exponentiation, generating the large primes that RSA key generation requires would not be practical. It also appears as a key subroutine in the AKS deterministic primality test [1]. A modified version of the algorithm is used in elliptic curve cryptography. In the setting of elliptic curves, the group operation is point addition rather than multiplication, and a scalar multiple of a point, instead of an exponent, for a large integer, needs to be computed. The analogous technique in this setting is called double and add. To compute the scalar multiple kP of a point P for a large positive integer k, one doubles and conditionally adds according to the binary expansion of k. This is the operation at the heart of the Elliptic Curve Diffie–Hellman (ECDH) key exchange, the Elliptic Curve Digital Signature Algorithm (ECDSA), and related protocols standardized by NIST and the NSA [20]. As Li et al. note, the double-and-add method is directly inspired by the repeated square-and-multiply algo5
rithm and has long been considered a fundamental technique in this area [25]. The algorithm also shows up in a perhaps unexpected place, namely quantum computing. Modular exponentiation via repeated squaring is the computational bottleneck in Shor’s quantum polynomial-time factoring algorithm [37], where it has to be implemented using a circuit of reversible gates. This means the algorithm matters not just for the cryptographic systems in use today but also for the quantum algorithms that could threaten those systems in the future. The widespread use of the square-and-multiply algorithm has also made it an important target in security research. Kocher’s timing attack [24] showed that the difference in execution time between the squaring and multiplication steps can leak private key bits from RSA implementations. That finding led to a large body of work on constant-time variants, including the Montgomery ladder algorithm, and on implementations that resist power analysis attacks [16].
3
Al-Kāshı̄’s Work
Ghiyāth al-Dı̄n Jamshı̄d Mas’ūd al-Kāshı̄ (1380-1429 AD, usually referred to as al-Kāshı̄ and sometimes as al-Kāshanı̄) was one of the most renowned mathematicians and astronomers in Persian history, and one of the most fascinating medieval Muslim mathematicians. We will very briefly reintroduce his significant works in mathematics and astronomy. One of the most notable mathematical achievements of al-Kāshı̄ is al-Risāla al-Muh.ı̄t.ı̄yya (“The Treatise on the Circumference”), which he completed in Arabic in 1424 AD. In this treatise, he correctly estimated 2π to 9 sexagesimal digits which is equivalent to 16 decimal places of accuracy [10, 11]. The second important mathematical achievement of al-Kāshı̄ is Risāla al-Watar wa’l-Jaib (“The Treatise on the Chord and Sine”), which he finalized between 1424 and 1427 AD in Arabic. Al-Kāshı̄ applied Ptolemy’s theorem to an inscribed quadrilateral to obtain his famous cubic equation, and then he invented an ingenious and quickly converging iteration algorithm to calculate sin(1◦ ) to 16 correct decimal digits (9 correct sexagesimal places) as a root of his cubic equation. It is remarkable that al-Kāshı̄ used both geometry and algebra to approximate sin(1◦ ), to any desired accuracy. Not only was this the most creative method of approximation, but it was one of the first known approximation methods in the history of mathematics, and a substantial achievement in medieval algebra [8, 9]. The third and the most well- known mathematical work of al-Kāshı̄ written in Arabic is Meftāh. al-H . esāb (“The Calculators’ Key” or “The Key to Arithmetic”, henceforth Miftāh.). It contains some of al-Kāshı̄’s original findings, as well as his improvements on earlier works. Written primarily as a textbook, Miftāh. was used for more than five centuries, not only as a textbook, but also as an encyclopedia. It served many generations of students and professionals. It took al-Kāshı̄ more than 7 years to bring Miftāh. to fruition, on March 2, 1427 [12]. Miftāh. has been recently translated to English in full. More on al-Kāshı̄’s contributions and the content of Miftāh. can be found in [13], [4],[5], and [6].
6
Al-Kāshı̄ was also a prominent astronomer who served as the director of Samarqand observatory which was the most advanced observatory of his time. al-Kāshı̄ completed some of his best works while at Ulugh Beg’s observatory and madrasah in Samarqand (c. 1420-1429), where he was recognized as the leading mathematician and astronomer. Some mathematical discoveries of al-Kāshı̄ were in conjunction with his various works on astronomy. The best known of his works in astronomy are: (i) Sullam al-samā’ (“The Ladder of the Sky” or “The Stairway of Heaven”), completed in Arabic on March 1, 1407; (ii) Mukhtasar dar ’ilm-i hay’at (“Compendium of Science and Astronomy”), finished in Persian in 1410-1411 AD; (iii) Risāla dar sharh-i ālāt-i rasad (“Treatise on the Explanation of Observational Instruments”), concluded in Persian in January 1416; (iv) Nuzha al-hadāiq (“The Garden Excursion”), finalized in Arabic on February 10, 1416; and (v) Zı̄j-i Khāqānı̄ (“The Khāqānı̄ Astronomical Tables”) was completed in Persian 1413-1414 AD (this is a revised version of Zı̄j-i Ilkhānı̄ of Nası̄r al-Dı̄n al-Tūsı̄) [7]. The method of “square-and-multiply” appears in Miftāh. even though it is not a specifically named method. It is first mentioned in the context of computing the sum of a geometric series. The fifth treatise of Miftāh. is devoted to algebra [6], which is about a third of the entire book, the other two being on arithmetic [4], and geometry [5]. The third chapter of Treatise 5 is titled “On Some Computational Rules that are Crucial to Find Unknowns” and it contains fifty rules. In Rule 9, al-Kāshı̄ describes the square-and-multiply algorithm for the first time in Miftāh.. However, the main goal of this rule is to give a formula for the sum of a geometric series. Later, he gives Rule 16 which is specifically devoted to the algorithm. Here is the full statement of Rule 9 as translated in [6]: The Ninth Rule. On the sum of numbers resulting from doubling one or another number. This is also from what we deduced. The way to do this is that if the last number [of this sequence] is known, we subtract one from its double. The result is the sum of these numbers. If the last number is unknown, we look at how many times we duplicated. That is the rank of a multiple. That multiple is obtained from a first ratio of two. The way to obtain this [i.e., obtain the multiple] is to see if the rank can be halved [over and over] until it becomes one. We look then, to find how many times it can be halved until it gets to one, or we know the power of two with its rank. We square two again and again as many times as to get that number [i.e. as many as that rank]. That is, we multiply two by itself then the product by itself then the second product by itself and so on, as many times as to get that number. To obtain the last number, we double it [previous number] and always subtract one from it. The result is the sum of these numbers. If we initially add one to the numbers that are multiples, and if the sum [of the multiples] can be halved until it becomes one, then we use it to do the same computations as earlier, and the result is the sum of the numbers with one added to it. An Analysis of al-Kāshı̄’s Ninth Rule: As it was custom at the time, al-Kāshı̄ explains everything in prose. Algebraic symbolism was not yet introduced. Al-Khwārizmı̄ wrote his algebra book in early ninth century [3]. It was the first time in history that algebra was specifically named as a technical mathematical operation. The English word algebra is a 7
transliteration of the Arabic word al-jabr that appears in the title of this book [3]. Six centuries later, when Miftāh. was written, there was still no symbols in algebra. Al-Kāshı̄ explains that this rule is about finding the sum of a geometric series with the common ratio of 2 whose initial term is either 1 or some other number. In the subsequent explanations, he seems to be working with the case where the first term is 1. Therefore, he considers the geon X metric series 2i−1 . If we know the sum of this series, then the case when the first term is i=1
some other number a is easy to handle because
n X i=1
i−1
a2
=a
n X
2i−1 . Al-Kāshı̄ implies that
i=1
this formula is among the things he discovered or invented. This claim needs to be examined by researchers. Al-Kāshı̄ says if the last term of the sequence is known, then the sum equals twice the last term minus 1, that is, he gives the formula 1 + 2 + 22 + · · · + 2n = 2n+1 − 1 which is the correct formula. Then he considers the case where the last term in the series is not known. In this case, he finds the exponent (say n) of the last term of the series (2n ) from the number of terms. To compute the numerical value of the last term, he divides n by 2 consecutively until he obtains 1, if possible. First, he assumes that n can be divided by 2 consecutively until 1 is obtained, in say m steps. Then, he computes 2n as being the m ··· 2 successive squares 22 . After this rule, al-Kāshı̄ gives a sequence of examples. In the first example, he computes 8 X the sum 2i . As a first step, he computes 28 via the square-and-multiply method, i.e., by i=1
computing ((22 )2 )2 which requires 3 squaring operations as opposed to the direct method of computing 2, 2 · 2, 2 · 4, 2 · 8, 2 · 16, 2 · 32, 2 · 64, 2 · 128 = 256 which requires 7 multiplications. He doubles the last number, and subtracts 1 from it to get 2 · 256 − 1 = 511 8 8 X X i which is 2 . He subtracts 1 again to find 2i = 510. Next, he considers the well i=0
i=1
known chessboard problem which amounts to computing 263 . The way al-Kāshı̄ solves this problem is to first compute 264 via the square-and-multiply method, that is by computing 22 , 42 , 162 , 2562 , 655362 , 42949672962 , and 184467440737095516162 because 64 can be repeatedly halved until 1 is obtained (i.e., it is a power of 2). Then he halves the last number to obtain 263 which he finds to be 9,223,372,036,854,775,808. After this example, al-Kāshı̄ makes the following comment: As for when the number of doubles cannot be halved [over and over] to get to one, we subtract from it the largest number that can be halved until it gets to one, then the same from the remainder, and so on until nothing is left or there is one left. So, the number is decomposed into these numbers. And he gives a quick example of this case: Example. If the number is ten, we decompose it into two parts which are eight and two,
8
each of which can be halved till one. Next he considers an example where the number is broken into three parts such that each part is a power of two. In the example, the parts are 64, 32, and 4. Therefore, the number itself is n = 100, though al-Kāshı̄ does not explicitly name 100. He gives a detailed expla100 X 100 nation of how to compute 2 , then obtains 2i . In the next example, he explains how to i=0
compute
11 X
2i in which he starts with breaking up 11 as 11 = 8+2+1. Next, al-Kāshı̄ makes
i=0
the point that if the first value in the sequence is a number other than 1 and if we double n n X X i−1 each term at every step, then one can find the result using the formula a2 = a 2i−1 . i=1
i=1
Then, in rules numbered 10 to 15, al-Kāshı̄ gives the formulas below, all in words and without proofs. He stated that the rules 7, 9, 15, and 16 were his own discoveries. Here are the formulas in modern notation that al-Kāshı̄ stated in words in these six rules. Rule 10.
n+1
n X
n(n + 1)(n + 2) [(n + 1) − 1]2 X i= i(i + 1) = 3 3 i=1 i=1
Rule 11. " n+1 # " n+1 ! # X X (n + 1)(n + 2) (n + 1)(n + 2) −1 i(i + 1)(i + 2) = i i −1 = 2 2 i=1 i=1 i=1
n X
Rule 12.
n X
n
2n + 1 X n(n + 1)(2n + 1) i = i= 3 6 i=1 i=1 2
Rule 13. n X i=1
Rule 14.
3
i =
n X
!2 i
=
i=1
n(n + 1) 2
2
" P # n n n X X ( i) − 1 i=1 i4 = + i i2 5 i=1 i=1 i=1
n X
Remark.
It is intriguing that about four centuries prior to al-Kāshı̄, Ibn al-Haytham n X (c. 965 – c. 1040), known in the west as Alhazen, discussed i4 in his treatise on the i=1
Determination of the Sums of Powers of Numbers (c. 1000–1020) [12]. Rule 15.
n X i=1
ai =
a (an − 1) an − a aan − a = = + an , a−1 a−1 a−1 9
where a is any number except 1. For a =
p < 1, al-Kāshı̄ presented the following formula q
n i X p i=1
q
(q n − pn )p = . (q − p)q n
Then comes the sixteenth rule which is entirely devoted to the square and multiply method. Here is the full statement of the rule given in [6]. The Sixteenth Rule. To get a large power of a number without finding the consecutive powers between them. This is also from what we deduced. We take the power and check if it can be halved until one. If it is, we find the number of times it needs to be halved to get to one. Then, we square the first power that many times to get the final power, which is the wanted value. Then he gives two examples. In the first example, al-Kāshı̄ computes 58 . Here, 8 is a power of 2 and 1 is obtained by halving 8 three times. Therefore, he obtains the result by 3 squarings: 52 = 25, 252 = 625 and 6252 = 390625. He then explains how to apply the method if the exponent is not a power of 2. He writes: If the power cannot be halved until one, we subtract from it the largest number possible that can be halved to one, then do the same with the remainder, and so on until either nothing is left or one is left. We get numbers whose sum equals the wanted power, and each of them can be halved until one or one of them is one itself and the others can be halved until one. We put the numbers in a table as mentioned earlier in the ninth rule. We find the count of halvings required for each number to get to one, and write it next to its respective number. We write a zero next to the one. We call these counts the number-of-times. Then, we square the first power again and again as many times as the largest of the numbers of times. We write the last square next to its respective number. Similarly, we write next to each number the last square which results from squaring the first power a number of times corresponding to that number. We put the first power next to the zero. Then, we multiply these powers in the column by each others, the result is the last power that is wanted. In this case, al-Kāshı̄ explains the technique to compute an where n is not a power of 2 as follows. He breaks up n as n = n1 +n2 +· · ·+nk where the numbers n1 , n2 , . . . , nk are powers of 2 i.e., he obtains the binary (base-2) representation of n. Then, he computes bi = ani for each i, using the 16th rule. He then multiplies all bi ’s to obtain an . Next, he gives an example to illustrate how to apply this technique to compute 414 . The first step is to write 14 = 8 + 4 + 2. Then he computes 48 , 44 , and 42 using the rule, finally multiplies all of the numbers together to obtain 414 .
4
Earlier Works
As noted in the introduction, two Islamic scholars predate al-Kāshı̄ in their use of successive squaring. Al-Uqlı̄dı̄sı̄, in the tenth century, and al-Bı̄rūnı̄, in the eleventh century, both 10
employed repeated squaring to compute large powers of 2 efficiently, several centuries before al-Kāshı̄ articulated the method as a general rule. However, neither of them presented the technique as a standalone general method. Rather, in both cases the method was embedded within specific computational problems. In this section, we examine what each of these scholars did, followed by a discussion of Pingāla’s earlier work.
4.1
Al-Bı̄rūnı̄ (973–1048 CE)
In The Chronology of Ancient Nations, al-Bı̄rūnı̄ addresses the same classical chess problem, requiring the computation of 264 − 1 [2, p. 132–136]. He presents two fundamental rules [2, p. 134]. The first rule states that the square of the number of a check x of the 64 checks of the chessboard is equal to the number of that check whose distance from check x is equal to the distance of check x from the first check. As an example, al-Bı̄rūnı̄ takes the square of the number of the 5th check, i.e., 162 = 256, which is the number belonging to the 9th check, since the distance of the 9th check from the 5th equals the distance of the 5th check from the first [2, p. 134]. The second rule states that the number of a check x minus 1 is equal to the total sum of the numbers of all the preceding checks. As an example, the number of the 6th check is 32, and 32 − 1 = 31, which equals 1 + 2 + 4 + 8 + 16 [2, p. 132]. Using the first rule, al-Bı̄rūnı̄ computes 264 through a chain of successive squarings. He expresses this as [2, p. 132]: h i2 2 2 2 16 = 1616 = 264 , tracing the following chain of checks and their values: Check Number Operation 5th starting point 9th square of 5th 17th square of 9th 33rd square of 17th 65th square of 33rd
Value 16 = 24 256 = 28 65,536 = 216 4,294,967,296 = 232 18,446,744,073,709,551,616 = 264
Table 1: Al-Bı̄rūnı̄’s successive squaring chain for the chess problem [2, p. 134–135].
He then subtracts 1 to obtain the total sum of all the checks of the chessboard, arriving at 18,446,744,073,709,551,615 [2, p. 132].
4.2
Al-Uqlı̄dı̄sı̄ (c. 920–980 CE)
In The Arithmetic of al-Uqlı̄dı̄sı̄, Book IV, Chapter 32, titled “On Doubling One, Sixty-Four Times,” al-Uqlı̄dı̄sı̄ addresses the problem of computing the number in any cell of a doubling 11
sequence, as well as the total of all cells up to a given one [33, p. 337–342]. Al-Uqlı̄dı̄sı̄ begins by establishing a standard of ten cells: 1 2 4 8 16 32 64 128 256 512, to which he reduces all subsequent computations [33, p. 339]. He observes that multiplying the number in any cell by its like (i.e., squaring it) gives the number in twice the cell number less one. For example, the number on the fifth cell is 16. If you square 16, you get 256 which is the number on the ninth cell, and 2 · 5 − 1 = 9. The total of all cells up to the last is obtained by doubling the last number and deducting one, i.e., n X
2i−1 = 2n − 1.
i=1
Al-Uqlı̄dı̄sı̄’s method for finding the number in an odd-numbered cell proceeds by adding one to the cell number and halving it, then using the ten-cell standard. For the 17th cell, he states: “we add one to seventeen and take half of that, finding nine. We then multiply what is in the ninth cell by its like: 256×256 = 65,536, which is the amount in the 17th cell.” For the 51st cell, al-Uqlı̄dı̄sı̄ proceeds as follows [33, p. 341–342]: increase 51 by one and take half, which is 26; take its half, which is 13; add one and take half, which is 7; add one and take half, which leads to the fourth cell, in which we find 8. He then computes upward through successive squarings: 82 = 64 (7th cell), 642 = 4,096 (13th cell), 4,0962 = 16,777,216 (25th cell), 2 × 16,777,216 = 33,554,432 (26th cell), 33,554,4322 = 1,125,899,906,842,624 (51st cell). That is, after reaching the 25th cell, he doubles the amount to reach the 26th cell, and then squares it to reach the 51st cell, since 2 × 26 − 1 = 51. For even-numbered cells, al-Uqlı̄dı̄sı̄ states that one halves the cell number and adds one, then proceeds as in the odd case [33, p. 342]. Consider the 14th cell for example. Take half of 14, which is 7. Then, add one and take half of that, which leads to the fourth cell, in which we find 8. He then computes 82 = 64 (7th cell), 642 = 4,096 (13th cell), 2 × 4,096 = 8,192 (14th cell), that is, after reaching the 13th cell by two successive squarings, he doubles the amount to obtain the value in the 14th cell.
12
4.3
Pingāla (c. 2nd century BCE)
Pingāla is an ancient Indian scholar who is credited with writing the Chandahśutra, a treatise on Sanskrit prosody concerned with the systematic study of metrical patterns in poetry. A number of sources, ranging from educational websites and blog posts to some academic publications [38, 22, 30, 15, 14, 36, 34], attribute the square-and-multiply algorithm to Pingāla, sometimes calling it the earliest known instance of binary exponentiation. Knuth states in [23] that the binary method appeared before 400 AD in Pingāla’s Chandahśutra. Therefore, Pingāla deserves a careful examination in any discussion of the history of the square and multiply algorithm. One thing we notice is that many of the sources do not directly engage with Pingāla’s original text and appear to rely on each other rather than on independent primary source analysis. For instance, the blog posts and educational websites [30, 15, 14, 38, 22] make statements that Pingāla invented binary exponentiation without providing direct textual evidence from the Chandahśutra itself. The academic paper by Sahu [34] similarly attributes algorithmic thinking to Pingāla, but draws on secondary literature rather than primary sources. One of the scholarly treatments of Pingāla’s original work that we found is the paper by Shah [36], which systematically traces Pingāla’s algorithms through Indian mathematical literature over more than a millennium. Shah does describe a divide-and-conquer recursive algorithm in the Chandahśutra for computing powers of 2, specifically the algorithm for calculating the total number of possible metrical forms of a given length. In Pingāla’s scheme, if the number of syllables n can be halved, the result is obtained by squaring, and if not, one subtracts one and doubles. This is expressed in four cryptic sūtras and is used to compute Sn = 2n , the total count of all forms of an n-syllable meter. The algorithm is recursive and it does rest on the same underlying mathematical principle as the square-and-multiply technique. In this sense, Pingāla does use a method that is mathematically equivalent to binary exponentiation. It is interesting to note that Pingāla’s use of this technique is entirely embedded within the specific problem of counting metrical patterns in Sanskrit poetry. It is not presented as a general computational method for computing arbitrary powers of a given number. Joseph’s The Crest of the Peacock [21] discusses the Chandahśutra exclusively in the context of combinatorics and Pascal’s triangle, with no mention of a general exponentiation algorithm. A well known expert in the history of Indian mathematics is Kim Plofker. Plofker’s chapter in [28] and her book [29] describe Pingāla’s work related to binary exponentiation in the context of prosody and combinatorics . In the section titled “Mathematical Ideas in Other Disciplines” in her book, Plofker describes Pingāla’s method of using a succession of squaring and doubling operations to calculate 2n . She (rather than Pingāla himself) illustrates the algorithm via the example of computing 27 . In section 5.3 of [29], Plofker states that a later Indian scholar presents a more general version of Pingāla’s technique to compute rn . Plofker states that this scholar was a medieval (ninth century) namesake of Mahavira, the founder of Jainism (6th-5th century BCE). 13
5
Conclusion
The number theoretical algorithm known as the square-and-multiply, binary exponentiation, or repeated squaring is an important algorithm in modern computational number theory and cryptography that enables fast exponentiation of numbers of the form am mod n for large integers m and n. Tracing historical origins of this algorithm, we find an explicit description of the algorithm as a “rule” in al-Kāshı̄’s fifteenth century book Miftāh. al-H . isāb. Although al-Kāshı̄ seems to claim that he discovered the algorithm himself, scholars well before alKāshı̄ wrote about it. For example, two Islamic scholars al-Uqlı̄dı̄sı̄ and al-Bı̄rūnı̄, who predate al-Kāshı̄ by several centuries, employed successive squaring to compute large powers of 2 efficiently. Al-Uqlı̄dı̄sı̄’s treatment is presented as a general procedure, while al-Bı̄rūnı̄’s treatment is presented specifically in the context of the chess problem, tracing a fixed chain of four squarings from the 5th to the 65th check. Going further in history than Islamic scholars, there is evidence that the ancient Indian scholar Pingāla had the main idea of the square and multiply algorithm which is to use the binary representation of the exponent even though it was in the context of counting metrical patterns. Using the binary representation of the exponent is the essence of the algorithm that makes it efficient compared to the naive algorithm, which has exponential running time. There is sufficient evidence to conclude that Pingāla had the basic idea and explained it in an elementary way in the context of counting metrical patterns in the third or second century BCE. Although it was not initially stated as a general mathematical procedure, on the basis of available evidence, Pingāla may be viewed as the first person who used a procedure that we now call the square and multiply algorithm.
Acknowledgments The third and fourth authors gratefully acknowledge support from the Global Scholar Award, University of Evansville Center for Innovation and Change.
References [1] Agrawal, M., Kayal, N., and Saxena, N. PRIMES is in P. Annals of Mathematics, 160(2):781–793, 2004. [2] Al-Bı̄rūnı̄, M. ibn A. The Chronology of Ancient Nations. Translated by C. Eduard Sachau. Oriental Translation Fund of Great Britain & Ireland, W.H. Allen, London, 1879. [3] Al-Khwārizmı̄, M. ibn M. Al-Khwārizmı̄: The Beginnings of Algebra. Translated and edited by R. Rashed. Saqi Books, London, 2009. [4] Aydin, N. and Hammoudi, L. Al-Kāshı̄’s Miftāh. al-H . isāb, Volume I: Arithmetic. Birkhäuser, 2019.
14
[5] Aydin, N., Hammoudi, L., and Bakbouk, G. Al-Kāshı̄’s Miftāh. al-H . isāb, Volume II: Geometry. Birkhäuser, 2020. [6] Aydin, N., Hammoudi, L., and Bakbouk, G. Al-Kāshı̄’s Miftāh. al-H . isāb, Volume III: Algebra. Birkhäuser, 2022. [7] Azarian, M. K. An Overview of Mathematical Contributions of Ghiyāth al-Dı̄n Jamshı̄d Al-Kāshānı̄. Mathematics Interdisciplinary Research, 4:11–19, 2019. [8] Azarian, M. K. A Study of Risāla al-Watar wa’l Jaib (“The Treatise on the Chord and Sine”): Revisited. Forum Geometricorum, 18:219–222, 2018. Mathematical Reviews MR3819227; Zentralblatt MATH Zbl 1395.51026. [9] Azarian, M. K. A Study of Risāla al-Watar wa’l Jaib (“The Treatise on the Chord and Sine”). Forum Geometricorum, 15:229–242, 2015. Mathematical Reviews MR3418854; Zentralblatt MATH Zbl 1328.01015. [10] Azarian, M. K. Al-Risāla al-Muh.ı̄t.ı̄yya: A Summary. Missouri Journal of Mathematical Sciences, 22(2):64–85, 2010. Mathematical Reviews MR2675403; Zentralblatt MATH Zbl 1204.01009. [11] Azarian, M. K. Al-Kāshı̄’s Fundamental Theorem. International Journal of Pure and Applied Mathematics, 14(4):499–509, 2004. [12] Azarian, M. K. Meftāh. al-h.esāb [Miftāh. al-h.isāb]: A Summary. Missouri Journal of Mathematical Sciences, 12(2):75–95, 2000. Mathematical Reviews MR1764526; Zentralblatt MATH Zbl 1036.01002. [13] Berggren, J. L. Episodes in the Mathematics of Medieval Islam. 2nd edition. Springer, 2016. [14] Bhavya. Pingala’s Contribution in Chhandas Shastra: The Birth of Ancient Algorithms. Medium, October 2025. [https://medium.com/@bhavya.17845/the-ancientindian-secret-to-faster-calculations]. Accessed: 29 January 2026. [15] BooksFact. Pingala, Inventor of Binary Numbers in 2nd Century BCE, January 2016. https://www.booksfact.com/science/ancient-science/ pingala-inventor-of-binary-numbers-in-2nd-century-bce.html. Accessed: 29 January 2026. [16] Coron, J.-S. Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems. In Cryptographic Hardware and Embedded Systems – CHES 1999, Lecture Notes in Computer Science, vol. 1717, pp. 292–302. Springer, Berlin, 1999. [17] Diffie, W. and Hellman, M. E. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. [18] Effinger, G. F. and Mullen, G. L. Elementary Number Theory. CRC Press, Boca Raton, 2022. 15
[19] Grokipedia. Exponentiation by Squaring, 2025. https://grokipedia.com/page/ Exponentiation_by_squaring. Accessed: 29 January 2026. [20] Hankerson, D., Menezes, A., and Vanstone, S. Guide to Elliptic Curve Cryptography. Springer, New York, 2004. [21] Joseph, G. G. The Crest of the Peacock: Non-European Roots of Mathematics. 3rd edition. Princeton University Press, Princeton, NJ, 2010. [22] Kiddle Encyclopedia. Exponentiation by Squaring Facts for Kids, 2025. https://kids. kiddle.co/Exponentiation_by_squaring. Accessed: 29 January 2026. [23] Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. 3rd edition. Addison-Wesley, Reading, MA, 1997. [24] Kocher, P. C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Advances in Cryptology – CRYPTO 1996, Lecture Notes in Computer Science, vol. 1109, pp. 104–113. Springer, Berlin, 1996. [25] Li, C.-L., Li, H., Guo, X., and You, X. Parallel and Regular Algorithm of Elliptic Curve Scalar Multiplication over Binary Fields. Security and Communication Networks, vol. 2020, Article ID 4087873, 2020. https://doi.org/10.1155/2020/4087873. [26] Menezes, A. J., van Oorschot, P. C., and Vanstone, S. A. Handbook of Applied Cryptography. CRC Press, Boca Raton, 1997. https://doi.org/10.1201/9780429466335. [27] Miller, G. L. Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, 13(3):300–317, 1976. [28] Plofker, K. Mathematics in India. In: Katz, V. J. (ed.), The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook. Princeton University Press, Princeton, NJ, 2007. [29] Plofker, K. Mathematics in India: 500 BCE–1800 CE. Princeton University Press, Princeton, NJ, 2009. [30] Praveenkumar, K. Pingala Chanda Sutra. Blog post, May 2016. https:// prepyourmathblog.wordpress.com/2016/05/10/pingala-chanda-sutra/. Accessed: 29 January 2026. [31] Rabin, M. O. Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12(1):128–138, 1980. [32] Rivest, R. L., Shamir, A., and Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2):120–126, 1978. [33] Saidan, A. S. The Arithmetic of al-Uqlı̄dı̄sı̄: The Story of Hindu-Arabic Arithmetic as Told in Kitāb al-Fus.ūl fı̄ al-H . isāb al-Hindı̄. Translated and annotated by A. S. Saidan. D. Reidel Publishing, Dordrecht, 1978. 16
[34] Sahu, C. K. Mathematical Contributions of Pingāla – The Ancient Sage of Binary and Combinatorics. International Journal for Innovative Research in Multidisciplinary Field, 11(7):220–222, July 2025. ISSN: 2455-0620. [35] Schneier, B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. 2nd edition. Wiley, New York, 1996. [36] Shah, J. A History of Pin.gala’s Combinatorics. Northeastern University, Boston, Massachusetts. https://sanskrit.uohyd.ac.in/Algorithms_in_Ancient_India/ Material/Pingala.pdf. Accessed: 29 January 2026. [37] Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. [38] Simple English Wikipedia. Exponentiation by Squaring, 2023. https://simple. wikipedia.org/wiki/Exponentiation_by_squaring. Accessed: 29 January 2026. [39] Wikipedia. Exponentiation by Squaring, 2026. https://en.wikipedia.org/wiki/ Exponentiation_by_squaring. Accessed: 29 January 2026. [40] Wikipedia. Modular Exponentiation, 2026. https://en.wikipedia.org/wiki/ Modular_exponentiation. Accessed: 29 January 2026. [41] Yan, S. Y. Number Theory for Computing. 2nd edition, revised and extended. Springer, Berlin, 2002.
17