Pith. sign in

REVIEW 3 major objections 4 minor 21 references

Quantum Algorithms for Modular Factorials

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

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

Pith's one-line read This paper claims a bounded-error quantum algorithm computes n! mod p in ~O(q^c + sqrt(p/q)) when q divides p−1, breaking the exponent-1/2 barrier for modular factorials by reconstructing Jacobi sums in compact algebraic form without expand

desk verdict Real sub-square-root algorithm under a divisor promise, but the speedup rests on Biasse–Song black boxes and a constant c the paper never makes explicit. read the letter →

arxiv 2607.29453 v1 pith:LADN3ZC5 submitted 2026-07-31 quant-ph cs.CC

Yann Tal This is my paper · ORCID
classification quant-phcs.CC MSC 68Q1281P6811T24
keywords quantumalgorithmmodularfactorialsub-square-roottimeJacobisumscompactrepresentationS-unitgroupsprincipalidealproblemp-adiccongruence
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 tries to show that modular factorials n! mod p and n! mod p^2 can be computed by a quantum computer in expected time ~O(q^c + sqrt(p/q)), where q is any promised divisor of p−1 and c is an absolute constant. Because the two terms balance at q ≈ p^{1/(2c+1)}, the running time is p^{c/(2c+1)}, an exponent strictly below 1/2, breaking the square-root barrier that limits classical baby-step/giant-step methods. The key is not to multiply the n factors individually, but to relate (aK)! to K! and a Jacobi sum attached to a character of order q, then reconstruct that Jacobi sum exactly in a compact form that can be reduced modulo p or p^2. At n = p−1 modulo p^2, the method also computes the quotient ((p−1)!+1)/p mod p, which detects primes whose factorial is congruent to −1 modulo p^2. If the central claim is right, a single-input worst-case quantum algorithm can compute modular factorials sub-square-root for a positive proportion of primes.

What carries the argument

The carrying object is the a-fold Jacobi sum J_a(χ), an algebraic integer in the cyclotomic field of degree φ(q). Its magnitude and prime-ideal factorization are known in advance, and a p-adic Jacobi-multinomial congruence expresses (aK)! mod p as (−1)^{a−1} ρ_p(J_a(χ)) (K!)^a, where K = (p−1)/q. The load-bearing device is the compact representation: a symbolic power product of field elements with polynomial description length that stands for an algebraic number of potentially exponential height. The proof chain computes the ideal of J_a(χ), converts it to a generator via a principal-ideal routine, adjusts that generator by units so it differs from J_a(χ) only by a root of unity, identifies

What would settle it

Run the exact Jacobi-sum reconstruction for a family of pairs (p,q) with q growing, e.g., q ≈ p^{1/3}, and inspect the empirical gate count of the principal-ideal, unit-group, and phase-estimation subroutines: if the count in q exceeds q^C polylog(p) for every fixed C, Theorems 1.3 and 1.1 are false. Because the paper never fixes c, the same experiment is also the only way to select the balanced divisor the algorithm promises.

Watch

Extended reading notes

Core claim

The paper's central claim is that a bounded-error quantum algorithm, given a prime p, a divisor q of p−1, and 0 < n < p, computes n! mod p in expected time ~O(q^c + sqrt(p/q)) for some absolute constant c ≥ 1, and that the same bound holds for n! mod p^2 uniformly for 0 ≤ n < p^2. The engine is an exact reconstruction, in compact algebraic form, of the Jacobi sum J_a(χ) for a multiplicative character of order q. The algorithm determines the prime-ideal factorization of the ideal generated by J_a(χ), finds a generator of that ideal using a principal-ideal routine, adjusts it via unit-group and relative-norm computations so it differs from J_a(χ) only by a root of unity, identifies that root b

Load-bearing premise

The whole speedup rests on three cited quantum algorithms actually running in polynomial time in the field degree q and the bit size of p, with no unproved number-theoretic hypothesis; if any one of them is slower or conditional, the claimed exponent below 1/2 collapses.

Editorial extensions

