Relaxing the size constraints on the criterion of Proth

2018/12/27 by Rao, Tejas R.
#11A51 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1812.11965

Abstract

We add one condition to the theorem of Proth to extend its applicability to N=k2ⁿ+1 where 2ⁿ>N^1/3 as opposed to the former constraint of 2ⁿ>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.

Related

• A primality test for Kpⁿ+1 numbers
• Deterministic Primality Proving on Proth Numbers
• Primality tests for specific classes of N=k⋅ 2^m ± 1
• Primality tests for Fermat numbers and 2^(2k+1)±2^(k+1)+1
• Primality tests for 2^kn-1 using elliptic curves