Analytic Proof of the recent Baseline Primality Conjecture

Thumbnail Image

Files

bpcp.pdf (409.78 KB)

Links to Files

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

Permanent Link

https://dx.doi.org/10.36227/techrxiv.17139041.v1
 http://hdl.handle.net/11603/24067

Collections

UMBC Computer Science and Electrical Engineering Department
UMBC Faculty Collection

Author/Creator

Author/Creator ORCID

Date

2021-12-12

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