If this is right

  • If the central claim is correct, modular factorials n! mod p for a single input no longer need roughly sqrt(p) work whenever p−1 has a divisor of suitable intermediate size; the time exponent becomes c/(2c+1) < 1/2.
  • The same running-time bound applies to n! mod p^2, and at n = p−1 it computes ((p−1)!+1)/p mod p, giving a single-input test for primes with (p−1)! ≡ −1 mod p^2.
  • The divisor q need not be supplied by the user: factoring p−1 on a quantum computer and applying the paper's trimming argument finds a near-optimal q in polynomial time.
  • A positive proportion of primes have a divisor in the required intermediate range, so the algorithm is not vacuous, though the proportion is not quantified.
  • The compact-representation technique decouples the huge height of an algebraic integer from the cost of evaluating it modulo p or p^2, so exact algebraic reconstruction can be polynomial even when expanded representations are prohibitive.

Reading between the lines

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

  • If the exact-divisibility condition can be relaxed as the author conjectures, the same compact-reconstruction strategy would likely give a uniform sub-square-root quantum algorithm for every prime, not only those whose p−1 has an intermediate divisor; a natural test is to try shifted characters or nearby q that do not divide p−1.
  • The compact-reconstruction pipeline is transferable: any algebraic integer whose ideal factorization is known in a field with polynomial-size descriptions could be reconstructed and evaluated by the same principal-ideal, unit-group, and phase-identification steps, so the method may apply beyond factorial computation.
  • A concrete near-term experiment is to implement the central congruence and the compact-reduction step classically for small primes with q | (p−1) and compare the Jacobi-sum residue with a direct computation of (aK)!; this would validate the number-theoretic core before quantum hardware is available.
  • The paper leaves the constant c unspecified; identifying a concrete c from the referenced algorithms would determine whether the balanced exponent is merely below 1/2 or practically significant, and would make the divisor-search step executable.
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 / 4 minor

Summary. The paper presents a bounded-error quantum algorithm that, given a prime p, a divisor q | (p-1), and an integer 0 < n < p, computes n! mod p in expected time O~(q^c + sqrt(p/q)) for an absolute constant c >= 1. When p-1 has a divisor near p^{1/(2c+1)}, the running time is p^{c/(2c+1)+o(1)} with exponent below 1/2, breaking the square-root barrier under a divisor promise. The method reconstructs the Jacobi sum J_a(chi) in compact algebraic form using Stickelberger's factorization, the Biasse-Song principal-ideal and S-unit algorithms, and Van Dam-Seroussi Gauss-sum phase estimation. It then combines the Jacobi sum with Young's p-adic congruence relating (aK)! to Jacobi sums, and with two classical interval products. A second theorem extends the bound to n! mod p^2, with the Wilson quotient as a corollary.

Significance. If the quoted external algorithms are correct and unconditional as stated, this is a substantial technical contribution: it gives the first sub-square-root quantum algorithm for modular factorials in the divisor-promise regime, and the exact compact reconstruction of Jacobi sums of growing order is a useful new tool. The internal reduction is coherent: the central congruences and Stickelberger factorization are proved in the appendices, and the method avoids expanding algebraic integers of enormous height. The main caveats are that the proof leans on unproved black-box theorems for unit groups, S-units, and Gauss-sum phase estimation, and that the balancing constant c is never made explicit, so the claimed speedup is partly non-effective. These concerns are load-bearing for the headline result but appear addressable within the manuscript's scope.

major comments (3)
  1. [§2.7, Theorems 2.5–2.7] The proof of Theorem 1.3 (and hence Theorems 1.1–1.2) treats the Biasse–Song PIP and S-unit algorithms and the Van Dam–Seroussi Gauss-sum phase estimation as unproved black boxes. The paper asserts they are unconditional and polynomial in degree and log discriminant, citing [18,19]. These results carry the entire q-polynomial dependence in the Jacobi-sum reconstruction; if any of them is conditional on GRH or has a superpolynomial hidden dependence on [F:Q], the O~(q^c) bound and the sub-square-root exponent collapse. Please include the precise statements and hypotheses of the cited theorems, or prove the needed special cases for cyclotomic fields.
  2. [§1.1, §1.3, §4.2] The absolute constant c in Theorems 1.1–1.3 is never made explicit. In the proof of Theorem 1.3, c is chosen larger than the fixed degrees of the polynomial bounds, but those degrees are not stated, notably for the Biasse–Song black boxes. Consequently Proposition 1.4 cannot be applied with target T = p^{1/(2c+1)}: the target itself depends on the unknown c. The balancing discussion is therefore only an existential claim, not an effective algorithm for selecting q. Make c explicit, or reformulate the theorem so that the non-effectiveness of the speedup is stated clearly.
  3. [§4.1, Step 4] The exact recovery of integer exponents from numerical approximations rests on the quoted lower bound from [19, Proposition 6] that the first minimum of the logarithmic unit lattice is at least log(d/2)/(6(d/2)^4). This is a strong polynomial-in-1/d bound, stated without proof or context. If it does not hold, the rounding step and hence the whole coordinate-recovery argument fail. Please provide a proof or a complete statement of the bound, or replace this dependency by a fully specified lemma for the cyclotomic fields used here.
