{"id":"9c8f782e-43e2-43bf-b89f-8cd2d3ddb6bc","arxiv_id":"1908.06964","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors conjecture that an odd non-square N is prime iff a quadratic non-residue q, with q not congruent to -1, passes both the Euler criterion and a quadratic-extension binomial congruence.","lead":"This paper proposes a new way to test whether a large number is prime using quadratic non-residues and a binomial congruence, claiming much faster deterministic tests than the famous AKS algorithm. The catch is that the main result is an unproven conjecture, supported by experiments with no counterexamples so far.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Advertised O((log N)^3) test is not the Section 11 algorithm: PPTA_INR uses four-condition PGPC with exponent N^d-1, giving O((log N)^4) by the paper's own PL6.","rationale":"The manuscript is genuinely useful as a conjecture-plus-experiments paper: it proves PL1-PL4, supplies a large amount of reproducible experimental data (Pinch's Carmichael sets, big Carmichaels, probable primes), and is transparent about which parts are conjectures (abstract; Sections 10 and 13.1; Section 15.2). Those are real strengths, and I do not dispute the experimental record. However, the advertised central result — a deterministic O((log N)^3) primality test — is not what the specified algorithm delivers. The Section 11 algorithm explicitly invokes the four-condition PGPC, and the paper's own PL6 shows that this costs O((log N)^4). The O((log N)^3) bound is derived under FGPC, which is both unproven and never implemented as a complete algorithm. This is not a matter of outside consensus; it is an internal mismatch between the stated result and the provided construction. Additionally, the correctness of any version of the test depends on unproven conjectures, so the word 'unconditionally' in the abstract overstates the status. The reader's weakest_assumption (FGPC) captures part of this, and the verdict of REJECT is appropriate for the paper's stated claims; a revised manuscript that clearly frames the algorithms as conditional on the conjectures and uses FGPC consistently could merit a different assessment.","tokens_in":61867,"tokens_out":12562,"duration_ms":132868,"concrete_test":"Take the PPTA_INR pseudocode from Section 11 and count, for the PGPC branch, the bit-complexity of each of the four conditions. For conditions 3 and 4, the exponent is N^d - 1, so the square-and-multiply loop has about d log N iterations, each costing O(d log N polylog(log N)) for polynomial multiplication modulo Υ_m or Ψ_m; summing gives O(d^2 (log N)^2 polylog(log N)) = O((log N)^4 polylog(log N)), exactly PL6. Then repeat the count after replacing line 23 with the single FGPC congruence of Section 13.1: the exponent is N, giving O((log N)^3). The discrepancy settles that the advertised O((log N)^3) complexity applies to an algorithm that is not specified in the manuscript, and that the specified PPTA_INR is O((log N)^4) conditional on PGPC.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central advertised result is a deterministic worst-case O((log N)^3) primality test (abstract; Section 14). The algorithm actually specified as PPTA_INR (Section 11) does not implement that result. After finding the canonical m, line 23 checks 'any of the four conditions in PGP Conjecture' — i.e., PGPC, not FGPC. PGPC conditions 3 and 4 (Section 10) require evaluating x^(N^d - 1) modulo Υ_m(x) and Ψ_m(x), where d = deg Υ_m. The paper's own Primality Lemma 6 derives from this an O((log N)^4 polylog(log N)) worst case. The O((log N)^3) claim (Primality Lemma 7) is conditional on the Furthermost Generalized Primality Conjecture (FGPC, Section 13.1), which checks a single binomial congruence modulo Ψ_m, and is stated as a conjecture with no proof. No pseudocode for an FGPC-only algorithm is given, and the experimental support in Part 2 does not replace a proof. Furthermore, the abstract's 'unconditionally' is not supported: correctness of both the baseline and generalized algorithms depends on the unproven PBPC/PGPC/FGPC; Part 3 supplies only partial proofs for special cases (Sections 15.2 and 33). Thus the paper's main claim, as stated, is not established by its own specified algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript, in three companion parts, proposes new deterministic primality tests based on a family of conjectures about quadratic non-residues and cyclotomic-derived polynomials. The Baseline Primality Conjecture (Section 2) asserts that an odd non-square N is prime if some q ≠ -1 is a quadratic non-residue, satisfies Euler's criterion, and makes sqrt(q) satisfy the modular binomial congruence. Part 1 specifies the explicit-QNR algorithm PPTA_EQNR and the implicit-non-residue algorithm PPTA_INR, derives several auxiliary lemmas, and states the Generalized and Furthermost Generalized Primality Conjectures (Sections 10 and 13.1). Part 2 reports experimental tests over Carmichael numbers, pseudoprimes, and large probable primes, claiming no counterexample. Part 3 gives proofs of the baseline conjecture for special cases. The advertised headline result is a deterministic worst-case O((log N)^3 polylog(log N)) primality test, with PPTA_EQNR claimed to run in O((log N)^2 polylog(log N)) once a quadratic non-residue is known.","tokens_in":62349,"tokens_out":2917,"duration_ms":34802,"significance":"If the conjectures were proved, the paper would offer a substantial complexity improvement over AKS for deterministic primality testing, and the hybrid Miller-Rabin variants in Section 7 could be practically useful. The paper deserves credit for several clean auxiliary results: PL1 (a QNR that is a Miller-Rabin witness is an Euler witness), PL2 (the binomial congruence holds modulo any nonzero divisor polynomial for prime N), PL3 (existence of canonical divisor polynomials with non-residue roots), and PL4 (Fermat-style identity in irreducible quotient rings). The experimental campaign is extensive, covering all Carmichael numbers below 10^18, many constructed pseudoprimes, and very large probable primes, and the conjectures are tested against external data rather than fit to data. However, the central claims are conditional on unproved conjectures, and the paper's own specified algorithm does not realize the advertised O((log N)^3) bound.","major_comments":[{"comment":"The abstract claims a deterministic worst-case O((log N)^3 polylog(log N)) test 'unconditionally', but the only derivation of that bound is Primality Lemma 7, whose proof begins 'Assuming that the Furthermost Generalized Primality Conjecture (FGPC) is true'. FGPC itself is stated in Section 13.1 as a conjecture with no proof, and the paper provides no pseudocode for an FGPC-only algorithm. The algorithm actually specified, PPTA_INR in Section 11, line 23, checks 'any of the four conditions in PGP Conjecture', i.e. PGPC, not FGPC. The paper's own PL6 gives an O((log N)^4 polylog(log N)) bound for that algorithm. The advertised O((log N)^3) claim is therefore not established by the manuscript.","section":"Abstract and Section 13.1"},{"comment":"The load-bearing assertion is Phatak's Baseline Primality Conjecture (PBPC), which states that conditions C-1 through C-5 are sufficient for primality. Section 4 proves correctness of PPTA_EQNR only under the explicit assumption 'if the PBP Conjecture is true'. Section 15.2 and Part 3 acknowledge that only special cases of the conjectures are proved analytically. Since the deterministic correctness of the baseline and generalized algorithms rests entirely on these unproven conjectures, the manuscript does not provide a deterministic primality test in the standard sense.","section":"Section 2 and Section 4"},{"comment":"The analogue of Euler's criterion for the canonical divisor polynomials is introduced as 'Auxiliary Primality Conjecture 1' and the paper states 'We do not yet know how to prove in general ... the two identities in Eqns. (78) and (79)'. The partial proofs given require irreducibility of Υ_m or Ψ_m modulo N, which is a stronger condition than the no-integer-root guarantee of PL3 and is not established for the algorithm's inputs. These identities are essential to PGPC conditions 3 and 4, so the generalized test's correctness is not supported beyond the conjecture itself.","section":"Section 9.2, Eqs. (78) and (79)"},{"comment":"The claimed O((log N)^2 polylog(log N)) complexity of PPTA_EQNR applies only after an explicit QNR is available. Section 5.2 concedes that no deterministic polynomial-time method is known to find a QNR for arbitrary composite N, and Section 5.3 writes the overall complexity as the maximum of the two costs. Thus the manuscript does not actually deliver a deterministic polynomial-time test for all N via the baseline route; the generalized route is the only candidate, and it is conjectural and at best O((log N)^4) by the paper's own PL6.","section":"Section 5.2 and Section 5.3"},{"comment":"The experimental data, while extensive, do not constitute evidence sufficient for a deterministic correctness claim. Testing all Carmichael numbers below 10^18 and assorted larger pseudoprimes is useful corroboration, but the conjectures are universal statements over all integers, and the paper's own conclusion in Part 2 is 'No counter example has been found'. This cannot replace a proof, and the paper explicitly leaves the full proofs as future work.","section":"Part 2, Sections 20-24"}],"minor_comments":[{"comment":"The pseudocode refers to 'PGP Conjecture', which appears to be a typo for 'PGPC' (Phatak's Generalized Primality Conjecture).","section":"Section 11, line 23"},{"comment":"Several passages are written in a personal, exhortatory style ('we hope that readers and reviewers will feel the same level of excitement', 'just joking as usual') that is inappropriate for a formal journal submission.","section":"Section 16 and Part 2, Section 23"},{"comment":"The nested numbering '5.1, 5.2, 5.3' inside Reason 1 conflicts with the section numbering and makes the text harder to follow.","section":"Section 5.4, Reason 1"},{"comment":"The notation for the coefficients of BCC(sqrt(q),N) is inconsistent: A and B are used in Eq. (16), while A1 and B1 are introduced in Eq. (20) without a clear distinction; define the coefficient notation once and use it consistently.","section":"Equations (16)-(20)"},{"comment":"The document contains numerous typographical errors and formatting artifacts, including 'Primailty' in the title page, 'congruence modulo' misspellings, and several incomplete or garbled sentences; a thorough editorial pass is needed.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The manuscript is a set of three companion papers combined into one document. The core issue is not presentation but substance: the principal results are explicitly conjectural, and the algorithm that is actually specified does not achieve the advertised complexity. This is a high-risk, high-reward submission, but in its current form the central claims are not established and the missing steps are the main content, not fixable local errors. I would not recommend inviting a revision unless the authors can supply proofs of PBPC, PGPC, or at least a fully specified FGPC-based algorithm with a correctness argument, or can reframe the paper as a conjectural research announcement with explicit disclaimers in the abstract. The experimental data are a real strength and could support a shorter empirical paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a conjecture paper, not a theorem paper. The advertised deterministic O((log N)^3) primality test doesn't match the algorithm the paper actually specifies, and the abstract's 'unconditionally' is not supported by anything in the document. That said, the conjectures are new and the experimental work is substantial, so it's worth taking seriously.\n\nThe genuinely new content: the PBP conjecture says that for odd non-square N, if q is a QNR with q ≠ -1, q satisfies the Euler criterion, and (1+sqrt(q))^N ≡ 1 + sqrt(q)^N mod N, then N is prime. The PGPC/FGPC generalizations use cyclotomic-derived polynomials Υ_m and Ψ_m. I don't know of these exact statements in the prior literature. PL1 is a nice proved observation: for a QNR base, a Miller-Rabin witness is an Euler witness, so the Euler criterion check is at least as strong as one MR iteration. The experiments are real: all Carmichael numbers < 10^18, pseudoprimes < 10^13, the big Arnault/Howe composites, and a few 30k-digit probable primes. No counterexample found. The paper is transparent about what is proved and what is conjecture.\n\nThe soft spots, in order. First, the complexity claim is mismatched. Section 11's PPTA_INR checks the four PGPC conditions and the paper's own PL6 gives O((log N)^4). The O((log N)^3) bound is conditional on FGPC, stated as a conjecture in Section 13.1 with no proof and no pseudocode for an FGPC-only algorithm. The abstract says 'unconditionally' for that O((log N)^3) result, which is false on the paper's own terms. Second, the central reverse direction—no composite satisfies the conditions—is unproven; Part 3 covers only special cases. Third, the citation gap: no Grantham quadratic Frobenius test, no Frobenius pseudoprime literature, which is the closest prior work in spirit.\n\nWho this is for: people working on primality testing. The Section 23 counterexample—a composite that fools Henri's probable-prime criteria but is caught by their test—is an interesting, concrete finding. The conjectures could inspire a proof or a counterexample; either would be progress.\n\nRecommendation: a serious editor should send this to a referee rather than desk-reject. The referee should push the authors to fix the framing: either present it as a conjecture-plus-evidence paper, or scale back the claims. As written, it does not establish a deterministic O((log N)^3) primality test, but it is a serious research program worth engaging with.","headline":"A genuinely new conjecture-driven approach to deterministic primality testing with strong experimental evidence, but the advertised O((log N)^3) result is not the algorithm actually specified and the abstract overstates what is proven.","tokens_in":62675,"tokens_out":3968,"would_cite":false,"duration_ms":38564,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11Y11","11A15","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Two modular congruences, one using a quadratic non-residue, may certify primality if the paper's conjecture holds.","keywords":["primality testing","quadratic non-residue","Euler criterion","modular binomial congruence","cyclotomic polynomials","Carmichael numbers","deterministic polynomial time","strong pseudoprime test"],"falsifier":"For the baseline conjecture, a single composite N and a quadratic non-residue q not equal to -1 with q^((N-1)/2) congruent to -1 modulo N and (1+$\\sqrt$(q))^N congruent to 1+($\\sqrt$(q))^N modulo N would refute the claim. For the fastest generalized form, a single composite N whose Psi_m congruence vanishes would refute FGPC; such an N can be sought by running the check on the same Carmichael and pseudoprime datasets already used in the paper.","tokens_in":61640,"feed_emoji":"🔢","tokens_out":8637,"duration_ms":84227,"temperature":0.7,"pith_summary":"The paper claims that an odd integer can be certified prime by a small number of modular checks built around quadratic non-residues. In its baseline form, the claim is that any composite fails at least one of five conditions: N is odd and not a square; q is a non-residue with q not equal to -1; q satisfies the Euler criterion; and (1+$\\sqrt$(q))^N is congruent to 1+($\\sqrt$(q))^N modulo N. If all hold, the number is prime. The authors then replace the explicit non-residue with roots of low-degree polynomials derived from cyclotomic polynomials, which lets the test avoid ever finding a non-residue and gives conjectured worst-case deterministic complexity O((log N)^3) with polylog factors. The conjectures are backed by large experiments over Carmichael numbers, pseudoprimes, and multi-thousand-digit probable primes; analytic proofs are completed only for special cases of the baseline conjecture.","feed_headline":"Two congruences may certify primes—if a new conjecture holds","feed_subtitle":"A residue check plus a binomial congruence could replace many rounds of random testing.","key_machinery":"The engine is the Modular Binomial Expansion Congruence (MBEC): for prime N, (1+x)^N is congruent to 1+x^N modulo N. The baseline test evaluates this congruence at x = $\\sqrt$(q) for a quadratic non-residue q, together with the Euler criterion q^((N-1)/2) congruent to -1 modulo N. To avoid finding an explicit q, the paper derives from the cyclotomic polynomial Phi_m(x) two monic polynomials Upsilon_m(t), via t = x + 1/x, and Psi_m(u), via u = $\\sqrt$($t^{2}$ - 4), whose roots are implicitly non-residues modulo N. The generalized tests perform the MBEC and the power law x^(N^d - 1) modulo Upsilon_m and Psi_m, where d is the degree of Upsilon_m; a logarithmic bound on m keeps d logarithmic in N, which is what drives the low worst-case complexity claim.","core_discovery":"The paper's central claim is that no composite integer can simultaneously satisfy the Baseline Primality Conjecture conditions: N is odd and not a perfect square; q is a quadratic non-residue modulo N with q not congruent to -1; q satisfies the Euler criterion q^((N-1)/2) congruent to -1 modulo N; and $\\sqrt$(q) satisfies the modular binomial congruence (1+$\\sqrt$(q))^N congruent to 1+($\\sqrt$(q))^N modulo N. The authors generalize this by deriving two monic polynomials, Upsilon_m and Psi_m, from the cyclotomic polynomial Phi_m, whose roots implicitly specify non-residues modulo N. They conjecture that checking the binomial congruence and related power congruences modulo these polynomials certifies primality without an explicit non-residue. The fastest form, the Furthermost Generalized Primality Conjecture, reduces the certificate to a single congruence modulo Psi_m. The paper reports exhaustive experiments with no counterexample, but analytic proofs are provided only for some subcases of the baseline conjecture.","pith_inferences":["Beyond the paper, if FGPC survives further testing, the generalized test becomes a candidate for the fastest known deterministic primality certificate in practice, because the degree of Psi_m is logarithmic in N rather than roughly (log N)^2 as in the standard polynomial-time test.","Beyond the paper, the same implicit-non-residue construction may transfer to other tasks in computational number theory that require a non-residue, such as constructing irreducible polynomials or extracting square roots in finite fields, though the paper does not develop that transfer.","Beyond the paper, the hybrid structure suggests a practical adaptive protocol: try random bases, and as soon as one turns out to be a quadratic non-residue, switch to the two-congruence certificate to obtain a deterministic result; the paper describes hybrids but does not optimize this switching policy."],"forward_implications":["For roughly 91.67% of odd inputs, either 2, -2, or 3 is immediately available as a quadratic non-residue, so the baseline test needs at most two modular exponentiations once that value is in hand.","A quadratic non-residue that fails the strong pseudoprime test also fails the Euler criterion, so an Euler-criterion check can replace further strong-pseudoprime rounds whenever a non-residue is encountered.","If the Furthermost Generalized Primality Conjecture holds, a single binomial congruence modulo Psi_m certifies primality in worst-case O((log N)^3 polylog(log N)) without ever constructing an explicit non-residue.","The cyclotomic and Upsilon_m congruence checks alone can be fooled by composites; in the experimental record, the Psi_m check is the one that catches the composites that pass the others."],"supporting_citations":[{"why":"Supplies the exhaustive list of Carmichael numbers below 10^18 on which the conjectures and algorithms are tested.","marker":"[1]"},{"why":"Supplies adversarial composites constructed to fool common probabilistic primality libraries, which the new algorithms are tested against.","marker":"[2]"},{"why":"Supplies the modular binomial congruence as the starting point and the deterministic polynomial-time baseline for complexity comparison.","marker":"[10]"},{"why":"Supplies the construction that lets non-residues be specified implicitly, a building block for the generalized algorithms.","marker":"[20]"},{"why":"Supplies large constructed Carmichael numbers used to test the algorithms and to verify primality of their prime factors.","marker":"[47]"},{"why":"Supplies the giant probable primes used to demonstrate the algorithms on numbers beyond 30,000 decimal digits.","marker":"[49]"}],"fun_headline_variants":["Two congruences might prove primality—if conjecture holds","Faster primality testing via hidden non-residues","Deterministic prime test promising O((log N)^3)—conjectural","Primality check via implicit non-residues: no counterexamples","New primality test: 91% of odds need only explicit QNR"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The fastest generalized variant stands on one unsupported claim: no composite passes the single binomial congruence computed modulo the special polynomial Psi_m (derived from cyclotomic polynomials), and the paper supports that claim only by experiment.","fun_headline_variants_meta":{"raw":{"variants":["Two congruences might prove primality—if conjecture holds","Faster primality testing via hidden non-residues","Deterministic prime test promising O((log N)^3)—conjectural","Primality check via implicit non-residues: no counterexamples","New primality test: 91% of odds need only explicit QNR"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000343,"raw_usage":{"total_tokens":1984,"prompt_tokens":1143,"completion_tokens":841,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":759,"completion_tokens_details":{"reasoning_tokens":748}},"tokens_in":759,"tokens_out":841,"duration_ms":9997,"temperature":1.0,"reasoning_tokens":748,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:18:19.210910+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the baseline conjecture, a single composite N and a quadratic non-residue q not equal to -1 with q^((N-1)/2) congruent to -1 modulo N and (1+$\\sqrt$(q))^N congruent to 1+($\\sqrt$(q))^N modulo N would refute the claim. For the fastest generalized form, a single composite N whose Psi_m congruence vanishes would refute FGPC; such an N can be sought by running the check on the same Carmichael and pseudoprime datasets already used in the paper.","supporting_citations":[{"cited_title":"Mathematics research page,","cited_arxiv_id":null,"evidence_quote":"Supplies the exhaustive list of Carmichael numbers below 10^18 on which the conjectures and algorithms are tested."},{"cited_title":"Prime and prejudice: Primality testing under adversarial conditions,","cited_arxiv_id":null,"evidence_quote":"Supplies adversarial composites constructed to fool common probabilistic primality libraries, which the new algorithms are tested against."},{"cited_title":"PRIMES is in P,","cited_arxiv_id":null,"evidence_quote":"Supplies the modular binomial congruence as the starting point and the deterministic polynomial-time baseline for complexity comparison."},{"cited_title":"On taking square roots and constructing quadratic nonresidues over finite fields,","cited_arxiv_id":null,"evidence_quote":"Supplies the construction that lets non-residues be specified implicitly, a building block for the generalized algorithms."},{"cited_title":"Constructing carmichael numbers which are strong pseudoprimes to several bases,","cited_arxiv_id":null,"evidence_quote":"Supplies large constructed Carmichael numbers used to test the algorithms and to verify primality of their prime factors."},{"cited_title":"PRP Records, Probable Primes Top 10000 ,","cited_arxiv_id":null,"evidence_quote":"Supplies the giant probable primes used to demonstrate the algorithms on numbers beyond 30,000 decimal digits."}],"review_version":1}