Determination of the primality of by using factors of

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

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 are known. A test for the primality of *N* which makes use of known factors of and 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.

**[1]**John Brillhart, D. H. Lehmer, and J. L. Selfridge,*New primality criteria and factorizations of 2^{𝑚}±1*, Math. Comp.**29**(1975), 620–647. MR**0384673**, https://doi.org/10.1090/S0025-5718-1975-0384673-1**[2]**DOV JARDEN,*Recurring Sequences*, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 41-59.**[3]**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****[4]**Michael A. Morrison,*A note on primality testing using Lucas sequences*, Math. Comp.**29**(1975), 181–182. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0369234**, https://doi.org/10.1090/S0025-5718-1975-0369234-2**[5]**J. M. Pollard,*Theorems on factorization and primality testing*, Proc. Cambridge Philos. Soc.**76**(1974), 521–528. MR**0354514****[6]**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****[7]**H. C. WILLIAMS, "A generalization of Lehmer's functions,"*Acta Arith.*(To appear).

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

Retrieve articles in all journals with MSC: 10A25

Additional Information

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

Keywords:
Primality testing,
Lucas functions,
Lehmer functions

Article copyright:
© Copyright 1976
American Mathematical Society