minor comments (4)
  1. [§1.2] The definition of K is typeset ambiguously as “K = p−1 q”; write K = (p−1)/q for clarity.
  2. [Theorem 1.2] The sentence following the display ends with “Breaking the square-root bound again.” with a capital B; fix capitalization and punctuation.
  3. [References] Reference [19] is an arXiv preprint; please update it with the publication status or give the exact DOI if it has appeared.
  4. [§2.1] The same symbol p is used for the rational prime and for the distinguished prime ideal p = (p, ζ_q − η). Although the context is clear, using a Fraktur symbol for the prime ideal would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the Jacobi-sum reconstruction is independent of the target factorial, and the load-bearing external results are not self-citations.

full rationale

The derivation chain is not circular. The algorithm computes n! mod p by: (i) classically computing K! and the remainder interval product via baby-step/giant-step, and (ii) reconstructing the Jacobi sum Ja(χ) exactly via Stickelberger factorization, Biasse–Song principal-ideal and S-unit algorithms, and Van Dam–Seroussi Gauss-sum phase estimation. The central congruence (eq. 1) — (aK)! ≡ (−1)^{a−1} ρp(Ja(χ)) (K!)^a (mod p) — is used only after Ja(χ) has been reconstructed; it is not used to compute Ja(χ). The Jacobi-sum reconstruction never invokes n! or (aK)! as input. The external black boxes (Theorems 2.5, 2.6, 2.7) come from Biasse–Song, Van Dam–Seroussi, and Eisenträger–Hallgren–Kitaev–Song; none of these authors overlap with the present paper, and no load-bearing claim is justified by a self-citation. The paper's own appendices prove the central congruence and the Stickelberger factorization from standard number theory, so those are not assumed from the target result. The main substantive concerns — that the Biasse–Song algorithms are quoted as black boxes, that the absolute constant c is left inexplicit, and that the existence of a suitable divisor q is not guaranteed for all primes — are correctness or completeness risks, not circularity. In particular, if a black-box theorem were conditional or slower than claimed, the conclusion would collapse, but the paper has not defined its output in terms of its input. Therefore the circularity score is 0.

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

The central claim pulls several heavy results from prior literature: Stickelberger, Young, Biasse-Song, Van Dam-Seroussi, and a lattice lower bound. None are new entities; the only free parameter introduced by the paper is the existence of an absolute constant c, and the input divisor q is a promise. The main risk is the unproved unconditionality and exact cost of the external quantum subroutines.

free parameters (2)
  • absolute constant c
    The runtime is O~(q^c) with an unspecified c >= 1. The balanced divisor q = p^(1/(2c+1)) cannot be chosen without knowing c.
  • divisor q = provided as input; near p^(1/(2c+1)) for best speedup
    The speedup only holds for primes p-1 with a divisor of intermediate size. q is a promised input, not derived by the algorithm.
assumptions (6)
  • standard math Stickelberger factorization of Jacobi sums gives the prime-ideal decomposition of (J_a(chi)) with exponents floor(at/q).
    Used in Step 1 of the Jacobi-sum reconstruction and proved via the two-character Jacobi-sum factorization in Appendix C.
  • standard math Young's p-adic congruence specializes to the central congruence mod p (Equation 1) and mod p^2 (Proposition 5.1).
    Load-bearing identity connecting (aK)! to J_a(chi) and (K!)^a; proofs are given in Appendices A and D via Young's theorem [3].
  • ad hoc to paper Biasse-Song S-unit and principal-ideal algorithms are correct, run in polynomial time in [F:Q], log|Delta_F|, |S|, max log N(q), and are unconditional.
    Quoted as Theorems 2.5 and 2.6 from [18,19]; the paper does not prove them or verify unconditionality, yet the Jacobi-sum reconstruction cannot work without them.
  • ad hoc to paper Van Dam-Seroussi Gauss-sum phase estimation returns an angle approximation with error eps in time O(eps^{-1} polylog(p) log(1/delta)), for arbitrary multiplicative characters.
    Theorem 2.7 is used in Step 5 to identify the missing root of unity; the stated cost and success guarantee are not derived in the paper.
  • ad hoc to paper The first minimum of the logarithmic unit lattice of L and L+ is at least log(d/2)/(6(d/2)^4) ( [19, Proposition 6] ).
    This lower bound is needed in Step 4 to recover integer exponent vectors by rounding approximate log-embedding coordinates; it is quoted from an unpublished detailed-version preprint.
  • standard math Shor's algorithm factors p-1 and supports finding a primitive root modulo p in quantum polynomial time.
    Used to construct the character chi and the prime ideal p; standard but not proved in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Algorithms for Modular Factorials." pith.science (2026). https://pith.science/paper/LADN3ZC5

