Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The pseudoprimes to $ 25\cdot 10\sp{9}$


Authors: Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff
Journal: Math. Comp. 35 (1980), 1003-1026
MSC: Primary 10A40; Secondary 10-04, 10A25
DOI: https://doi.org/10.1090/S0025-5718-1980-0572872-7
MathSciNet review: 572872
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The odd composite $ n \leqslant 25 \cdot {10^9}$ such that $ {2^{n - 1}} \equiv 1\;\pmod n$ have been determined and their distribution tabulated. We investigate the properties of three special types of pseudoprimes: Euler pseudoprimes, strong pseudoprimes, and Carmichael numbers. The theoretical upper bound and the heuristic lower bound due to Erdös for the counting function of the Carmichael numbers are both sharpened. Several new quick tests for primality are proposed, including some which combine pseudoprimes with Lucas sequences.


References [Enhancements On Off] (What's this?)

  • [1] N. C. ANKENY, Review #4935, Math. Rev., v. 21, 1959, p. 905.
  • [2] R. J. BAILLIE & S. S. WAGSTAFF, JR., "Lucas pseudoprimes," Math. Comp., v. 35, 1980, pp. 000-000. MR 583518 (81j:10005)
  • [3] 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 52 #5546. MR 0384673 (52:5546)
  • [4] N. G. DE BRUIJN, "On the number of positive integers $ \leqslant x$ and free of prime factors $ > y$," Nederl. Acad. Wetensch. Proc. Ser. A, v. 54, 1951, pp. 50-60. Also II, ibid., v. 69, 1966, pp. 239-247. MR 13, 724; 34 #5770. MR 0046375 (13:724e)
  • [5] R. D. CARMICHAEL, "On composite numbers P which satisfy the Fermat congruence $ {a^{P - 1}} \equiv 1\;\bmod\, P$," Amer. Math. Monthly, v. 19, 1912, pp. 22-27. MR 1517641
  • [6] A. SCHINZEL, "On primitive prime factors of $ {a^n} - {b^n}$," Proc. Cambridge Philos. Soc., v. 58, 1962, pp. 555-562. MR 26 #1280. MR 0143728 (26:1280)
  • [7] P. ERDÖS, "On the normal number of prime factors of $ p - 1$ and some other related problems concerning Euler's $ \phi $-function," Quart. J. Math. Oxford Ser., v. 6, 1935, pp. 205-213.
  • [8] P. ERDÖS, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201-206. MR 18, 18. MR 0079031 (18:18e)
  • [9] P. ERDÖS & A. RÉNYI, "Probabilistic methods in group theory," J. Analyse Math., v. 14, 1965, pp. 127-138. MR 0202831 (34:2690)
  • [10] W. KNÖDEL, "Carmichaelsche Zahlen," Math. Nachr., v. 9, 1953, pp. 343-350. MR 14, 1062. MR 0055360 (14:1062f)
  • [11] EMMA LEHMER, "On the infinitude of Fibonacci pseudo-primes," Fibonacci Quart., v. 2, 1964, pp. 229-230.
  • [12] D. H. LEHMER, "On the converse of Fermat's theorem. II," Amer. Math. Monthly, v. 56, 1949, pp. 300-309. MR 10, 681. MR 0029925 (10:681g)
  • [13] D. H. LEHMER, "Strong Carmichael numbers," J. Austral. Math. Soc. Ser. A, v. 21, 1976, pp. 508-510. MR 0417032 (54:5093)
  • [14] D. E. G. MALM, "On Monte-Carlo primality tests," Notices Amer. Math. Soc., v. 24, 1977, p. A-529; Abstract #77T-A22.
  • [15] G. L. MILLER, "Riemann's Hypothesis and tests for primality," Proc. Seventh Annual ACM Symposium on the Theory of Computing, May 4-7, 1975, Albuquerque, pp. 234-239. MR 0480296 (58:470b)
  • [16] L. MIRSKY, "The number of representations of an integer as a sum of a prime and a k-free integer," Amer. Math. Monthly, v. 56, 1949, pp. 17-19. MR 10, 431. MR 0028335 (10:431e)
  • [17] E. A. PARBERRY, "On primes and pseudo-primes related to the Fibonacci sequence," Fibonacci Quart., v. 8, 1970, pp. 49-60. MR 41 #6809. MR 0262199 (41:6809)
  • [18] P. POULET, "Table des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu'à 100 000 000," Sphinx, v. 8, 1938, pp. 42-52. For corrections see Math. Comp., v. 25, 1971, pp. 944-945, MTE 485; v. 26, 1972, p. 814, MTE 497. MR 0655816 (58:31707)
  • [19] MICHAEL O. RABIN, "Probabilistic algorithms," in Symposium on New Directions and Recent Results in Algorithms and Complexity (J. F. Traub, Ed.), Academic Press, New York, 1976, pp. 21-39. MR 0464678 (57:4603)
  • [20] B. ROSSER, "The n-th prime is greater than n $ \log n$," Proc. London Math. Soc. (2), v. 45, 1939, pp. 21-44.
  • [21] A. ROTKIEWICZ, "Sur les progressions arithmétiques et géométriques formées de trois nombres pseudopremiers distincts," Acta Arith., v. 10, 1964, pp. 325-328. MR 30 #1995. MR 0171768 (30:1995)
  • [22] D. SHANKS, Solved and Unsolved Problems in Number Theory, 2nd ed., Chelsea, New York, 1978. MR 516658 (80e:10003)
  • [23] R. SOLOVAY & V. STRASSEN, "A fast Monte-Carlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 84-85. MR 0429721 (55:2732)
  • [24] J. D. SWIFT, "Table of Carmichael numbers to $ {10^9}$," Math. Comp., v. 29, 1975, pp. 338-339. Review #13. MR 0048492 (14:21f)
  • [25] K. SZYMICZEK, "On pseudoprimes which are products of distinct primes," Amer. Math. Monthly, v. 74, 1967, pp. 35-37. MR 34 #5746. MR 0205921 (34:5746)
  • [26] S. S. WAGSTAFF, JR., "Pseudoprimes and a generalization of Artin's conjecture." Acta Arith. (To appear.) MR 674829 (83m:10004)
  • [27] M. YORINAGA, "A technique of numerical production of a sequence of pseudo-prime numbers," Math. J. Okayama Univ., v. 19, 1976, pp. 1-4. MR 55 #5510. MR 0432522 (55:5510)
  • [28] M. YORINAGA, "On a congruencial property of Fibonacci numbers--numerical experiments," Math. J. Okayama Univ., v. 19, 1976, pp. 5-10. MR 55 #5513. MR 0432525 (55:5513)
  • [29] M. YORINAGA, "On a congruencial property of Fibonacci numbers--considerations and remarks," Math. J. Okayama Univ., v. 19, 1976, pp. 11-17. MR 55 #5514. MR 0432526 (55:5514)
  • [30] A. ROTKIEWICZ, "On the number of pseudoprimes $ \leqslant x$," Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., No. 381-409, 1972, pp. 43-45. MR 48 #256. MR 0321891 (48:256)
  • [31] A. ROTKIEWICZ, "On the pseudoprimes with respect to the Lucas sequences," Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., v. 21, 1973, pp. 793-797. MR 0332640 (48:10966)
  • [32] H. C. WILLIAMS, "On numbers analogous to the Carmichael numbers," Canad. Math. Bull., v. 20, 1977, pp. 133-143. MR 0447099 (56:5414)
  • [33] D. H. LEHMER, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp. 419-448. MR 1502953
  • [34] J. BRILLHART, J. TONASCIA & P. WEINBERGER, "On the Fermat quotient," Computers in Number Theory, Academic Press, London, 1971, pp. 213-222. MR 0314736 (47:3288)
  • [35] H. C. WILLIAMS, "Primality testing on a computer," Ars Combin., v. 5, 1978, pp. 127-185. MR 504864 (80d:10002)
  • [36] P. ERDÖS, "On the converse of Fermat's theorem," Amer. Math. Monthly, v. 56, 1949, pp. 623-624. MR 11, 331. MR 0032691 (11:331g)

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1980-0572872-7
Keywords: Pseudoprime, strong pseudoprime, Euler pseudoprime, Carmichael number, primality testing, Lucas sequence
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society