Relaxing the size constraints on the criterion of Proth

Abstract

We add one condition to the theorem of Proth to extend its applicability to $N=k{2}^n+1$ where $2^n>N^{1/3}$ as opposed to the former constraint of $2^n>k$. This additional condition adds barely any complexity or time to the test and can furthermore be calculated concurrently. Furthermore, it maintains the biconditionality of the theorem and thus makes it readily applicable. A note on an extension of the primality test of Brillhart, Lehmer, and Selfridge is also made.

3 pages