Pith. sign in

REVIEW 5 major objections 5 minor 60 references

PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts

T0 review · 5 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Two modular congruences, one using a quadratic non-residue, may certify primality if the paper's conjecture holds.

desk verdict 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. read the letter →

arxiv 1908.06964 v1 pith:UPMFNGL5 submitted 2019-08-20 cs.CR cs.CCcs.DScs.SCmath.NT

Dhananjay Phatak , Alan T. Sherman , Steven D. Houston , Andrew Henry This is my paper · ORCID
classification cs.CRcs.CCcs.DScs.SCmath.NT MSC 11Y1111A1568W40
keywords primalitytestingquadraticnon-residueEulercriterionmodularbinomialcongruencecyclotomicpolynomialsCarmichaelnumbersdeterministicpolynomialtimestrongpseudoprimetest
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

5 major / 5 minor

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.

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 (5)
  1. [Abstract and Section 13.1] 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.
  2. [Section 2 and Section 4] 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.
  3. [Section 9.2, Eqs. (78) and (79)] 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.
  4. [Section 5.2 and Section 5.3] 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.
  5. [Part 2, Sections 20-24] 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.
minor comments (5)
  1. [Section 11, line 23] The pseudocode refers to 'PGP Conjecture', which appears to be a typo for 'PGPC' (Phatak's Generalized Primality Conjecture).
  2. [Section 16 and Part 2, Section 23] 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.
  3. [Section 5.4, Reason 1] The nested numbering '5.1, 5.2, 5.3' inside Reason 1 conflicts with the section numbering and makes the text harder to follow.
  4. [Equations (16)-(20)] 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.
  5. [Throughout] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the conjectures are used as open premises with explicitly conditional proofs, and all experimental support comes from external benchmark sets.

full rationale

The paper's derivation chain is not circular. The Baseline Primality Conjecture (PBPC), Generalized Primality Conjecture (PGPC), and Furthermost Generalized Primality Conjecture (FGPC) are stated as unproved conjectures and are not derived from the algorithm outputs; the correctness proofs are explicitly conditional (e.g., Section 4: 'if the PBP Conjecture is true; then the PPTA_EQNR Algorithm works correctly', and Section 12: 'assuming that PGP Conjecture is true'). No free parameters are fitted to data: the algorithms evaluate fixed congruences (ECC, BCC, PGPC conditions 1-4, FGPC condition), and the experimental validation is performed against external benchmark sets (Pinch's exhaustive Carmichael/pseudoprime lists, Arnault's constructed composites, probable-prime records), not against a training subset that is then 'predicted'. The one self-citation to the companion Part/Article 3 ([11]) supports only the trivial forward direction and the status of partial analytic proofs; it is not load-bearing for the conjectures themselves. The abstract's O((log N)^3) claim is not established by the Section 11 algorithm as written (which checks the four PGPC conditions and hence has the O((log N)^4) bound of PL6; PL7 is conditional on FGPC), but this is a correctness/consistency gap, not a circular reduction. Cross-validation between the baseline and generalized conjectures (Section 15.4) is described as a consistency check, and both are independently tested against external data, so it does not make either conjecture an input to itself.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central results rest on four explicit conjectures, all new and unproven in full generality. No numerical constants are fitted to the experimental data, and no new mathematical objects beyond the constructed cyclotomic-derived polynomials are introduced.

assumptions (4)
  • ad hoc to paper Phatak Baseline Primality Conjecture: conditions C-1 through C-5 imply N is prime.
    Stated in Section 2 and used as the correctness basis for PPTA_EQNR in Section 4; no complete proof is given.
  • ad hoc to paper Auxiliary Primality Conjecture 1, identities (78) and (79) for powers of x modulo Upsilon_m and Psi_m.
    Introduced in Section 9.2 as a conjecture; only partial proofs are provided, but the identities are needed for PGPC conditions 3 and 4.
  • ad hoc to paper Phatak Generalized Primality Conjecture (PGPC): the four congruences together imply N is prime.
    Stated in Section 10; the PPTA_INR algorithm in Section 11 relies on this conjecture for correctness.
  • ad hoc to paper Furthermost Generalized Primality Conjecture (FGPC): a single Psi_m-based binomial congruence implies N is prime.
    Stated in Section 13.1 as the most aggressive conjecture; it underpins the claimed O((log N)^3) worst-case bound in PL7.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts." pith.science (2026). https://pith.science/paper/UPMFNGL5

@misc{pith2026190806964,
  author       = {Pith},
  title        = {Pith review of: PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UPMFNGL5}},
  note         = {Machine review of arXiv:1908.06964}
}
read the original abstract

