New Proof of the recent Baseline Primality Conjecture

dc.contributor.authorPhatak, Dhananjay
dc.date.accessioned2023-09-08T21:35:13Z
dc.date.available2023-09-08T21:35:13Z
dc.date.issued2023-06-08
dc.description.abstractThis 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.urihttps://www.techrxiv.org/articles/preprint/Analytic_Proof_of_the_recent_Baseline_Primality_Conjecture/17139041/2en_US
dc.format.extent29 pagesen_US
dc.genrejournal articlesen_US
dc.genrepreprintsen_US
dc.identifierdoi:10.13016/m24t9g-e5eu
dc.identifier.urihttp://hdl.handle.net/11603/29628
dc.language.isoen_USen_US
dc.relation.isAvailableAtThe University of Maryland, Baltimore County (UMBC)
dc.relation.ispartofUMBC Computer Science and Electrical Engineering Department Collection
dc.relation.ispartofUMBC Faculty Collection
dc.rightsThis 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.rightsAttribution 4.0 International (CC BY 4.0)*
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/*
dc.titleNew Proof of the recent Baseline Primality Conjectureen_US
dc.typeTexten_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
bpcp-29april2023.pdf
Size:
475.71 KB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.56 KB
Format:
Item-specific license agreed upon to submission
Description: