PPT : New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues - Phatak, Dhananjay; Sherman, Alan T.; Houston, Steven D.; Henry, Andrew (My University, 2019)
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 (logN) 2 (polylog(logN)) ; 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 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 (logN) 3 (polylog(logN)) ; unconditionally, for any/all values of N. In Part/Article 2 , we present substantial experimental data that corroborate all the conjectures3 . For a striking/interesting example, wherein a combination of well-known state-of-the-art probabilistic primality tests applied together fail to detect a composite (which is easily/instantly detected correctly to be a composite number by the Baseline Primality Conjecture), see Section 23 in Part/Article 2. The data show that probabilistic primality tests in software platforms such as Maple are now extremely robust. I have not yet found a single composite number N that fools Maple’s Probabilistic primality tests; but gets correctly identified as a composite by our deterministic tests. Construction of (or a search for) such integers (assuming that those exist) is an interesting open problem which we plan to investigate in the future. 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 (i.e. for particular types of inputs N). We are optimistic that full analytic proofs of all conjectures introduced herein will be generated in the near future. That will be a big step toward moving the problem of primality detection into the category of problems that have been “solved and retired
Introducing Three Main New Primality Conjectures: Phatak’s Baseline Primality (PBP) Conjecture , and its extensions to Phatak’s Generalized Primality Conjecture (PGPC) , and Furthermost Generalized Primality Conjecture (FGPC) , and New Fast Primailty Testing Algorithms Based on the Conjectures and other results.
Substantial Experimental Data and Evidence
Keywords: Baseline Primality Conjecture (PBPC); Quadratic NON Residue ( QNR ) modulo-N; Primality Lemma 1; synergistic fusion