Determination of the primality of $N$ by using factors of $N^{2}\pm 1$

Authors:
H. C. Williams and J. S. Judd

Journal:
Math. Comp. **30** (1976), 157-172

MSC:
Primary 10A25

DOI:
https://doi.org/10.1090/S0025-5718-1976-0396390-3

MathSciNet review:
0396390

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- 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 https://doi.org/10.1090/S0025-5718-1975-0384673-1
DOV JARDEN, - D. H. Lehmer,
*Computer technology applied to the theory of numbers*, Studies in Number Theory, Math. Assoc. Amer. (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 https://doi.org/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 https://doi.org/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) Utilitas Math., Winnipeg, Man., 1975, pp. 109–120. Congr. Numer., No. XII. MR**0369226**
H. C. WILLIAMS, "A generalization of Lehmer’s functions,"

*Recurring Sequences*, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 41-59.

*Acta Arith.*(To appear).

Retrieve articles in *Mathematics of Computation*
with MSC:
10A25

Retrieve articles in all journals with MSC: 10A25

Additional Information

Keywords:
Primality testing,
Lucas functions,
Lehmer functions

Article copyright:
© Copyright 1976
American Mathematical Society