Analytic Proof of the recent Baseline Primality Conjecture

Abstract

This document presents an analytic proof of the Baseline Primality Conjecture (BPC) that was recently unveiled in [1, 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 [1]. 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.1 Additionally, analytic proofs of the BPC for several specific forms of the input N were also presented in [1], wherein the BPR was first unveiled. However, at the time of the original publication [1], we were not able to complete a general analytic proof of the BPC that covered all possible cases (i.e., forms) of the input N. We have now completed that vital task by developing a general analytic proof of the BPC using its polynomial domain reformulation. A concise presentation of that analytic proof is the main and narrow 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 [1].