REVIEW 2 major objections 5 minor 13 references
An Unconditional Improvement to the Running Time of the Quadratic Frobenius Test
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read An unconditional variant of the Quadratic Frobenius Test runs in about 2.2 selfridges instead of 3.
desk verdict Small, honest, technically sound note that removes ERH from a constant-factor speedup in the QFT, but the 'unconditional' in the title is doing more work than the cost analysis can support. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Jacobi-symbol sum $S(\gamma)=\sum_{k<n^{\gamma}}(k/n)$. A short-interval character-sum estimate shows $S(\gamma)=o(n^{\gamma})$ for $\gamma$ slightly above $1/3$, and a second theorem on large character sums converts that into a positive proportion of values $\neq 1$ for every exponent $\delta > 1/(3\sqrt{e})$. In the algorithm, this supplies a small $c$ with $(c/n)=-1$ or $0$, so the quadratic extension is $x^2-c$ with coefficients of size $\delta N$; one of the three modular multiplications in the extension arithmetic shrinks from size $N$ to size $\delta N$.
What would settle it
Compute, for a growing sequence of composite non-squares $n$ and a fixed $\delta > 1/(3\sqrt{e})$, the proportion of $c < n^{\delta}$ with $(c/n)=1$; if that proportion tends to 1, the theorem's positive-proportion claim is false. Separately, benchmark the variant with a multiply-to-square ratio $m \ge 2$; if it is not faster than the original Quadratic Frobenius Test, the speed-up claim fails for that cost model.
Extended reading notes
Core claim
For every sufficiently large composite integer $n$ that is not a square, and every $\delta > 1/(3\sqrt{e})$, a positive proportion of $c$ in $0<c<n^{\delta}$ satisfy $(c/n)\neq 1$. The proof combines a short-interval character-sum estimate showing $\sum_{k<n^\gamma}(k/n)=o(n^\gamma)$ for $\gamma$ just above $1/3$ with a large-character-sum theorem that lifts such an $o(x)$ bound to an $O(x^\alpha)$ bound for any $\alpha>1/\sqrt{e}$; taking $\gamma$ close to $1/3$ and $\alpha$ close to $1/\sqrt{e}$ yields every $\delta=\alpha\gamma$ above $1/(3\sqrt{e})$. The algorithmic consequence is an unconditional reformulated Quadratic Frobenius Test (rQFT) variant whose cost per $\log_2 n$ operation is $(2+\delta)m$ modular squarings, where $m$ is the price of one modular multiplication in squaring units; this is $(2+\delta)$ selfridges when $m=1$, about $2.86$ selfridge units when one multiplication costs $1.3$ squarings, and $4.4$ selfridge units when one multiplication costs two squarings. In the last case the variant is not faster than the original QFT, so the claimed improvement is tied to the cost model.
Load-bearing premise
The claimed speedup assumes that a modular multiplication by an integer of size $\delta N$ costs $\delta$ times a full multiplication and that multiplication costs less than twice a squaring; under the opposite weighting the new test is slower than the original QFT.
Editorial extensions
If this is right
- Probable-prime testing can realize the small-nonresidue speed-up without any unproved hypothesis, matching what was previously conditional on the Extended Riemann Hypothesis, in the author's cost model.
- The running time of the reformulated Quadratic Frobenius Test falls to $2+\delta$ selfridges, about $2.2$ for $\delta$ close to $1/(3\sqrt{e})$.
- The constant $1/(3\sqrt{e})$ is a real threshold: the unconditional argument supplies no positive proportion of small nonresidues for exponents at or below it.
- Reported speed-ups must be accompanied by the assumed multiplication-to-squaring cost ratio, since the variant is slower when that ratio is $2$.
Reading between the lines
- One could test the residue-count theorem numerically for large composite $n$: the fraction of $c<n^{\delta}$ with $(c/n)\neq 1$ should stay bounded away from zero, so a visible decline would suggest the constants in the proof need re-examination.
- The same two-stage character-sum route could supply small coefficients for other primality or compositeness tests built on quadratic extensions, wherever a small nonresidue cheapens multiplication.
- A natural convention for future timing papers is to report both the multiplication-to-squaring ratio and the resulting cost in selfridge units, rather than a single figure.
- Because the theorem counts values $\neq 1$, it also counts $c$ sharing a factor with $n$; the small-$c$ search therefore doubles as a way to find small factors of composite $n$, which may be useful in factoring algorithms.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an unconditional (no ERH) variant of the Quadratic Frobenius Test by finding, via Burgess-type character sum estimates and a theorem of Granville and Soundararajan, a small c with Jacobi symbol (c/n) = -1. Theorem 3.1 states that for sufficiently large nonsquare composite n and any delta > 1/(3 sqrt(e)), a positive proportion of 0 < c < n^delta have (c/n) != 1. Section 4 then compares the running time of the resulting reformulated QFT with the original QFT under three different cost models for modular multiplication relative to modular squaring: m = 1, m = 1.3, and m = 2. The paper reports a running time of (2 + delta) selfridges under the author's convention, versus 3 for the original QFT, and also notes that under Atkin's weighting (m = 2) the new variant is not an improvement.
Significance. If Theorem 3.1 can be established with full details, the paper makes a worthwhile contribution: it removes the ERH assumption from the Damgard-Frandsen speedup and connects it to modern character sum bounds. The cost analysis is transparent and the arithmetic in the selfridge counts is internally consistent; no data are fitted and no circularity is apparent. However, the significance of the claimed speedup depends heavily on the cost model, and the proof of the key number-theoretic theorem is only a sketch, so the result as presented is conditional in both regards.
major comments (2)
- [Section 4, cost table] The headline claim of an 'unconditional improvement' in running time is not robust to the choice of cost model. In the author's own accounting, under Atkin's convention m = 2 the original QFT costs 4 SUs, while the new variant costs (2 + delta) * 2 ≈ 4.4 SUs, so it is slower. The improvement holds only when m < 2/(1 + delta) ≈ 1.664, a condition that is not defended and that excludes one of the cost models the paper itself discusses. Since the central claim is exactly the running-time improvement, the title and abstract should be qualified, or the cost model should be justified as the appropriate standard.
- [Section 3, proof of Theorem 3.1] The proof of Theorem 3.1 is only a sketch. It invokes Theorem A of [4] and a Granville-Soundararajan theorem as stated in [3], but does not verify that the hypotheses of the latter apply to the Jacobi symbol sum modulo composite n for every sufficiently large nonsquare n, nor does it spell out the uniformity in n that is needed to pass from the Burgess bound to the final density statement. In particular, the exact relation among gamma, alpha, and delta, and the required size of the 'positive proportion' and 'sufficiently large' thresholds are not quantified. Because Theorem 3.1 is the core enabling result for the claimed speedup, a complete derivation or a precise reference with all constants and hypotheses is needed.
minor comments (5)
- [Abstract] The abstract contains a typo: 'vers ion' should be 'version'.
- [Section 1, first paragraph] The sentence 'Let p = 2rs + 1' appears abruptly and without context; it should be part of a complete statement about primes of that form.
- [Definition 2.1, Step 4] The congruence 'xn+1 ≢ -c' is missing the modulus; it should read 'mod (n, x^2 - bx - c)' for consistency with the preceding step.
- [Section 3, proof of Theorem 3.1] In the line quoting the Granville-Soundararajan result, 'sum_{m <= x} f(n) = o(x)' uses n as the summation variable in f(n) but m in the summation; this is a typo that should be corrected.
- [Section 3, proof of Theorem 3.1] The phrase 'particular Corollary 1.8 The formulation' is missing punctuation; it should read 'particularly Corollary 1.8. The formulation'.
Circularity Check
No significant circularity: the running-time improvement comes from external character-sum bounds and an explicit cost calculation, with only a minor, non-load-bearing self-citation for the original QFT definition.
full rationale
The paper's central claim, Theorem 3.1, is a positive-proportion statement about Jacobi-symbol nonresidues derived from Burgess's character-sum estimates and the Granville-Soundararajan large-character-sum theorem; both are external published results, with the formulation taken from Banks, Garaev, Heath-Brown, and Shparlinski. No parameter is fitted to data, and no output is renamed as a prediction. The Section 4 speedup is a transparent cost calculation: the original QFT costs 2+m MSQs per (1+o(1)) log2 N operation, and the new variant costs (2+delta)m MSQs, which becomes 2+delta selfridges only under the author's convention m=1. The comparison is definitional in the sense that the 'selfridge' unit is the author's own from [6], but the central claim does not reduce to that definition unless one also accepts the cost model; the paper explicitly reports that under Atkin's m=2 convention the new test is slower, so the running-time claim is model-dependent rather than circular. The self-citations to [6] and [7] define the original QFT and its known error bounds, but they do not carry the load of Theorem 3.1 or of the cost count. No circular step satisfies the required quote-and-reduction standard, so the appropriate finding is a minimal score reflecting only the incidental, non-load-bearing self-citation used to define the baseline test.
Assumptions & free parameters
free parameters (2)
- δ (exponent for small nonresidue interval) =
any value > 1/(3√e), approximately 0.202 or greater
- m (cost ratio of modular multiplication to modular squaring) =
1 (Grantham selfridge), 1.3 (Damgård-Frandsen), 2 (Atkin)
assumptions (4)
- standard math Burgess type character sum bound for Jacobi symbols modulo composite n (Theorem A of [4]): for any ε>0, ∑_{k<n^γ} (k/n) < (n^γ)^{2/3} n^{1/9+ε}.
- standard math Granville-Soundararajan theorem (Corollary 1.8 of [8]): if ∑_{m≤x} f(m)=o(x) and α>1/√e, then |∑_{m≤x^α} f(m)| < C x^α for some C<1.
- domain assumption The reformulated Quadratic Frobenius Test (rQFT) and its error bounds from Damgård-Frandsen [5] remain valid for the new parameter choices.
- domain assumption The cost of a modular multiplication by a number of size δN is δ times the cost of a full multiplication (linear scaling with bit length).
Cite this review
Pith. "Pith review of An Unconditional Improvement to the Running Time of the Quadratic Frobenius Test." pith.science (2026). https://pith.science/paper/6PIGYNEG
@misc{pith2026190802394,
author = {Pith},
title = {Pith review of: An Unconditional Improvement to the Running Time of the Quadratic Frobenius Test},
year = {2026},
howpublished = {\url{https://pith.science/paper/6PIGYNEG}},
note = {Machine review of arXiv:1908.02394}
}
read the original abstract
In a 2006 paper, Damg{\aa}rd and Frandsen designed a faster version of the Quadratic Frobenius Test. This test assumes the Extended Riemann Hypothesis in order to find small nonresidues, which allow construction of quadratic extensions with faster arithmetic. In this paper, I describe a version of the test using small nonresidues, without assuming any unproven hypothesis.
Reference graph
Works this paper leans on
-
[8]
A. Granville and K. Soundararajan, Large character sums: Bur gess’s theo- rem and zeros of L-functions, J. Eur. Math. Soc. (JEMS) 20 (2018) 1–14
work page 2018
-
[4]
D. A. Burgess, The character sum estimate with r = 3, J. London Math. Soc. (2) 33 (1986) 219–226
work page 1986
-
[3]
W. D. Banks, M. Z. Garaev, D. R. Heath-Brown, and I. E. Shpar linski, Density of non-residues in Burgess-type intervals and applications , Bull. Lond. Math. Soc. 40 (2008) 88–96
work page 2008
-
[1]
A. O. L. Atkin, Intelligent primality test offer, in Computational perspec- tives on number theory (Chicago, IL, 1995) , AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, 1–11
work page 1995
-
[2]
R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980) 1391–1417
work page 1980
-
[5]
I. B. Damg ˚ ard and G. S. Frandsen, An extended quadratic Fro benius pri- mality test with average- and worst-case error estimates, J. Cryptology 19 (2006) 489–520
work page 2006
-
[6]
Grantham, A probable prime test with high confidence, J
J. Grantham, A probable prime test with high confidence, J. Number The- ory 72 (1998) 32–47. [7] , Frobenius pseudoprimes, Math. Comp. 70 (2001) 873–891
work page 1998
-
[9]
L. Monier, Evaluation and comparison of two efficient probabilistic p rimal- ity testing algorithms, Theoret. Comput. Sci. 12 (1980) 97–108
work page 1980
Show all 13 references
-
[10]
M¨ uller, A probable prime test with very high confidence for n ≡ 1 mod 4, in Advances in cryptology—ASIACRYPT 2001 (Gold Coast) , Lecture Notes in Comput
S. M¨ uller, A probable prime test with very high confidence for n ≡ 1 mod 4, in Advances in cryptology—ASIACRYPT 2001 (Gold Coast) , Lecture Notes in Comput. Sci., vol. 2248, Springer, Berlin, 2001, 87–106
2001
-
[11]
Cryptology 16 (2003) 117–139
, A probable prime test with very high confidence for n ≡ 3 mod 4, J. Cryptology 16 (2003) 117–139
2003
-
[12]
Pomerance, J
C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pse udoprimes to 25 · 109, Math. Comp. 35 (1980) 1003–1026
1980
-
[13]
M. O. Rabin, Probabilistic algorithm for testing primality, J. Number The- ory 12 (1980) 128–138
1980
-
[14]
Zhang, A one-parameter quadratic-base version of the Ba illie-PSW prob- able prime test, Math
Z. Zhang, A one-parameter quadratic-base version of the Ba illie-PSW prob- able prime test, Math. Comp. 71 (2002) 1699–1734. 5
2002
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.