The pseudoprimes to

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 such that 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.

**[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 ,"*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 and free of prime factors ,"*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 ,"*Amer. Math. Monthly*, v. 19, 1912, pp. 22-27. MR**1517641****[6]**A. SCHINZEL, "On primitive prime factors of ,"*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 and some other related problems concerning Euler's -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*,"*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 ,"*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 ,"*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)**

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