New Proof of the recent Baseline Primality Conjecture
dc.contributor.author | Phatak, Dhananjay | |
dc.date.accessioned | 2023-09-08T21:35:13Z | |
dc.date.available | 2023-09-08T21:35:13Z | |
dc.date.issued | 2023-06-08 | |
dc.description.abstract | This document presents a theoretical proof of the Baseline Primality Conjecture (BPC) that was recently unveiled in [4, Part I]. The BPC identifies a new small set of conditions that are sufficient to decide the primality of any input integer N under test (see Section 2 for the exact statement of the BPC in the original form using algebraic integers; and Section 3 for an equivalent polynomial domain reformulation). The practical significance of the BPC is that it directly leads to ultra low complexity primality testing algorithms, wherein the number of bit-operations required is essentially a quadratic function of the bit-length of the input N [4]. More specifically, the Baseline Primality Result (BPR) demonstrates that after an/any integer in the closed interval [2,N −2] which is a Quadratic Non Residue (QNR) modulo-N is found; exactly 2 (Two, which is a small O(1) constant, independent of the bit-length of the input N) specific modular exponentiations are sufficient to determine whether N is a composite or a prime. The BPC was (and to this day continues to be) extensively tested numerically. Additionally, theoretical proofs of the BPC for several specific forms of the input N were also presented in [4]. However, at the time of the original publication [4], we were not able to complete a general theoretical proof of the BPC that covered all possible cases (i.e., forms) of the input N. A preliminary version of a general proof of the BPC was posted in the IEEE TechRxiv [5]. However, after the release of that document, the author solicited feedback from the renowned number theory expert Prof. Carl Pomerance in Jan. 2022. He pointed out a mistake [2] in that version of the proof (which appears in [5]). Since then, after more than an year of effort, a completely new proof has been developed in the period approximately from the 28th of January 2023 to the end of April 2023. To the best of our knowledge, this proof [6] is error free (and therefore will replace [5] in the near future.) A concise presentation of that new theoretical proof is the main focus as well as the main new contribution of this article. An auxiliary contribution is a clear and precise explanation of the intuition behind our approach and the illustration of how it leads to the new theoretical results developed in [4]. | en_US |
dc.description.uri | https://www.techrxiv.org/articles/preprint/Analytic_Proof_of_the_recent_Baseline_Primality_Conjecture/17139041/2 | en_US |
dc.format.extent | 29 pages | en_US |
dc.genre | journal articles | en_US |
dc.genre | preprints | en_US |
dc.identifier | doi:10.13016/m24t9g-e5eu | |
dc.identifier.uri | http://hdl.handle.net/11603/29628 | |
dc.language.iso | en_US | en_US |
dc.relation.isAvailableAt | The University of Maryland, Baltimore County (UMBC) | |
dc.relation.ispartof | UMBC Computer Science and Electrical Engineering Department Collection | |
dc.relation.ispartof | UMBC Faculty Collection | |
dc.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. | en_US |
dc.rights | Attribution 4.0 International (CC BY 4.0) | * |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | * |
dc.title | New Proof of the recent Baseline Primality Conjecture | en_US |
dc.type | Text | en_US |