PPT : New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues
Loading...
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2019-08-20
Type of Work
Department
Program
Citation of Original Publication
Dhananjay Phatak; Alan T. Sherman; Steven D. Houston; Andrew Henry; PPT: New Low Complexity Deterministic Primality Tests Leveraging Explicit and Implicit Non-Residues. A Set of Three Companion Manuscripts 2019; Cite as:arXiv:1908.06964v1 [cs.CR]
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
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
(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