Pith. sign in

REVIEW 3 major objections 3 minor 87 references

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

T0 review · 3 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum circuit factors n-bit integers N=P^2 Q with small Q using near-linear gates and sublinear qubits and depth

desk verdict Real algorithmic advance in compact quantum factoring circuits; the proof-of-quantumness framing rests on an honest but unproven classical-hardness assumption. read the letter →

arxiv 2412.12558 v4 pith:FK2QOTSY submitted 2024-12-17 quant-ph cs.CC

Gregory D. Kahanamoku-Meyer , Seyoon Ragavan , Vinod Vaikuntanathan , Katherine Van Kirk This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1211Y05 PACS 03.67.Lx
keywords quantumfactoringJacobisymbolsquarefreedecompositionsublinearspacedepthproofofquantumnessGausssumsperiodfinding
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that $n$-bit integers of the form $N=P^2Q$ with prime $P,Q$ and $Q<2^m$ can be factored by a quantum circuit using $\tilde{O}(n)$ gates, $\tilde{O}(m)$ qubits, and $\tilde{O}(n/m+m)$ depth. When $\log Q=\tilde{\Theta}(n^{2/3})$, both space and depth become $\tilde{O}(n^{2/3})$, sublinear in $n$; the authors state this is the first polynomial-time factoring circuit with sublinear qubit count for a class of integers believed hard for classical computers. The result matters because no known classical algorithm exploits the small size of $Q$ to beat the general number field sieve in this regime, so such integers are a promising basis for a classically verifiable proof of quantumness. The same Jacobi-symbol machinery also completely factors any integer whose prime exponents are all distinct, using only $O(\sqrt{\log N})$ calls to the squarefree-decomposition circuit.

What carries the argument

The central object is the Jacobi symbol $(a/b)$, a multiplicative character computable without factoring $b$; when $b$ is squarefree it is a primitive Dirichlet character, and for $N=P^2Q$ it collapses to $(x/Q)$ for $x$ coprime to $N$, making the symbol periodic with period $Q$. The argument is carried by two mechanisms. A Gauss-sum estimate for primitive characters gives $|G(\chi)|=\sqrt{m}$, which guarantees that after the quantum Fourier transform the superposition of periodic signals has $\Omega(1)$ amplitude on frequencies close to multiples of $1/Q$, so a single Fourier sampling run succeeds with constant probability. A new reversed long division subroutine streams over the classical bits of $N$ in blocks of size $m$, constructing a multiple $kx$ that matches $N$ in its low $n-m$ bits while storing only the leading $O(m)$ bits of $kx$; by quadratic reciprocity this reduces $(x/N)$ to a Jacobi symbol between two $m$-bit inputs with near-linear gates and sublinear space and depth.

What would settle it

A classical factoring algorithm that handles $n$-bit $N=P^2Q$ with $\log Q=\Theta(n^{2/3})$ in time $\exp(o(n^{1/3}))$ would falsify the claim that these integers are classically hard, and with it the proof-of-quantumness application; the circuit construction itself would remain valid.

Watch

Extended reading notes

Core claim

The core discovery is that factoring $N=P^2Q$ reduces to period finding on a function periodic modulo the secret $Q$: the Jacobi symbol satisfies $(x/N)=(x/Q)$ whenever $\gcd(x,N)=1$, because $(x/P)^2=1$. The paper proves a sharpened analysis of the squarefree-decomposition circuit showing that a uniform superposition over only $\mathrm{poly}(B_{\max})$ values, rather than $\mathrm{poly}(N)$, suffices to recover the squarefree part $B$ with constant success probability. It then constructs a space-efficient quantum circuit computing the Jacobi symbol $(x/N)$ for classical $N<2^n$ and superposed $x<2^m$ using $\tilde{O}(n)$ gates, $\tilde{O}(m)$ qubits, and $\tilde{O}(n/m+m)$ depth, which is the technical heart of the paper. For $N=P^2Q$ with $\log Q=\tilde{\Theta}(n^{2/3})$, this yields $\tilde{O}(n)$ gates, $\tilde{O}(n^{2/3})$ qubits, and $\tilde{O}(n^{2/3})$ depth.

Load-bearing premise

