Some algorithms for prime testing using generalized Lehmer functions

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

doi:10.1090/S0025-5718-1976-0414473-6

Some algorithms for prime testing using generalized Lehmer functions
HTML articles powered by AMS MathViewer

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

Math. Comp. 30 (1976), 867-886 Request permission

Abstract:

Let N be an odd integer thought to be prime. The properties of special functions which are generalizations of the functions of Lehmer (Ann. of Math., v. 31, 1930, pp. 419-448) are used to develop algorithms that produce information concerning the possible prime divisors of N. It is shown how the factors of $N \pm 1,{N^2} + 1,{N^2} \pm N + 1$, together with the factor bounds on these numbers, may all be used to calculate lower bounds for the possible prime divisors of N. Frequently, these bounds are large enough that N may be shown to be prime. These tests were implemented on an IBM/370-158 computer and run on the pseudoprime divisors of the first 385 Fibonacci and Lucas numbers.

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

A. O. L. Atkin and B. J. Birch (eds.), Computers in number theory, Academic Press, London-New York, 1971. MR 0314733
Emma Lehmer, Criteria for cubic and quartic residuacity, Mathematika 5 (1958), 20–29. MR 95162, DOI 10.1112/S0025579300001303
Tracy A. Pierce, The numerical factors of the arithmetic forms $\prod _{i=1}^n(1\pm \alpha _i^m)$, Ann. of Math. (2) 18 (1916), no. 2, 53–64. MR 1503584, DOI 10.2307/2007169
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
H. C. Williams, A generalization of Lehmer’s functions, Acta Arith. 29 (1976), no. 4, 315–341. MR 412091, DOI 10.4064/aa-29-4-315-341
H. C. Williams and J. S. Judd, Determination of the primality of $N$ by using factors of $N^{2}\pm 1$, Math. Comp. 30 (1976), no. 133, 157–172. MR 396390, DOI 10.1090/S0025-5718-1976-0396390-3

Comm. ACM