New Proof of the recent Baseline Primality Conjecture

Thumbnail Image

Files

bpcp-29april2023.pdf (475.71 KB)

Links to Files

https://www.techrxiv.org/articles/preprint/Analytic_Proof_of_the_recent_Baseline_Primality_Conjecture/17139041/2

Permanent Link

http://hdl.handle.net/11603/29628

Collections

UMBC Computer Science and Electrical Engineering Department
UMBC Faculty Collection

Author/Creator

Author/Creator ORCID

Date

2023-06-08

Type of Work

journal articles
preprints
Text

Department

Program

Citation of Original Publication

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.
Attribution 4.0 International (CC BY 4.0)

Subjects

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].