The load-bearing premise is that no classical algorithm can factor $N=P^2Q$ with $Q$ of size $n^a$ for $a\in(2/3,1)$ asymptotically faster than the best known general-purpose factoring method, the number field sieve; the paper surveys known methods but does not prove such an algorithm cannot exist.

Editorial extensions

If this is right

  • For $N=P^2Q$ with $\log Q=\tilde{\Theta}(n^{2/3})$, Corollary 4.8 gives a factoring circuit with $\tilde{O}(n)$ gates, $\tilde{O}(n^{2/3})$ qubits, and $\tilde{O}(n^{2/3})$ depth.
  • This is the first polynomial-time quantum factoring circuit whose qubit count is sublinear in $n$ for a class of integers believed classically hard, and it yields a factoring-based, non-interactive proof of quantumness with sublinear space.
  • The Jacobi-symbol circuit generalizes to computing greatest common divisors and modular inverses with the same $\tilde{O}(n)$-gate, $\tilde{O}(m)$-space, $\tilde{O}(n/m+m)$-depth profile.
  • Any integer whose prime factorization has distinct exponents can be completely factored with $O(\sqrt{\log N})$ calls to the squarefree-decomposition circuit, succeeding with probability $1-\mathrm{negl}(\log N)$.
  • The initial superposition needs only $\mathrm{poly}(B_{\max})$ values, so the quantum cost scales with the size of the squarefree part rather than with $N$ when that part is small.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper leaves implicit that the circuit theorems and the classical-hardness claim are separable: a future classical speedup for $P^2Q$ would end the proof-of-quantumness application without invalidating the circuit construction.
  • By analogy with the reversed-division subroutine, the same block-streaming idea should transfer to modular reduction and modular inversion with a large classical modulus and a small superposed operand, making the improvement a general template.
  • Theorem 3.1 in fact applies to every squarefull $N=A^2B$ with squarefree $B$, so the sublinear-resource claim covers a much larger class than the $P^2Q$ headline; the headline case is the one with a clean classical-hardness story.
  • A 2048-bit instantiation with $Q\approx 2^{161}$ would be the natural next test of whether the asymptotic savings survive concrete constant factors; the paper leaves that resource estimation to future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. This paper gives a quantum circuit for factoring integers of the form N = P^2 Q with near-linear gate count and, when log Q is polynomially smaller than log N, sublinear space and depth. The authors first refine the LPDS squarefree-decomposition algorithm so that the initial superposition only needs to range up to poly(B_max), then build a space-efficient quantum circuit for computing Jacobi symbols when the modulus N is classical and much larger than the superposition input x, and finally give a black-box reduction showing that any squarefree-decomposition algorithm completely factors integers whose prime exponents are distinct. The paper also discusses applications to classically-verifiable proofs of quantumness.

Significance. If the results are correct, Corollary 4.7 is the first polynomial-time quantum factoring circuit with sublinear qubit count for a class of integers for which no faster classical algorithm is currently known. The Jacobi-symbol algorithm in Section 4 is of independent interest and is stated with explicit, parameterized resource bounds. The proof structure is largely rigorous: Theorem 3.1 carries out a careful trace-distance and Gauss-sum analysis, Lemmas 4.2--4.4 verify the blockwise reduction underlying the Jacobi circuit, and Theorem 5.3 is a clean black-box reduction. A particular strength is that the authors are explicit about the main unproven premise: the classical hardness of N=P^2Q with small Q is supported only by a survey of known algorithms and is flagged as an open direction.

major comments (3)
  1. [Section 3, Algorithm 3.1 / Theorem 3.1] The proof of Theorem 3.1 analyzes the state after an exact QFT, but the efficiency paragraph specifies that the circuit uses Coppersmith's o(1)-approximate QFT. Since the near-linear gate count depends on using the approximate QFT (an exact QFT would cost O(ell^2) gates and break the main claim), the proof must explicitly argue that the o(1) approximation error changes the final measurement distribution by o(1) in total variation distance, so the Omega(1) success probability is preserved. The argument is standard, but it is currently omitted.
  2. [Abstract, Section 2.3, Corollary 4.8] The claims that N=P^2Q with log Q = Theta(n^{2/3}) is a 'classically-hard factoring problem' and that the circuit yields the first factoring-based proof of quantumness with sublinear space rest on an unproven, nonstandard hardness assumption. The paper's own survey concedes that there has been little classical cryptanalysis of this specific form. Please state the required assumption explicitly as a conjecture (e.g., no classical polynomial-time algorithm factors such N with non-negligible success probability), and qualify the proof-of-quantumness statements as conditional on that conjecture. The unconditional circuit-resource theorems should be separated from the application claim.
  3. [Section 4, Algorithm 4.1 / Lemma 4.4] Lemma 4.4 notes that s can be negative, but Step 4 of Algorithm 4.1 feeds s to an m-bit Jacobi-symbol subroutine that is normally specified for nonnegative inputs. The text should clarify how negative s is represented in the quantum registers and reduced modulo x' before the subroutine is invoked, or the algorithm should be modified to guarantee s >= 0. The asymptotic resource claims survive if modular reduction is included, but the current description is ambiguous on a point that is central to the construction.
