2019/08/20 by Dhananjay Phatak, Dhananjay S. Phatak, Alan T. Sherman +6
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Number Theory (math.NT) #Symbolic Computation (cs.SC) #cs.CC #cs.CR #cs.DS #cs.SC #math.NT
paper · pdf · doi:10.48550/arxiv.1908.06964
a set of 3 companion articles.217 (two hundred and seventeen) pages including everything = table of contents, list of figures, list of tables and an acknowledgment at the end. There is no watermark or highlighted text. Only color is in hyper-links and figures
arxiv created 2019/08/20 · openalex publication_date 2019/08/20 · arxiv updated 2019/08/21 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
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.