@misc{pith2026260729453,
  author       = {Pith},
  title        = {Pith review of: Quantum Algorithms for Modular Factorials},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LADN3ZC5}},
  note         = {Machine review of arXiv:2607.29453}
}
abstract

We give a bounded-error quantum algorithm that, given a prime $p$, a divisor $q\mid(p-1)$, and an integer $0<n<p$, computes $n!\bmod p$ in expected time $\widetilde{O}(q^c+\sqrt{p/q})$ for some absolute constant $c\ge 1$. When $p-1$ has a divisor of size $q\approx p^{1/(2c+1)}$, this gives the exponent $c/(2c+1)<1/2$. To our knowledge, this is the first algorithm to break the exponent $1/2$ barrier for modular factorials under such a divisor promise. The main technical ingredient is a quantum algorithm that reconstructs the relevant Jacobi sum exactly in compact algebraic form, with polynomial dependence on $q$ and $\log p$. We further extend the same asymptotic bound to the computation of $n!\bmod p^2$, uniformly over $0\le n<p^2$. At $n=p-1$, this determines the Wilson quotient $\frac{(p-1)!+1}{p}\pmod p$. We conjecture that the condition $q\mid(p-1)$ is a technical limitation of the present method rather than an inherent obstruction, and that a uniform quantum algorithm exists for all primes.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 10 canonical work pages

  1. [1]

    Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator

    A. Bostan, P. Gaudry, and É. Schost. “Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator”. In:SIAM Journal on Computing36.6 (2007), pp. 1777–1806.doi:10.1137/S0097539704443793

    work page doi:10.1137/s0097539704443793 2007

  2. [2]

    A Search for Wilson Primes

    E. Costa, R. Gerbicz, and D. Harvey. “A Search for Wilson Primes”. In:Mathematics of Computation83.290 (2014), pp. 3071–3091.doi:10.1090/S0025-5718-2014-02800-7

    work page doi:10.1090/s0025-5718-2014-02800-7 2014

  3. [3]

    On Jacobi Sums, Multinomial Coefficients, andp-adic Hypergeometric Func- tions

    P. T. Young. “On Jacobi Sums, Multinomial Coefficients, andp-adic Hypergeometric Func- tions”. In:Journal of Number Theory52.1 (1995), pp. 125–144.doi: 10.1006/jnth.1995. 1060

    work page doi:10.1006/jnth.1995 1995

  4. [4]

    van Dam and G

    W. van Dam and G. Seroussi.Efficient Quantum Algorithms for Estimating Gauss Sums. Tech. rep. HPL-2002-208. Palo Alto, CA: Hewlett-Packard Laboratories, July 2002. arXiv: quant-ph/0207131

    arXiv 2002

  5. [5]

    Lattice Basis Reduction, Jacobi Sums and Hyperelliptic Cryp- tosystems

    J. Buhler and N. Koblitz. “Lattice Basis Reduction, Jacobi Sums and Hyperelliptic Cryp- tosystems”. In:Bulletin of the Australian Mathematical Society58.1 (1998), pp. 147–154.doi: 10.1017/S000497270003207X

    work page doi:10.1017/s000497270003207x 1998

  6. [6]

    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

    P. W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. In:SIAM Journal on Computing26.5 (1997), pp. 1484–1509.doi: 10.1137/S0097539795293172

    doi:10.1137/s0097539795293172 1997

  7. [7]

    Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

    O. H. Ibarra and C. E. Kim. “Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems”. In:Journal of the ACM22.4 (Oct. 1975), pp. 463–468.doi:10.1145/ 321906.321909

    arXiv 1975

  8. [8]

    Divisors of Shifted Primes

    D. Koukoulopoulos. “Divisors of Shifted Primes”. In:International Mathematics Research Notices24 (2010), pp. 4585–4627.doi:10.1093/imrn/rnq045

    work page doi:10.1093/imrn/rnq045 2010

