Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Some algorithms for prime testing using generalized Lehmer functions


Authors: H. C. Williams and J. S. Judd
Journal: Math. Comp. 30 (1976), 867-886
MSC: Primary 10A25; Secondary 10-04
DOI: https://doi.org/10.1090/S0025-5718-1976-0414473-6
MathSciNet review: 0414473
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] JOHN BRILLHART, D. H. LEHMER & J. L. SELFRIDGE, "New primality criteria and factorizations of $ {2^m} \pm 1$," Math. Comp., v. 29, 1975, pp. 620-647. MR 0384673 (52:5546)
  • [2] DOV JARDEN, Recurring Sequences, 3rd ed., Riveon Lemathematika, Jerusalem, 1973, pp. 41-59.
  • [3] D. H. LEHMER, "The economics of number theoretic computation," Computers in Number Theory, Academic Press, London and New York, 1971, pp. 1-9. MR 47 #3285. MR 0314733 (47:3285)
  • [4] D. H. LEHMER, "Use of Pierce functions for a primality test." (Unpublished notes.)
  • [5] EMMA LEHMER, "Criteria for cubic and quartic residuacity," Mathematika, v. 5, 1958, pp. 20-29. MR 20 #1668. MR 0095162 (20:1668)
  • [6] T. A. PIERCE, "The numerical factors of the arithmetic forms $ {\Pi ^n}(1 \pm \alpha _i^m)$," Ann. of Math. (2), v. 18, 1916, pp. 53-64. MR 1503584
  • [7] J. M. POLLARD, "Theorems on factorization and primality testing," Proc. Cambridge Philos. Soc., v. 76, 1974, pp. 521-528. MR 50 #6992. MR 0354514 (50:6992)
  • [8] J. L. SELFRIDGE & M. C. WUNDERLICH, "An efficient algorithm for testing large numbers for primality," Proc. Fourth Manitoba Conf. on Numerical Math. (Winnipeg, Man.,1974), Congr. Numer., No. 12, Utilitas Math., Winnipeg, Man., 1975, pp. 109-120. MR 51 #5461. MR 0369226 (51:5461)
  • [9] H. C. WILLIAMS, "A generalization of Lehmer's functions," Acta Arith., v. 29, 1976, pp. 315-341. MR 0412091 (54:220)
  • [10] H. C. WILLIAMS & J. S. JUDD, "Determination of the primality of N by using factors of $ {N^2} \pm 1$," Math. Comp., v. 30, 1976, pp. 157-172. MR 0396390 (53:257)
  • [11] M. C. WUNDERLICH & J. L. SELFRIDGE, "A design for a number theory package with an optimized trial division routine," Comm. ACM, v. 17, 1974, pp. 272-276.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 10A25, 10-04

Retrieve articles in all journals with MSC: 10A25, 10-04


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1976-0414473-6
Keywords: Primality testing, generalized Lehmer functions, Fibonacci numbers, Lucas numbers
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society