On the History of the Square and Multiply Algorithm

• URL: http://arxiv.org/abs/2606.00958v2
• Date: Sat, 06 Jun 2026 02:20:00 GMT
• Title: On the History of the Square and Multiply Algorithm
• Abstract summary: 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.<n>This paper critically examines the origins and formalization of the algorithm through primary source analysis.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Randomized and quantum approximate matrix multiplication [0.718791111462057]
  A long line of literature considers randomized algorithms, which return an approximate solution in faster time.<n>We first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (99), and based on sketching by Sarl'os (06) and Drineas-Kannan-Mahoney (06)<n>We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches.
  arXiv  Detail & Related papers  (2025-10-09T17:44:03Z)
• Basic interactive algorithms: Preview [0.0]
  The modern notion of algorithm was elucidated in the 1930s--1950s.<n>The axiomatization was used to show that for every basic algorithm there is a behaviorally equivalent abstract state machine.
  arXiv  Detail & Related papers  (2025-08-07T19:13:47Z)
• The Evolution of Cryptography through Number Theory [55.2480439325792]
  cryptography began around 100 years ago, its roots trace back to ancient civilizations like Mesopotamia and Egypt.<n>This paper explores the link between early information hiding techniques and modern cryptographic algorithms like RSA.
  arXiv  Detail & Related papers  (2024-11-11T16:27:57Z)
• Post-Quantum Security: Origin, Fundamentals, and Adoption [0.29465623430708915]
  We first describe the relation between discrete logarithms and two well-known asymmetric security schemes, RSA and Elliptic Curve Cryptography. Next, we present the foundations of lattice-based cryptography which is the bases of schemes that are considered to be safe against attacks by quantum algorithms. Finally, we describe two such quantum-safe algorithms (Kyber and Dilithium) in more detail.
  arXiv  Detail & Related papers  (2024-05-20T09:05:56Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  We study the ordinal case, i.e., the case in which a total order is defined on the set of n>2 classes. We propose a novel class of regularized OQ algorithms, which outperforms existing algorithms in our experiments.
  arXiv  Detail & Related papers  (2023-10-13T16:04:06Z)
• A Generalisation of the Phase Kick-Back [0.0]
  We present a generalisation of the Phase Kick-Back technique, which is central to some of the classical algorithms in quantum computing. We will begin by recalling the Phase Kick-Back technique to then introduce the new generalised version and analyse it. We will present a generalised version of the Bernstein-Vazirani problem and solve it using this technique to better understand its inner workings.
  arXiv  Detail & Related papers  (2022-07-06T10:53:02Z)
• Basic Quantum Algorithms [0.0]
  Quantum computing is evolving so rapidly that it forces us to revisit, rewrite, and update the foundations of the theory.<n>Basic Quantum Algorithms revisits the earliest quantum algorithms.
  arXiv  Detail & Related papers  (2022-01-25T19:00:10Z)
• Deep Algorithm Unrolling for Biomedical Imaging [99.73317152134028]
  In this chapter, we review biomedical applications and breakthroughs via leveraging algorithm unrolling. We trace the origin of algorithm unrolling and provide a comprehensive tutorial on how to unroll iterative algorithms into deep networks. We conclude the chapter by discussing open challenges, and suggesting future research directions.
  arXiv  Detail & Related papers  (2021-08-15T01:06:26Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.