Show all 21 references
  1. [9]

    Einige Resultate über Berechnungskomplexität

    V. Strassen. “Einige Resultate über Berechnungskomplexität”. In:Jahresbericht der Deutschen Mathematiker-Vereinigung78.1 (1976–1977), pp. 1–8.url: https://eudml.org/doc/146659

    1976

  2. [10]

    Factoring and Factorials

    R. J. Lipton. “Factoring and Factorials”. In:The P=NP Question and Gödel’s Lost Letter. Boston, MA: Springer, 2010, pp. 153–156.doi:10.1007/978-1-4419-7155-5_33

    2010 doi

  3. [11]

    On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines

    L. Blum, M. Shub, and S. Smale. “On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines”. In:Bulletin of the American Mathematical Society21.1 (1989), pp. 1–46.doi:10.1090/S0273-0979-1989- 15750-9

    1989 doi

  4. [12]

    On the Intractability of Hilbert’s Nullstellensatz and an Algebraic Version of “NP̸=P?

    M. Shub and S. Smale. “On the Intractability of Hilbert’s Nullstellensatz and an Algebraic Version of “NP̸=P?”” In:Duke Mathematical Journal81.1 (1995), pp. 47–54.doi: 10.1215/ S0012-7094-95-08105-8

    1995

  5. [13]

    Factoring Integers with Elliptic Curves

    H. W. Lenstra Jr. “Factoring Integers with Elliptic Curves”. In:Annals of Mathematics126.3 (1987), pp. 649–673.doi:10.2307/1971363

    1987 doi

  6. [14]

    On the Ultimate Complexity of Factorials

    Q. Cheng. “On the Ultimate Complexity of Factorials”. In:Theoretical Computer Science 326.1–3 (2004), pp. 419–429.doi:10.1016/j.tcs.2004.06.020

    2004 doi

  7. [15]

    Gauss–Jacobi Sums and Stickelberger’s Theorem

    S. A. Katre. “Gauss–Jacobi Sums and Stickelberger’s Theorem”. In:Cyclotomic Fields and Related Topics. Ed. by S. D. Adhikari, S. A. Katre, and D. S. Thakur. Pune: Bhaskaracharya Pratishthana, 2000, pp. 75–92

    2000

  8. [16]

    L. C. Washington.Introduction to Cyclotomic Fields. 2nd ed. Vol. 83. Graduate Texts in Mathematics. New York: Springer, 1997.doi:10.1007/978-1-4612-1934-7. 33

    1997 doi

  9. [17]

    A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field

    K. Eisenträger, S. Hallgren, A. Kitaev, and F. Song. “A Quantum Algorithm for Computing the Unit Group of an Arbitrary Degree Number Field”. In:Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 2014, pp. 293–302.do...

    2014

  10. [18]

    Efficient Quantum Algorithms for Computing Class Groups and Solving the Principal Ideal Problem in Arbitrary Degree Number Fields

    J.-F. Biasse and F. Song. “Efficient Quantum Algorithms for Computing Class Groups and Solving the Principal Ideal Problem in Arbitrary Degree Number Fields”. In:Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Appl...

    2016 doi

  11. [19]

    Biasse and F

    J.-F. Biasse and F. Song.An Efficient Quantum Algorithm for ComputingS-Units and Its Applications. Detailed version of the SODA 2016 paper. 2025. arXiv:2510.02280 [cs.CR]

    2016

  12. [20]

    Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix

    R. Kannan and A. Bachem. “Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix”. In:SIAM Journal on Computing8.4 (1979), pp. 499–507. doi:10.1137/0208040

    1979 doi

  13. [21]

    B. C. Berndt, R. J. Evans, and K. S. Williams.Gauss and Jacobi Sums. Canadian Mathematical Society Series of Monographs and Advanced Texts. New York: John Wiley & Sons, 1998. 34 A Proof of the Central Congruence We prove (1). Forx=g m∈F× p , ρp(χ(x)) =ρ p(ζm q ) =η m = (gm)−K ...

    1998

Pith tools

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