minor comments (3)
  1. [Section 3, proof of Lemma 3.3] The displayed trace-distance bound has a confusing square-root/fourth-root expression. Please state the exact form of [Che24, Lemma 2.11] being used and show the chain of inequalities, since the current notation suggests sqrt(||u-v||^2/||u||^2) while the final bound is a fourth root of a ratio of squared norms.
  2. [Section 4, Theorem 4.1 / Algorithm 4.2] The algorithm requires m | n and its loop range presupposes n >= 2m. Please state how arbitrary m is handled via padding or restriction, so that the corollaries are unambiguously valid for all stated parameter ranges.
  3. [Remark 5] The recursion formula m_i = m_{i-1}/d with m_1 = n/d appears inconsistent as written: after one step m_2 would already be smaller than d when d is, say, n^{2/3}. Please correct or clarify the recurrence and the stopping condition for the claimed depth/space tradeoff.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Jacobi-symbol factoring circuit and its resource bounds are derived from external number-theoretic facts (Gauss sums, Jacobi reciprocity) and subroutine reductions, not from the target result. The only load-bearing fragility is the unproven classical-hardness premise for P^2Q, which is an assumption rather than a circular step.

full rationale

The paper's derivation chain is self-contained against external benchmarks. Theorem 3.1 reduces factoring squarefull N to a black-box Jacobi-symbol oracle, and the proof is a Shor-style period-finding analysis using Gauss sum bounds (Lemma 2.16) proved from Conrad's lecture notes and standard Jacobi-symbol properties. The main technical contribution, Theorem 4.1, constructs the Jacobi-symbol circuit by reducing (x/N) to an equal-size Jacobi computation via a reversed long-division/Montgomery-like procedure (Algorithms 4.1 and 4.2); correctness (Lemma 4.4) uses only the standard Jacobi reciprocity rules of Theorem 2.4. The efficiency claims are instantiations of external multiplication ([NZLS23]) and equal-size Jacobi ([Sch71], [TY90], [BS96], [Möl08]) subroutines. No fitted parameter is renamed as a prediction, and no quantity is defined in terms of the quantity it purports to derive. The self-citations that appear ([RV24, Lemma A.2] for uncomputing ctrl in Algorithm 4.2, and [KMY24] for optional zero-ancilla multiplication) are peripheral reversible-arithmetic building blocks with independent statements; Corollary 4.7 does not use [KMY24], and [RV24] is used for a division uncomputation, not for the factoring claim. The paper itself flags the genuinely weak point: the classical hardness of N=P^2Q with small Q is asserted on the basis of a survey, with the explicit concession in Section 2.3 that 'there has been little classical cryptanalysis for factoring integers of the specific form we consider', and in the Introduction that 'this is not a regime that was previously of much practical interest'. That is an unproven premise for the proof-of-quantumness application, and a correctness/security risk, but it is not circular: the circuit theorems (Corollary 4.7, Theorem 3.1) remain unconditional regardless of whether a faster classical algorithm exists. Accordingly, no step of the derivation reduces by construction to its own input, and the circularity score is 0.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The construction relies on standard number-theoretic facts and cited subroutine results. The only load-bearing assumption outside pure mathematics is the classical hardness of the target integer family, which the paper flags as an open direction.

free parameters (2)
  • m (Jacobi block size)
    Algorithm parameter in Section 4.1; any m >= log Q is allowed, giving a space/depth tradeoff. Not fitted to data; asymptotic claims hold for all valid m.
  • c (small-prime threshold exponent) = c > 1 (any)
    Constant in Algorithm 3.1 step 1 and Lemma 3.3; chosen to ensure trace distance is o(1). Any c > 1 works; the value does not affect the asymptotic claims.
