Extending Regev's factoring algorithm to compute discrete logarithms

G.L. Miller: Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3) (1976), 300–317

1976

Earlier work this paper cites.

A.K. Lenstra, H.W. Lenstra and L. Lovász: Factoring polynomials with rational coefficients. Math. Ann. 261 (1982), 515–534

1982

Earlier work this paper cites.

C.-P. Schnorr and M. Euchner: Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Math. Program. 66(1–3) (1994), 181–199

1994

Earlier work this paper cites.

P.W. Shor: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS ’94 (1994), 124–134

1994

Earlier work this paper cites.

P.W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26(5) (1997), 1484–1509

1997

Earlier work this paper cites.

J.-P. Seifert: Using Fewer Qubits in Shor’s Factorization Algorithm via Simultaneous Diophantine Approximation. In: CT-RSA 2001. Lecture Notes in Computer Science (LNCS) 2020 (2001), 319–327

2001

Earlier work this paper cites.

D. Coppersmith: An approximate Fourier transform useful in quantum factoring. ArXiv quant-ph/0201067 (2002). (Also IBM Research Report RC 19642.)

2002

Earlier work this paper cites.

O. Regev: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6):34 (2009), 1–40

2009

Earlier work this paper cites.

M. Ekerå and J. Håstad: Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In: PQCrypto 2017. Lecture Notes in Computer Science (LNCS) 10346 (2017), 347–363

2017

Cited alongside, same era.

B.S. Kaliski, Jr.: A Quantum “Magic Box” for the Discrete Logarithm Problem. IACR ePrint 2017/745 (2017)

2017

Cited alongside, same era.

M. Ekerå: On post-processing in the quantum algorithm for computing short discrete logarithms. Des. Codes Cryptogr. 88(11) (2020), 2313–2335

2020

Cited alongside, same era.

M. Ekerå: Quantum algorithms for computing general discrete logarithms and orders with tradeoffs. J. Math. Cryptol. 15(1) (2021), 359–407

2021

Cited alongside, same era.

M. Ekerå: On completely factoring any integer efficiently in a single run of an order-finding algorithm, Quantum Inf. Proc. 20:205 (2021), 1–14

2021

M. Ekerå: Revisiting Shor’s quantum algorithm for computing general discrete logarithms. ArXiv 1905.09084v3 (2019–2023)

2023

Closest in time.

M. Ekerå: On the success probability of the quantum algorithm for the short DLP. ArXiv 2309.01754v1 (2023)

2023

Closest in time.

M. Ekerå and J. Gärtner: Simulating Regev’s quantum factoring algorithm. GitHub repository ekera/regevnum (2023)

2023

Closest in time.

M. Hhan, T. Yamakawa and A. Yun: Quantum Complexity for Discrete Logarithms and Related Problems. ArXiv 2307.03065 (2023)

2023

Closest in time.

D. Litinski: How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates. ArXiv 2306.08585v1 (2023)

2023

Closest in time.