{"id":"d24c4172-428d-49ad-8955-c615584e4bf3","arxiv_id":"1908.02394","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Using Burgess and Granville-Soundararajan character sum bounds, the author proves small nonresidues exist unconditionally and uses them to speed up the Quadratic Frobenius Test under two of three cost models.","lead":"A number theory paper removes the Extended Riemann Hypothesis from a faster variant of the Quadratic Frobenius primality test. The speedup is real under some standard cost models, but not under Atkin's, which the paper itself acknowledges.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed running-time improvement is conditional on the author's selfridge cost model; under Atkin's model (m=2) the new test is slower, so the 'unconditional' title overstates what is proven.","rationale":"Read in good faith, the manuscript is transparent: Section 4 explicitly computes the cost under Atkin's m=2 weighting and concedes the new test is slower there. The mathematical content—Theorem 3.1 and its use of Burgess plus Granville-Soundararajan—appears sound, though presented as a sketch. The single most load-bearing assumption for the claimed 'unconditional improvement' is the cost model: the speedup from 3 to 2+δ selfridges relies on m=1 and on the linear cost δ for a multiplication by an n^δ-sized integer. Under a ratio m≥1.664 the improvement disappears. This is not an internal inconsistency, but it is a correctness risk for the title's claim. The paper should either qualify the title ('under the selfridge model') or state clearly the cost-model dependence. A secondary concern is that the application of the unpublished GS theorem to the composite Jacobi symbol needs a uniformity check, reinforcing CONDITIONAL rather than ACCEPT. No new concern beyond the reader's is identified.","tokens_in":4251,"tokens_out":58472,"duration_ms":607594,"concrete_test":"Recompute the Section 4 cost comparison as a function of m: original QFT = 2+m MSQs per operation, new rQFT = (2+δ)m. Determine the threshold m0=2/(1+δ). If a concrete implementation (e.g., schoolbook or Montgomery) yields m≥m0, the new variant is not faster. Also, independently re-derive Theorem 3.1 from Corollary 1.8 of Granville-Soundararajan, checking that the constant C<1 can be chosen uniformly in n for the family of Jacobi symbols; if uniformity fails, the 'sufficiently large n' statement is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Theorem 3.1 plus the Section 4 accounting yields a QFT variant with running time (2+δ) selfridges, δ>1/(3√e), compared with 3 for the original QFT. The comparison depends entirely on the cost ratio m between a modular multiplication and a modular squaring. Under the author's convention m=1, the improvement is real (2+δ≈2.2 vs 3). But under Atkin's convention m=2, the original QFT costs 4 SUs, the reformulated QFT costs 6 SUs, and the new variant costs (2+δ)·2≈4.4 SUs—slower than the original QFT, as the paper itself states in Section 4. The improvement therefore holds only when m<2/(1+δ)≈1.664. Since m is implementation-dependent and other published analyses use m=1.3 or m=2, the title's 'unconditional improvement' is not robust to the choice of cost model. Additionally, the proof of Theorem 3.1 is a compact invocation of a previously unpublished Granville-Soundararajan result; applying it to the Jacobi symbol for each composite n requires a uniformity/effectivity check that the paper does not spell out. Neither issue invalidates the character-sum content, but together they mean the headline claim should be read as conditional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4544,"tokens_out":3998,"duration_ms":45832,"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":[{"comment":"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":"Section 4, cost table"},{"comment":"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.","section":"Section 3, proof of Theorem 3.1"}],"minor_comments":[{"comment":"The abstract contains a typo: 'vers ion' should be 'version'.","section":"Abstract"},{"comment":"The sentence 'Let p = 2rs + 1' appears abruptly and without context; it should be part of a complete statement about primes of that form.","section":"Section 1, first paragraph"},{"comment":"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":"Definition 2.1, Step 4"},{"comment":"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":"Section 3, proof of Theorem 3.1"},{"comment":"The phrase 'particular Corollary 1.8 The formulation' is missing punctuation; it should read 'particularly Corollary 1.8. The formulation'.","section":"Section 3, proof of Theorem 3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's own cost table shows that the claimed improvement is negative under Atkin's m = 2 model, so the title overstates what is proved. I would also ask the editor to require a full proof of Theorem 3.1 with the exact Granville-Soundararajan statement and uniformity conditions, since the current proof is a brief citation of a formerly unpublished result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is Theorem 3.1: an unconditional (ERH-free) bound showing that for composite nonsquare n a positive proportion of c < n^δ have (c/n) ≠ 1, for any δ > 1/(3√e). That is a real improvement over Damgård-Frandsen, who needed ERH to get small nonresidues. The application of Burgess and of Granville-Soundararajan to the Jacobi-symbol sum for composite n is the right move, and the paper is honest about relying on a previously unpublished result whose arguments appear in [8]. The cost table in Section 4 is also checked out — the arithmetic is consistent and the distinction between selfridges and Atkin's MSQ-based units is useful to have spelled out.\n\nThe soft spots are real but not fatal. The proof of Theorem 3.1 is a sketch: the Burgess bound is cited, the Granville-Soundararajan theorem is cited, and the uniformity/effectivity for composite n is asserted rather than shown. That is a genuine gap for a referee to fill, but it is a gap of exposition, not an obvious error. The bigger issue is the title. The improvement is unconditional only under the author's cost model where a multiplication and a squaring cost the same. Under Atkin's weighting (m=2) the new test costs ~4.4 SUs versus 4 for the original QFT — slower, as the paper itself admits. Under Damgård-Frandsen's m=1.3 it is faster (~2.86 vs 3.3). So the 'unconditional improvement' is conditional on an implementation-dependent cost ratio. Grantham notes the discrepancy between m=1.3 and m=2 and argues it supports ignoring the distinction entirely, which is a reasonable position but not one that makes the title accurate. A more limited title like 'An unconditional improvement to the running time of the Quadratic Frobenius Test under the selfridge cost model' would be honest. The character-sum content is not affected; only the headline claim.\n\nWho is this for? Specialists in probabilistic primality testing. It will not change practice — Baillie-PSW is already fast — and it does not move any complexity class. But it is a clean, citable result that removes a hypothesis from a published speedup, and it fills a small but real gap in the literature.\n\nRecommendation: send it to peer review. A competent referee can verify the character-sum details and ask the author to qualify the title and expand the proof sketch. The core mathematics appears correct; the overclaim is fixable.","headline":"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.","tokens_in":5057,"tokens_out":666,"would_cite":true,"duration_ms":8543,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11Y11","11L40","11A15"],"pacs":[],"model":"deepseek-v4-flash","headline":"An unconditional variant of the Quadratic Frobenius Test runs in about 2.2 selfridges instead of 3.","keywords":["quadratic Frobenius test","probable prime","quadratic nonresidue","Jacobi symbol","character sum","selfridge","running time","Extended Riemann Hypothesis"],"falsifier":"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.","tokens_in":4050,"feed_emoji":"⚡","tokens_out":12973,"duration_ms":122551,"temperature":0.7,"pith_summary":"The paper tries to establish that the faster version of the Quadratic Frobenius Test, previously available only under the Extended Riemann Hypothesis, works unconditionally. The key number-theoretic result is that for every sufficiently large composite non-square $n$ and every $\\delta > 1/(3\\sqrt{e})$, a positive proportion of the integers $c < n^{\\delta}$ have Jacobi symbol $(c/n) \\neq 1$. Such a small $c$ makes the quadratic extension $x^2-c$ cheap, replacing one full-size modular multiplication with a multiplication by a $\\delta$-sized number. In the author's cost model the running time drops from 3 selfridges to $2+\\delta$ selfridges, about 2.2 near the threshold, so the speed-up that once needed the Extended Riemann Hypothesis becomes unconditional.","feed_headline":"Unconditional tweak drops Frobenius test to 2.2 selfridges","feed_subtitle":"A small-nonresidue trick speeds the probable-prime test without assuming any unproved hypothesis.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Supplies the short-interval character-sum estimate that makes the Jacobi-symbol sum $o(n^\\gamma)$ for $\\gamma$ slightly above $1/3$.","marker":"[4]"},{"why":"States the large-character-sum formulation used to pass from an $o(x)$ bound to a positive proportion of nonresidues with exponent $\\delta > 1/(3\\sqrt{e})$.","marker":"[3]"},{"why":"Gives the arguments behind that large-character-sum theorem in the form needed here.","marker":"[8]"},{"why":"Introduces the reformulated Quadratic Frobenius Test and the ERH-based speed-up that this paper makes unconditional.","marker":"[5]"},{"why":"Introduces the original Quadratic Frobenius Test and the selfridge cost unit used for the running-time comparison.","marker":"[6]"},{"why":"Defines the alternative cost model under which one multiplication costs two squarings and the new test is not an improvement.","marker":"[1]"}],"fun_headline_variants":["Unconditional trick speeds probable-prime test to 2.2 selfridges","Frobenius test gets unconditional speed-up via small nonresidues","No ERH needed: new twist cuts Frobenius test to 2.2 selfridges","Small nonresidues unlock faster primality test without assumptions","Unconditional improvement drops Frobenius test runtime"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Unconditional trick speeds probable-prime test to 2.2 selfridges","Frobenius test gets unconditional speed-up via small nonresidues","No ERH needed: new twist cuts Frobenius test to 2.2 selfridges","Small nonresidues unlock faster primality test without assumptions","Unconditional improvement drops Frobenius test runtime"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000694,"raw_usage":{"total_tokens":3116,"prompt_tokens":902,"completion_tokens":2214,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":518,"completion_tokens_details":{"reasoning_tokens":2118}},"tokens_in":518,"tokens_out":2214,"duration_ms":16915,"temperature":1.0,"reasoning_tokens":2118,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:45:19.127152+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the short-interval character-sum estimate that makes the Jacobi-symbol sum $o(n^\\gamma)$ for $\\gamma$ slightly above $1/3$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the large-character-sum formulation used to pass from an $o(x)$ bound to a positive proportion of nonresidues with exponent $\\delta > 1/(3\\sqrt{e})$."},{"cited_title":"Granville and K","cited_arxiv_id":null,"evidence_quote":"Gives the arguments behind that large-character-sum theorem in the form needed here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the reformulated Quadratic Frobenius Test and the ERH-based speed-up that this paper makes unconditional."},{"cited_title":"Grantham, A probable prime test with high confidence, J","cited_arxiv_id":null,"evidence_quote":"Introduces the original Quadratic Frobenius Test and the selfridge cost unit used for the running-time comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the alternative cost model under which one multiplication costs two squarings and the new test is not an improvement."}],"review_version":1}