New Proof of the recent Baseline Primality Conjecture

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