assumptions (7)
  • standard math Standard properties of the Jacobi symbol (multiplicativity, quadratic reciprocity, (2/n), (a/n) depends on a mod n)
    Used throughout, stated as Theorem 2.4.
  • standard math Gauss sum magnitude |G(chi)| = sqrt(m) for primitive Dirichlet characters
    Theorem 2.15 from [Con], used in Lemma 2.16 and Lemma 3.4 to bound amplitudes.
  • standard math Chinese Remainder Theorem
    Used in Corollary 2.5, Lemma 2.13, and Lemma 2.16.
  • standard math [Che24, Lemma 2.11] trace distance bound between normalized states
    Used in Lemma 3.3 to replace the actual superposition with the ideal one; exact statement not reproduced in this paper.
  • standard math Bennett's reversible simulation of classical circuits preserves gate count and space up to polylog factors
    Used in Section 4.2 to make Schonhage-Jacobi reversible with ~O(t) cost.
  • standard math [RV24, Lemma A.2] allows uncomputing ctrl = floor(z/x) from z and an approximation of 1/x
    Used in Algorithm 4.2 step 3(c); lemma from a prior paper by two of the present authors.
  • standard math Parallel Schonhage-Strassen quantum multiplication with ~O(t) gates and polylog depth [NZLS23]
    Used in Corollary 4.7 to instantiate the abstract multiplier.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth." pith.science (2026). https://pith.science/paper/FK2QOTSY

