Determination of the primality of 𝑁 by using factors of 𝑁²±1

Williams, H. C.; Judd, J. S.

doi:10.1090/S0025-5718-1976-0396390-3

Determination of the primality of $N$ by using factors of $N^{2}\pm 1$
HTML articles powered by AMS MathViewer

by H. C. Williams and J. S. Judd PDF

Math. Comp. 30 (1976), 157-172 Request permission

Abstract:

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$ are known. A test for the primality of N which makes use of known factors of $N - 1,N + 1$ and ${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.

References

John Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^{m}\pm 1$, Math. Comp. 29 (1975), 620–647. MR 384673, DOI 10.1090/S0025-5718-1975-0384673-1

Recurring Sequences

D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR 0246815
Michael A. Morrison, A note on primality testing using Lucas sequences, Math. Comp. 29 (1975), 181–182. MR 369234, DOI 10.1090/S0025-5718-1975-0369234-2
J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528. MR 354514, DOI 10.1017/s0305004100049252
J. L. Selfridge and M. C. Wunderlich, An efficient algorithm for testing large numbers for primality, Proceedings of the Fourth Manitoba Conference on Numerical Mathematics (Winnipeg, Man., 1974) Congr. Numer., No. XII, Utilitas Math., Winnipeg, Man., 1975, pp. 109–120. MR 0369226

Acta Arith.