Determination of the primality of 𝑁 by using factors of 𝑁²±1
H. C. Williams, Jamie Judd · Mathematics of Computation · 1976
Algorithms are developed which can be used to determine the primality of a large integer N when a sufficient number of prime factors of N 2 + 1 {N^2} + 1 are known. A test for the primality of N which makes use of known factors of N − 1 , N + 1 N - 1,N + 1 and N 2 + 1 {N^2} + 1 and the factor bounds on these numbers is also presented. In order to develop the necessary theory, the properties of some functions which are a generalization of Lehmer functions are used. Several examples of numbers proved prime by employing these tests are given.