Fetching the paper…
Reading the bibliography…
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance.
Multiplication of many-digital numbers by automatic computers
Anatolii Alekseevich Karatsuba and Yu P Ofman · 1962
Earlier work this paper cites.
The complexity of a scheme of functional elements simulating the multiplication of integers
Andrei L Toom · 1963
Earlier work this paper cites.
On the minimum computation time of functions
Stephen A. Cook and Stål O. Aanderaa · 1969
Earlier work this paper cites.
Schnelle Berechnung von Kettenbruchentwicklungen
A. Schönhage · 1971
Earlier work this paper cites.
Fast multiplication of large numbers
Arnold Schönhage and Volker Strassen · 1971
Earlier work this paper cites.
Representations of natural numbers by a sum of Fibonacci numbers and Lucas numbers
Édouard Zeckendorf · 1972
Earlier work this paper cites.
Logical Reversibility of Computation
C. H. Bennett · 1973
Earlier work this paper cites.
Factoring polynomials with rational coefficients
Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász · 1982
Earlier work this paper cites.
Time/Space Trade-Offs for Reversible Computation
Charles H. Bennett · 1989
Earlier work this paper cites.
A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Robert Y. Levine and Alan T. Sherman · 1990
Earlier work this paper cites.
A unified approach to HGCD algorithms for polynomials and integers, 1990
Klaus Thull and Chee K Yap · 1990
Earlier work this paper cites.
Algorithms for quantum computation: Discrete logarithms and factoring
Peter W. Shor · 1994
Earlier work this paper cites.
The probability of generating some common families of finite groups
Vincenzo Acciaro · 1996
Earlier work this paper cites.
Efficient networks for quantum factoring
David Beckman, Amalavoyal N Chari, Srikrishna Devabhaktuni, and John Preskill · 1996
Earlier work this paper cites.
Quantum networks for elementary arithmetic operations
Vlatko Vedral, Adriano Barenco, and Artur Ekert · 1996
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1997
Earlier work this paper cites.
Fast parallel circuits for the quantum fourier transform
Richard Cleve and John Watrous · 2000
Earlier work this paper cites.
Addition on a quantum computer
Thomas G Draper · 2000
Cited alongside, same era.
Using fewer qubits in Shor’s factorization algorithm via simultaneous Diophantine approximation
Jean-Pierre Seifert · 2001
Cited alongside, same era.
An approximate Fourier transform useful in quantum factoring
Don Coppersmith · 2002
Cited alongside, same era.
Creating superpositions that correspond to efficiently integrable probability distributions, 2002
Lov Grover and Terry Rudolph · 2002
Cited alongside, same era.
The expected number of random elements to generate a finite abelian group
Carl Pomerance · 2002
Cited alongside, same era.
Circuit for Shor’s algorithm using 2n+3 qubits
Stéphane Beauregard · 2003
Cited alongside, same era.
Factoring using 2 n + 2 2n+2 qubits with Toffoli based modular multiplication
Thomas Häner, Martin Roetteler, and Krysta M. Svore · 2017
Later among the works it cites.
A quantum “magic box” for the discrete logarithm problem
Burton S. Kaliski Jr · 2017
Later among the works it cites.
Targeted Fibonacci exponentiation
Burton S. Kaliski Jr · 2017
Later among the works it cites.
Quantum resource estimates for computing elliptic curve discrete logarithms
Martin Roetteler, Michael Naehrig, Krysta M Svore, and Kristin Lauter · 2017
Later among the works it cites.
High performance quantum modular multipliers
Rich Rines and Isaac Chuang · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Shor’s discrete logarithm quantum algorithm for elliptic curves
John Proos and Christof Zalka · 2003
Cited alongside, same era.
A quantum circuit for Shor’s factoring algorithm using 2n+ 2 qubits
Yasuhiro Takahashi and Noboru Kunihiro · 2006
Cited alongside, same era.
Shor’s algorithm with fewer (pure) qubits, 2006
Christof Zalka · 2006
Cited alongside, same era.
Comparison of simple power analysis attack resistant algorithms for an elliptic curve cryptosystem
Andrew Byrne, Nicolas Meloni, Arnaud Tisserand, Emanuel M. Popovici, and William Peter Marnane · 2007
Cited alongside, same era.
New point addition formulae for ECC applications
Nicolas Meloni · 2007
Cited alongside, same era.
Should one always use repeated squaring for modular exponentiation?
Shmuel T. Klein · 2008
Cited alongside, same era.
Earl Campbell, Ankur Khurana, and Ashley Montanaro · 2019
Later among the works it cites.
Asymptotically efficient quantum Karatsuba multiplication
Craig Gidney · 2019
Later among the works it cites.
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Craig Gidney and Martin Ekerå · 2021
Later among the works it cites.
Integer multiplication in time O ( n log n ) {O}(n\log n)
David Harvey and Joris van der Hoeven · 2021
Later among the works it cites.
Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li · 2022
Later among the works it cites.
Shor’s algorithm does not factor large integers in the presence of noise
Jin-Yi Cai · 2023
Closest in time.
Comment on Scott Aaronson’s blog, 2023
Craig Gidney · 2023
Closest in time.
Extending Regev’s factoring algorithm to compute discrete logarithms
Martin Ekerå and Joel Gärtner · 2024
Closest in time.
Fast quantum integer multiplication with zero ancillas, 2024
Gregory D. Kahanamoku-Meyer and Norman Y. Yao · 2024
Closest in time.
Unconditional correctness of recent quantum algorithms for factoring and computing discrete logarithms, 2024
Cédric Pilatte · 2024
Closest in time.
Regev factoring beyond Fibonacci: Optimizing prefactors
Seyoon Ragavan · 2024
Closest in time.
An efficient quantum factoring algorithm
Oded Regev · 2025
Closest in time.