In this set of three companion manuscripts/articles, we unveil our new results on primality testing and reveal new primality testing algorithms enabled by those results. The results have been classified (and referred to) as lemmas/corollaries/claims whenever we have complete analytic proof(s); otherwise the results are introduced as conjectures. In Part/Article 1, we start with the Baseline Primality Conjecture~(PBPC) which enables deterministic primality detection with a low complexity = O((log N)^2) ; when an explicit value of a Quadratic Non Residue (QNR) modulo-N is available (which happens to be the case for an overwhelming majority = 11/12 = 91.67% of all odd integers). We then demonstrate Primality Lemma PL-1, which reveals close connections between the state-of-the-art Miller-Rabin method and the renowned Euler-Criterion. This Lemma, together with the Baseline Primality Conjecture enables a synergistic fusion of Miller-Rabin iterations and our method(s), resulting in hybrid algorithms that are substantially better than their components. Next, we illustrate how the requirement of an explicit value of a QNR can be circumvented by using relations of the form: Polynomial(x) mod N = 0 ; whose solutions implicitly specify Non Residues modulo-N. We then develop a method to derive low-degree canonical polynomials that together guarantee implicit Non Residues modulo-N ; which along with the Generalized Primality Conjectures enable algorithms that achieve a worst case deterministic polynomial complexity = O( (log N)^3 polylog(log N)) ; unconditionally ; for any/all values of N. In Part/Article 2 , we present substantial experimental data that corroborate all the conjectures. No counter example has been found. Finally in Part/Article 3, we present analytic proof(s) of the Baseline Primality Conjecture that we have been able to complete for some special cases.

Figures

Figures reproduced from arXiv: 1908.06964 by the authors.