@misc{pith2026241212558,
  author       = {Pith},
  title        = {Pith review of: The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FK2QOTSY}},
  note         = {Machine review of arXiv:2412.12558}
}
abstract

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor $n$-bit integers of the form $P^2 Q$ with $\log Q = \Theta(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (specifically, $\tilde{O}(\log Q)$) using $\tilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

87 extracted references · 75 canonical work pages

  1. [1]

    Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G

    Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, St...

    2019

  2. [2]

    Single- Round Proofs of Quantumness from Knowledge Assumptions , May 2024

    Petia Arabadjieva, Alexandru Gheorghiu, Victor Gitton, and Tony Metger. Single- Round Proofs of Quantumness from Knowledge Assumptions , May 2024

    2024

  3. [3]

    PRIMES is in P

    Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P . Annals of Mathematics , 160(2):781–793, September 2004

    2004

  4. [4]

    Ram Murty

    Kevser Akta s and M. Ram Murty. On the number of special numbers. Proceedings - Mathematical Sciences , 127:423--430, 2017

    2017

  5. [5]

    Miller, and Daochen Wang

    Yusuf Alnawakhtha, Atul Mantri, Carl A. Miller, and Daochen Wang. Lattice- Based Quantum Advantage from Rotated Measurements . Quantum , 8:1399, July 2024

    2024

  6. [6]

    On verifiable quantum advantage with peaked circuit sampling, April 2024

    Scott Aaronson and Yuxuan Zhang. On verifiable quantum advantage with peaked circuit sampling, April 2024

    2024

  7. [7]

    Bernstein, Jean-Fran c ois Biasse, and Michele Mosca

    Daniel J. Bernstein, Jean-Fran c ois Biasse, and Michele Mosca. A Low-Resource Quantum Factoring Algorithm . In Tanja Lange and Tsuyoshi Takagi, editors, Post- Quantum Cryptography , pages 330--346, Cham, 2017. Springer International Publishing

    2017

  8. [8]

    Efficient networks for quantum factoring

    David Beckman, Amalavoyal N Chari, Srikrishna Devabhaktuni, and John Preskill. Efficient networks for quantum factoring. Physical Review A , 54(2):1034, 1996

    work page 1996

Show all 87 references
  1. [9]

    A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

    Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device . Journal of the ACM (JACM) , August 2021

    2021

  2. [10]

    Factoring N = p\( ^ r \)q for large r

    Dan Boneh, Glenn Durfee, and Nick Howgrave - Graham. Factoring N = p\( ^ r \)q for large r. In Michael J. Wiener, editor, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings , vol...

    1999

  3. [11]

    Circuit for Shor's algorithm using 2n+3 qubits

    St \' e phane Beauregard. Circuit for Shor's algorithm using 2n+3 qubits. Quantum Inf. Comput. , 3(2):175--185, 2003

    2003

  4. [12]

    C. H. Bennett. Logical Reversibility of Computation . IBM Journal of Research and Development , 17(6):525--532, November 1973. Conference Name: IBM Journal of Research and Development

    1973

  5. [13]

    Charles H. Bennett. Time/ Space Trade - Offs for Reversible Computation . SIAM Journal on Computing , 18(4):766--776, August 1989. Publisher: Society for Industrial and Applied Mathematics

    1989

  6. [14]

    Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta

    Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta. Post-quantum RSA . In Tanja Lange and Tsuyoshi Takagi, editors, Post- Quantum Cryptography , pages 311--329, Cham, 2017. Springer International Publishing

    2017

  7. [15]

    Simpler Proofs of Quantumness

    Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness . In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation , Communication and Cryptography ( TQC 2020) , volume 158 of Leibniz International Proceeding...

    2020

  8. [16]

    Buchmann and Hendrik W

    Johannes A. Buchmann and Hendrik W. Lenstra Jr . Approximating rings of integers in number fields. Journal Theorie de Nombres Bordeaux , 6:221--260, 1994

    1994

  9. [17]

    Dan Boneh and Richard J. Lipton. Algorithms for black-box fields and their application to cryptography (extended abstract). In Neal Koblitz, editor, Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-...

    1996

  10. [18]

    J. P. Buhler, H. W. Lenstra, and Carl Pomerance. Factoring integers with the number field sieve. In Arjen K. Lenstra and Hendrik W. Lenstra, editors, The development of the number field sieve , pages 50--94, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg

    1993

  11. [19]

    Bach and J.O

    E. Bach and J.O. Shallit. Algorithmic Number Theory: Efficient algorithms . Number v. 1 in Algorithmic Number Theory. MIT Press, 1996

    1996

  12. [20]

    Sutherland

    Gaetan Bisson and Andrew V. Sutherland. Computing the endomorphism ring of an ordinary elliptic curve over a finite field. Journal of Number Theory , 131(5):815--831, 2011. Elliptic Curve Cryptography

    2011

  13. [21]

    Quantum algorithms revisited

    Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited . Proc. Roy. Soc. Lond. A , 454:339, 1998

    1998

  14. [22]

    Factoring n=p \^ rq \^ s for large r and s

    Jean - S \' e bastien Coron, Jean - Charles Faug \` e re, Gu \' e na \" e l Renault, and Rina Zeitoun. Factoring n=p \^ rq \^ s for large r and s. In Kazue Sako, editor, Topics in Cryptology - CT-RSA 2016 - The Cryptographers' Track at the RSA Conference 2016, San Francisco, C...

  15. [23]

    Reducing the Number of Qubits in Quantum Factoring , 2024

    Cl \'e mence Chevignard, Pierre-Alain Fouque, and Andr \'e Schrottenloher. Reducing the Number of Qubits in Quantum Factoring , 2024

    2024

  16. [24]

    The random oracle methodology, revisited

    Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. Journal of the ACM , 51(4):557--594, July 2004

    2004

  17. [25]

    Quantum algorithms for lattice problems

    Yilei Chen. Quantum algorithms for lattice problems. IACR Cryptol. ePrint Arch. , page 555, 2024

    2024

  18. [26]

    Guilhem Castagnos, Antoine Joux, Fabien Laguillaumie, and Phong Q. Nguyen. Factoring pq\( ^ 2 \) with quadratic forms: Nice cryptanalyses. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptol...

    2009

  19. [27]

    On the security of cryptosystems with quadratic decryption: The nicest cryptanalysis

    Guilhem Castagnos and Fabien Laguillaumie. On the security of cryptosystems with quadratic decryption: The nicest cryptanalysis. In Antoine Joux, editor, Advances in Cryptology - EUROCRYPT 2009, 28th Annual International Conference on the Theory and Applications of Cryptograph...

    2009

  20. [28]

    G auss and J acobi sums on finite fields and Z /m Z

    Keith Conrad. G auss and J acobi sums on finite fields and Z /m Z . http://kconrad.math.uconn.edu/blurbs/gradnumthy/Gauss-Jacobi-sums.pdf

  21. [29]

    An approximate Fourier transform useful in quantum factoring

    Don Coppersmith. An approximate Fourier transform useful in quantum factoring. arXiv preprint quant-ph/0201067 , 2002

    2002 arXiv

  22. [30]

    Fast parallel circuits for the quantum Fourier transform

    Richard Cleve and John Watrous. Fast parallel circuits for the quantum Fourier transform. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA , pages 526--536. IEEE Computer Society, 2000

    2000

  23. [31]

    Henry Corrigan - Gibbs and David J. Wu. The one-wayness of jacobi signatures. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part V ...

    2024

  24. [32]

    Draper, Samuel A

    Thomas G. Draper, Samuel A. Kutin, Eric M. Rains, and Krysta M. Svore. A logarithmic-depth quantum carry-lookahead adder. Quantum Information & Computation , 6(4):351--369, July 2006

    2006

  25. [33]

    Extending R egev's factoring algorithm to compute discrete logarithms

    Martin Eker and Joel G \"a rtner. Extending R egev's factoring algorithm to compute discrete logarithms. In Markku-Juhani Saarinen and Daniel Smith-Tone, editors, Post-Quantum Cryptography , pages 211--242, Cham, 2024. Springer Nature Switzerland

    2024

  26. [34]

    A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography

    Martin Eker and Joel G \" a rtner. A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography. CoRR , abs/2405.14381, 2024

    2024 arXiv

  27. [35]

    Quantum algorithms for computing short discrete logarithms and factoring RSA integers

    Martin Eker and Johan H stad. Quantum algorithms for computing short discrete logarithms and factoring RSA integers. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, ...

    2017

  28. [36]

    How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

    Craig Gidney and Martin Eker . How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum , 5:433, 2021

  29. [37]

    Factoring with n+2 clean qubits and n-1 dirty qubits

    Craig Gidney. Factoring with n+2 clean qubits and n-1 dirty qubits. arXiv preprint arXiv:1706.07884 , 2017

    2017 arXiv

  30. [38]

    Asymptotically efficient quantum Karatsuba multiplication

    Craig Gidney. Asymptotically efficient quantum Karatsuba multiplication. arXiv preprint arXiv:1904.07356 , 2019

    1904 arXiv

  31. [39]

    Creating superpositions that correspond to efficiently integrable probability distributions, 2002

    Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002

    2002

  32. [40]

    Smooth numbers: Computational number theory and beyond

    Andrew Granville. Smooth numbers: Computational number theory and beyond. Math. Sci. Res. Inst. Publ. , 44, 01 2000

    2000

  33. [41]

    An improved quantum Fourier transform algorithm and applications

    Lisa Hales and Sean Hallgren. An improved quantum Fourier transform algorithm and applications. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA , pages 515--525. IEEE Computer Society, 2000

    2000

  34. [42]

    A deterministic algorithm for finding r-power divisors

    David Harvey and Markus Hittmeir. A deterministic algorithm for finding r-power divisors. Research in Number Theory , 8(4), October 2022

    2022

  35. [43]

    Improved Quantum Circuits for Elliptic Curve Discrete Logarithms

    Thomas H \"a ner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken. Improved Quantum Circuits for Elliptic Curve Discrete Logarithms . In Jintai Ding and Jean-Pierre Tillich, editors, Post- Quantum Cryptography , Lecture Notes in Computer Science , pages 42...

    2020

  36. [44]

    Thomas H \" a ner, Martin Roetteler, and Krysta M. Svore. Factoring using 2n+2 qubits with Toffoli based modular multiplication. Quantum Inf. Comput. , 17(7 & 8):673--684, 2017

    2017

  37. [45]

    Integer multiplication in time O (n n)

    David Harvey and Joris van der Hoeven. Integer multiplication in time O (n n) . Annals of Mathematics , 193(2), March 2021

    2021

  38. [46]

    G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers . Oxford, fourth edition, 1975

    1975

  39. [47]

    Kahanamoku - Meyer, Soonwon Choi, Umesh V

    Gregory D. Kahanamoku - Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao. Classically-verifiable quantum advantage from a computational B ell test. CoRR , abs/2104.00687, 2021

    2021 arXiv

  40. [48]

    Quantum Advantage from Any Non-local Game

    Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum Advantage from Any Non-local Game . In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023, pages 1617--1628, New York, NY, USA, June 2023. Association for Computing Machinery

    2023

  41. [49]

    Neal Koblitz and Alfred J. Menezes. The random oracle model: A twenty-year retrospective. Designs, Codes and Cryptography , 77(2):587--610, December 2015

    2015

  42. [50]

    Kahanamoku-Meyer and Norman Y

    Gregory D. Kahanamoku-Meyer and Norman Y. Yao. Fast quantum integer multiplication with zero ancillas, 2024

    2024

  43. [51]

    The Art of Computer Programming, Volume II : Seminumerical Algorithms , 3rd Edition

    Donald Ervin Knuth. The Art of Computer Programming, Volume II : Seminumerical Algorithms , 3rd Edition . Addison-Wesley, 1998

    1998

  44. [52]

    H. W. Lenstra. Factoring integers with elliptic curves. Annals of Mathematics , 126(3):649--673, 1987

    1987

  45. [53]

    Lenstra, Hendrik W

    Arjen K. Lenstra, Hendrik W. Lenstra Jr. , Mark S. Manasse, and John M. Pollard. The number field sieve. In Harriet Ortiz, editor, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA , pages 564--572. ACM , 1990

    1990

  46. [54]

    An efficient exact quantum algorithm for the integer square-free decomposition problem

    Jun Li, Xinhua Peng, Jiangfeng Du, and Dieter Suter. An efficient exact quantum algorithm for the integer square-free decomposition problem. Scientific Reports , 2, 2012

    2012

  47. [55]

    Levine and Alan T

    Robert Y. Levine and Alan T. Sherman. A Note on Bennett ’s Time - Space Tradeoff for Reversible Computation . SIAM Journal on Computing , 19(4):673--677, August 1990. Publisher: Society for Industrial and Applied Mathematics

    1990

  48. [56]

    Using LLL -reduction for solving RSA and factorization problems

    Alexander May. Using LLL -reduction for solving RSA and factorization problems. In Phong Q. Nguyen and Brigitte Vall \' e e, editors, The LLL Algorithm - Survey and Applications , Information Security and Cryptography, pages 315--348. Springer, 2010

    2010

  49. [57]

    Verschoor

    Michele Mosca, Joao Marcos Vensi Basso, and Sebastian R. Verschoor. On speeding up factoring with quantum SAT solvers. Scientific Reports , 10(1):15022, September 2020

    2020

  50. [58]

    Carl A. Miller. Hidden- State Proofs of Quantumness , October 2024

    2024

  51. [59]

    o ller. On S ch \

    Niels M \"o ller. On S ch \"o nhage's algorithm and subquadratic integer gcd computation. Math. Comput. , 77:589--607, 2008

    2008

  52. [60]

    Montgomery

    Peter L. Montgomery. Modular multiplication without trial division. Mathematics of Computation , 44(170):519–521, 1985

    1985

  53. [61]

    Fast square-free decomposition of integers using class groups

    Erik Mulder. Fast square-free decomposition of integers using class groups. 2024

    2024

  54. [62]

    Proofs of quantumness from trapdoor permutations

    Tomoyuki Morimae and Takashi Yamakawa. Proofs of quantumness from trapdoor permutations. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference ( ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (Lipics) , pages 87:...

    2023

  55. [63]

    Quantum Circuit Design for Integer Multiplication Based on Sch \"o nhage -- Strassen Algorithm

    Junhong Nie, Qinlin Zhu, Meng Li, and Xiaoming Sun. Quantum Circuit Design for Integer Multiplication Based on Sch \"o nhage -- Strassen Algorithm . IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 42(12):4791--4802, December 2023

    2023

  56. [64]

    T. Okamoto. A fast signature scheme based on congruential polynomial operations. IEEE Transactions on Information Theory , 36(1):47--53, 1990

    1990

  57. [65]

    A new public-key cryptosystem as secure as factoring

    Tatsuaki Okamoto and Shigenori Uchiyama. A new public-key cryptosystem as secure as factoring. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, ...

    1998

  58. [66]

    Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM , 26(2):361--381, 1979

    1979

  59. [67]

    Faster factoring of integers of a special form

    Ren \'e Peralta and Eiji Okamoto. Faster factoring of integers of a special form. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , 79:489--493, 1996

    1996

  60. [68]

    J. M. Pollard. Factoring with cubic integers. In Arjen K. Lenstra and Hendrik W. Lenstra, editors, The development of the number field sieve , pages 4--10, Berlin, Heidelberg, 1993. Springer Berlin Heidelberg

    1993

  61. [69]

    A new public-key cryptosystem over a quadratic order with quadratic decryption time

    Sachar Paulus and Tsuyoshi Takagi. A new public-key cryptosystem over a quadratic order with quadratic decryption time. J. Cryptol. , 13(2):263--272, 2000

    2000

  62. [70]

    Shor's discrete logarithm quantum algorithm for elliptic curves

    John Proos and Christof Zalka. Shor's discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. , 3(4):317--344, 2003

    2003

  63. [71]

    On lattices, learning with errors, random linear codes, and cryptography

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

    2009

  64. [72]

    An efficient quantum factoring algorithm

    Oded Regev. An efficient quantum factoring algorithm. J. ACM , 72(1), January 2025

    2025

  65. [73]

    Quantum resource estimates for computing elliptic curve discrete logarithms

    Martin Roetteler, Michael Naehrig, Krysta M Svore, and Kristin Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. In Advances in Cryptology--ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Informa...

    2017

  66. [74]

    Space-efficient and noise-robust quantum factoring

    Seyoon Ragavan and Vinod Vaikuntanathan. Space-efficient and noise-robust quantum factoring. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proce...

    2024

  67. [75]

    Sch \"o nhage

    A. Sch \"o nhage. Schnelle B erechnung von K ettenbruchentwicklungen. Acta Informatica , 1(2):139–144, 1971

    1971

  68. [76]

    John M. Schanck. Multi-power post-quantum RSA . IACR Cryptol. ePrint Arch. , page 325, 2018

    2018

  69. [77]

    Using fewer qubits in Shor ’s factorization algorithm via simultaneous Diophantine approximation

    Jean-Pierre Seifert. Using fewer qubits in Shor ’s factorization algorithm via simultaneous Diophantine approximation. In Cryptographers’ Track at the RSA Conference , pages 319--327. Springer, 2001

    2001

  70. [78]

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

    1997

  71. [79]

    Fast multiplication of large numbers

    Arnold Sch \"o nhage and Volker Strassen. Fast multiplication of large numbers. Computing , 7:281--292, 1971

    1971

  72. [80]

    A new R abin-type trapdoor permutation equivalent to factoring

    Katja Schmidt-Samoa. A new R abin-type trapdoor permutation equivalent to factoring. Electronic Notes in Theoretical Computer Science , 157(3):79--94, 2006. Proceedings of the First International Workshop on Security and Trust Management (STM 2005)

    2006

  73. [81]

    Fast RSA -type cryptosystem modulo p\( ^ k \)q

    Tsuyoshi Takagi. Fast RSA -type cryptosystem modulo p\( ^ k \)q. In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO '98, 18th Annual International Cryptology Conference, Santa Barbara, California, USA, August 23-27, 1998, Proceedings , volume 1462 of Lecture Notes in Co...

    1998

  74. [82]

    A quantum circuit for Shor's factoring algorithm using 2n+2 qubits

    Yasuhiro Takahashi and Noboru Kunihiro. A quantum circuit for Shor's factoring algorithm using 2n+2 qubits. Quantum Information & Computation , 6(2):184--192, 2006

    2006

  75. [83]

    A uni ed approach to hgcd algorithms for polynomials and integers, 1990

    Klaus Thull and Chee K Yap. A uni ed approach to hgcd algorithms for polynomials and integers, 1990

    1990

  76. [84]

    Quantum networks for elementary arithmetic operations

    Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum networks for elementary arithmetic operations. Physical Review A , 54(1):147, 1996

    1996

  77. [85]

    David Y.Y. Yun. On square-free decomposition algorithms. In Proceedings of the Third ACM Symposium on Symbolic and Algebraic Computation , SYMSAC '76, page 26–35, New York, NY, USA, 1976. Association for Computing Machinery

    1976

  78. [86]

    Verifiable Quantum Advantage without Structure

    Takashi Yamakawa and Mark Zhandry. Verifiable Quantum Advantage without Structure . In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 69--74, October 2022

    2022

  79. [87]

    Shor's algorithm with fewer (pure) qubits, 2006

    Christof Zalka. Shor's algorithm with fewer (pure) qubits, 2006

    2006

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.