Figure 1
Figure 1. Illustration of one possible partitioning of all paths in the proof-space. The solid line-styled blue colored box indicates the region wherein all cases that fall within that box have been analytically proved (see Section 32 in Companion Manuscript Part/Article 3 for details). The red colored box with dash-dots line-style indicates the region where we have partial proofs (i.e. not all cases within that box have been… view at source ↗
Figure 2
Figure 2. Fraction of cases where a search for a QNR is needed (Y1 axis on the left) ; and the average number of iterations needed to find a QNR q by a brute-force-stepping thru primes from 3 onward (Y2 axis on the right) In this Figure, there are two distinct Y axes corresponding to two distinct plots. The red colored plot uses the Y1-axis on the left side to indicate the fraction of values that needed a search for a QNR . T… view at source ↗
Figure 3
Figure 3. Set 1 : Number of cases resolved by individual mechanisms within the PPTA_EQNR Algorithm [PITH_FULL_IMAGE:figures/full_fig_p095_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Set 1 : Fractions resolved by individual mechanisms within the PPTA_EQNR Algorithm illustrated with a box-plot. In this Figure there is only a single Y axis on the left. Also note that the values (in the BCC column) are multiplied by a factor 10 in order to make them a…
Figure 5
Figure 5. Figure 5: illustrates the data from [PITH_FULL_IMAGE:figures/full_fig_p100_5.png]
Figure 6
Figure 6. Figure 6: illustrates the raw counts (i.e., the integers in [PITH_FULL_IMAGE:figures/full_fig_p101_6.png]
Figure 7
Figure 7. Figure 7: Set 4 : Fractions resolved by individual mechanisms within the PPTA_EQNR Algorithm illustrated with a box-plot. This figure has only one common Y axis (shown on the left). In this case, there is no scaling of the BCC fractions. We conclude this section by identifying t…
Figure 8
Figure 8. Figure 8: illustrates the square roots that can occur in meta–path I; which starts at the exponent = (M −1) Level 2 Level 1 √ = +1 √ = −1 Box M_C [1 + √q] (M−1 4 ) = ±x2 where ; [1− √q] (M−1 4 ) = ±x2 and [1−q] (M−1 4 ) = (x2) 2 = −1 Box M_D [1 + √q] (M−1 4 ) = ±y2 √q where ; ⇒ …
Figure 9
Figure 9. Figure 9: Illustration of the two types of paths feasible in the third level: under Box M_C If M−1 4  is an even number; then Let I3 = (M −1) 8 (280) and Let (1 + √q ) I3 = (x3 +y3 √ q) mod P (281) ⇒ (x3 +y3 √ q) 2 = (1 + √q ) (M−1 4 ) = x2 Which leads to Box M_E in [PITH_FUL…
Figure 10
Figure 10. Figure 10: Illustration of the third type of path that occurs at the third level under Box M_D Finally, we illustrate a more general type of path (which we call “path type (iii)” in [PITH_FULL_IMAGE:figures/full_fig_p201_10.png]
Figure 11
Figure 11. Figure 11: illustrates the square roots that can occur in meta–path II; which starts at the exponent = (N + 1) Level 1 paths under Box N_Top Next, we indicate how to establish the relations shown in each box in [PITH_FULL_IMAGE:figures/full_fig_p203_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages

  1. [1]

    Mathematics research page,

    R. G. E. Pinch, “Mathematics research page,” Last modified: 2011, http://www.chalcedon.demon.co.uk/rgep/rcam.html

    work page 2011

  2. [2]

    Prime and prejudice: Primality testing under adversarial conditions,

    M. R. Albrecht, J. Massimo, K. G. Paterson, and J. Somorovsky, “Prime and prejudice: Primality testing under adversarial conditions,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security . ACM, 2018, pp. 281–298

    work page 2018

  3. [3]

    Euler’s criterion,

    Wikipedia, “Euler’s criterion,” Last modified: Nov. 2018, https://en.wikipedia.org/wiki/Euler’s_criterion

    work page 2018

  4. [4]

    W. J. LeVeque, Elementary theory of numbers . Courier Corporation, 1990

    work page 1990

  5. [5]

    Shoup,A computational introduction to number theory and algebra

    V . Shoup,A computational introduction to number theory and algebra . Cambridge university press, 2009

    work page 2009

  6. [6]

    Crandall and C

    R. Crandall and C. B. Pomerance, Prime numbers: a computational perspective . Springer Science & Business Media, 2006, vol. 182

    work page 2006

  7. [7]

    Jacobi Symbol,

    Wikipedia, “Jacobi Symbol,” Last modified: Nov. 2018, https://en.wikipedia.org/wiki/Jacobi_symbol

    work page 2018

  8. [8]

    Jacobi Symbol,

    P. Corn and J. Khim ; Brilliant.org, “Jacobi Symbol,” Last modified: Nov. 2018, https://brilliant.org/wiki/jacobi-symbol

    work page 2018

Show all 60 references
  1. [9]

    Maplesoft,

    “Maplesoft,” Last modified : 2018, . [Online]. Available: https://maplesoft.com/

    2018

  2. [10]

    PRIMES is in P,

    M. Agrawal, N. Kayal, and N. Saxena, “PRIMES is in P,”Annals of mathematics, pp. 781–793, 2004

    2004

  3. [11]

    D. S. Phatak, et. al., “PPT : New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. PART/Article 3 : Analytic Proofs of Baseline Primality Conjecture for Special Cases,” August 2019, The overall document is a set of 3 companion articles

    2019

  4. [12]

    The distribution of quadratic and higher residues,

    H. Davenport and P. Erdos, “The distribution of quadratic and higher residues,” Publ. Math. Debrecen, vol. 2, no. 3–4, pp. 252–265, 1952

    1952

  5. [13]

    The least quadratic non residue,

    N. C. Ankeny, “The least quadratic non residue,” Annals of mathematics, pp. 65–72, 1952. 80

    1952

  6. [14]

    The distribution of quadratic residues and non-residues,

    D. A. Burgess, “The distribution of quadratic residues and non-residues,”Mathematika, vol. 4, no. 2, pp. 106–112, 1957

    1957

  7. [15]

    Lower bounds for least quadratic non-residues,

    S. Graham and C. Ringrose, “Lower bounds for least quadratic non-residues,” inAnalytic number theory. Springer, 1990, pp. 269–309

    1990

  8. [16]

    Constructing nonresidues in finite fields and the Extended Riemann Hypothesis,

    J. Buchmann and V . Shoup, “Constructing nonresidues in finite fields and the Extended Riemann Hypothesis,” Mathematics of Computation of the American Mathematical Society , vol. 65, no. 215, pp. 1311–1326, 1996

    1996

  9. [17]

    On the distribution of quadratic residues and nonresidues modulo a prime number,

    R. Peralta, “On the distribution of quadratic residues and nonresidues modulo a prime number,” Mathematics of Computation, vol. 58, no. 197, pp. 433–440, 1992

    1992

  10. [18]

    Quadratic nonresidues and applications,

    N. A. Carella, “Quadratic nonresidues and applications,” 2003, technical Report No. 190, School of Computer and Information Systems, PACE University, 1 Pace Plaza, New York, NY 10038

    2003

  11. [19]

    Complexity of computing quadratic nonresidues,

    N. Carella, “Complexity of computing quadratic nonresidues,” arXiv preprint math/0502214, 2005

    2005 arXiv

  12. [20]

    On taking square roots and constructing quadratic nonresidues over finite fields,

    T.-W. Sze, “On taking square roots and constructing quadratic nonresidues over finite fields,” preprint, 2007, PDF copy available via Citeseer at the link http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.4571&rep=rep1&type=pdf

    2007

  13. [21]

    The least quadratic nonresidue, and the square root barrier,

    T. Tao, “The least quadratic nonresidue, and the square root barrier,” 2009, PDF copy available at the link https://terrytao.wordpress.com/2009/08/18/the-least-quadratic-nonresidue-and-the-square-root- barrier/

    2009

  14. [22]

    On taking square roots without quadratic nonresidues over finite fields,

    T.-W. Sze, “On taking square roots without quadratic nonresidues over finite fields,”Mathematics of Computation, vol. 80, no. 275, pp. 1797–1811, 2011

    2011

  15. [23]

    Conditional bounds for the least quadratic non- residue and related problems,

    Y . Lamzouri, X. Li, and K. Soundararajan, “Conditional bounds for the least quadratic non- residue and related problems,” Mathematics of Computation, vol. 84, no. 295, pp. 2391–2412, 2015

    2015

  16. [24]

    The elliott–halberstam conjecture implies the vinogradov least quadratic nonresidue conjecture,

    T. Tao, “The elliott–halberstam conjecture implies the vinogradov least quadratic nonresidue conjecture,” Algebra & Number Theory, vol. 9, no. 4, pp. 1005–1034, 2015

    2015

  17. [25]

    PRIMES is in P

    M. Dietzfelbinger, Primality testing in polynomial time: from randomized algorithms to" PRIMES is in P". Springer, 2004, vol. 3000

    2004

  18. [26]

    Primality testing with gaussian periods,

    H. W. Lenstra Jr. and C. Pomerance, “Primality testing with gaussian periods,” inFSTTCS, 2002, p. 1

    2002

  19. [27]

    Primality testing with gaussian periods,

    H. Lenstra Jr. and C. Pomerance, “Primality testing with gaussian periods,” Last modified : 2008, . [Online]. Available: https://math.dartmouth.edu/~carlp/aks240817.pdf

    2008

  20. [28]

    Proving primality in essentially quartic random time,

    D. Bernstein, “Proving primality in essentially quartic random time,”Mathematics of computation, vol. 76, no. 257, pp. 389–403, 2007. Part/Article 1 – page 81

    2007

  21. [29]

    On the complexity of multiplication in finite fields,

    A. Lempel, G. Seroussi, and S. Winograd, “On the complexity of multiplication in finite fields,” Theoretical Computer Science, vol. 22, no. 3, pp. 285–296, 1983

    1983

  22. [30]

    Hensel lifting and polynomial division,

    M. Agrawal, “Hensel lifting and polynomial division,” Lecture 17, CS 681: Computational Number Theory and Algebra, 2005, available at the web-link https://www.cse.iitk.ac.in/users/manindra/CS681/2005/Lecture17.pdf

    2005

  23. [31]

    Sparse polynomial multiplication and division in maple 14,

    M. Monagan and R. Pearce, “Sparse polynomial multiplication and division in maple 14,”ACM Communications in Computer Algebra, vol. 44, no. 3/4, pp. 205–209, 2011

    2011

  24. [32]

    On newton–raphson iteration for multiplicative inverses modulo prime powers,

    J.-G. Dumas, “On newton–raphson iteration for multiplicative inverses modulo prime powers,” IEEE Transactions on Computers, vol. 63, no. 8, pp. 2106–2109, 2013

    2013

  25. [33]

    Faster polynomial multiplication over finite fields using cyclotomic coefficient rings,

    D. Harvey and J. van der Hoeven, “Faster polynomial multiplication over finite fields using cyclotomic coefficient rings,” Journal of Complexity, 2019

    2019

  26. [34]

    Carmichael numbers,

    R. G. E. Pinch, “Carmichael numbers,” Last modified: 2008, http://www.chalcedon.demon.co.uk/rgep/carpsp.html

    2008

  27. [35]

    Strong pseudoprime,

    Wikipedia, “Strong pseudoprime,” Last modified: Oct. 2018, https://en.wikipedia.org/wiki/Strong_pseudoprime

    2018

  28. [36]

    Miller–Rabin primality test,

    ——, “Miller–Rabin primality test,” Last modified: Dec. 2018, https://en.wikipedia.org/wiki/Miller_Rabin_primality_test

    2018

  29. [37]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009

    2009

  30. [38]

    Cyclotomic polynomial,

    Wikipedia, “Cyclotomic polynomial,” Last modified: 2019, https://en.wikipedia.org/wiki/Cyclotomic_polynomial

    2019

  31. [39]

    Primorial,

    ——, “Primorial,” last updated in 2019, https://en.wikipedia.org/wiki/Primorial

    2019

  32. [40]

    Parhami, Computer Arithmetic Algorithms and Hardware Designs

    B. Parhami, Computer Arithmetic Algorithms and Hardware Designs . Oxford University Press, 2000

    2000

  33. [41]

    New distributed algorithms for fast sign detection in residue number systems (rns),

    D. S. Phatak and S. D. Houston, “New distributed algorithms for fast sign detection in residue number systems (rns),” Journal of Parallel and Distributed Computing, vol. 97, pp. 78–95, 2016

    2016

  34. [42]

    Bertrand’s postulate,

    Wikipedia, “Bertrand’s postulate,” Last modified: May 2019, https://en.wikipedia.org/wiki/Bertrand’s_postulate

    2019

  35. [43]

    Prime–counting function,

    ——, “Prime–counting function,” last updated in 2019, https://en.wikipedia.org/wiki/Prime-counting_function

    2019

  36. [44]

    Baillie–PSW primality test,

    ——, “Baillie–PSW primality test,” Last modified: Oct. 2018, https://en.wikipedia.org/wiki/Baillie–PSW_primality_test

    2018

  37. [45]

    Quadratic residue,

    ——, “Quadratic residue,” Last modified: Aug. 2018, https://en.wikipedia.org/wiki/Quadratic_residue. Part/Article 1 – page 82

    2018

  38. [46]

    Carmichael numbers in number rings,

    G. A. Steele, “Carmichael numbers in number rings,”Journal of Number Theory , vol. 128, no. 4, pp. 910–917, 2008

    2008

  39. [47]

    Constructing carmichael numbers which are strong pseudoprimes to several bases,

    F. Arnault, “Constructing carmichael numbers which are strong pseudoprimes to several bases,” Journal of Symbolic Computation, vol. 20, no. 2, pp. 151–161, 1995

    1995

  40. [48]

    The carmichael numbers up to 1021,

    R. G. Pinch, “The carmichael numbers up to 1021,” in Proceedings of Conference on Algorithmic Number Theory 2007, 2007, p. 129

    2007

  41. [49]

    PRP Records, Probable Primes Top 10000 ,

    Lifchitz, Henri and Lifchitz, Renaud, “PRP Records, Probable Primes Top 10000 ,” Last modified: Jan. 2019, http://www.primenumbers.net/prptop/prptop.php

    2019

  42. [50]

    A014233 : Smallest odd number for which Miller-Rabin primality test on bases≤n-th prime does not reveal compositeness

    Jud, McCranie and Sloane, N. J. A. and Joerg, Arndt and OEIS foundation staff, “ A014233 : Smallest odd number for which Miller-Rabin primality test on bases≤n-th prime does not reveal compositeness.” Last modified: Dec. 2018, https://oeis.org/A014233

    2018

  43. [51]

    A001262 : Strong pseudoprimes to base 2,

    N. J. A. Sloane and OEIS foundation staff , “A001262 : Strong pseudoprimes to base 2,” Last modified: Jan. 2019, https://oeis.org/A001262

    2019

  44. [52]

    Higher-order Carmichael numbers,

    E. Howe, “Higher-order Carmichael numbers,”Mathematics of computation, vol. 69, no. 232, pp. 1711–1719, 2000

    2000

  45. [53]

    Higher-order carmichael numbers,

    ——, “Higher-order carmichael numbers,” 2006, colorado State University Mathematics Colloquium, December. [Online]. Available: http://ewhowe.com/talks/FortCollins.pdf

    2006

  46. [54]

    Pepin’s Test,

    Wikipedia, “Pepin’s Test,” Last modified: Aug. 2018, https://en.wikipedia.org/wiki/Pepin’s_test

    2018

  47. [55]

    Fermat number,

    ——, “Fermat number,” Last modified: Dec. 2018, https://en.wikipedia.org/wiki/Fermat_number

    2018

  48. [56]

    Mersenne prime,

    ——, “Mersenne prime,” Last modified: Jan. 2019, https://en.wikipedia.org/wiki/Mersenne_prime

    2019

  49. [57]

    Lucas–Lehmer primality test,

    ——, “Lucas–Lehmer primality test,” Last modified: Dec. 2018, https://en.wikipedia.org/Lucas–Lehmer_primality_test. Part/Article 1 – page 83 § Section 17 : Article 1 – Appendix 1 Basic Number Theory Background Fact 3 : LetN >1 be an odd positive integer that is not a square of s...

    2018

  50. [58]

    Decimal digit length of each number should not be more than about 60,000 digits (otherwise it takes a day or longer just to execute the 2 modular exponentiations required in the PPTA_EQNR algorithm)

  51. [59]

    probable prime

    The formula for the numbers should be as diverse as possible. The numbers we picked are listed in Table 11. Each of these numbers was tested with the PPTA_EQNR algorithm. The relevant parameters of each run together with the final output (a decision indicating whetherN is a pri...

    2018

  52. [60]

    conjugate

    = (1−2) =−1 mod P (356) and in an analogous manner, the corresponding “conjugate” relation [1− √ 2] (N+1) =−1 mod P (357) Since (N + 1)is even; and−1 is a QR (Quadratic-Residue) the square root of Relation (356) yields (1 + √ 2) (N +1 2 ) =s mod P (358) where ;s is an integer ...

    2018

Pith tools

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