The pseudoprimes to $25\cdot 10^{9}$
Authors:
Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff
Journal:
Math. Comp. 35 (1980), 10031026
MSC:
Primary 10A40; Secondary 1004, 10A25
DOI:
https://doi.org/10.1090/S00255718198005728727
MathSciNet review:
572872
Fulltext 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.

N. C. ANKENY, Review #4935, Math. Rev., v. 21, 1959, p. 905.
 Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI https://doi.org/10.1090/S00255718198005835186
 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 https://doi.org/10.1090/S00255718197503846731
 N. G. de Bruijn, On the number of positive integers $\leq x$ and free of prime factors $>y$, Nederl. Acad. Wetensch. Proc. Ser. A. 54 (1951), 50–60. MR 0046375
 R. D. Carmichael, On Composite Numbers $P$ Which Satisfy the Fermat Congruence $a^{P1} \equiv 1 \operatorname {mod} P$, Amer. Math. Monthly 19 (1912), no. 2, 22–27. MR 1517641, DOI https://doi.org/10.2307/2972687
 A. Schinzel, On primitive prime factors of $a^{n}b^{n}$, Proc. Cambridge Philos. Soc. 58 (1962), 555–562. MR 143728 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. 205213.
 P. Erdös, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201–206. MR 79031
 P. Erdős and A. Rényi, Probabilistic methods in group theory, J. Analyse Math. 14 (1965), 127–138. MR 202831, DOI https://doi.org/10.1007/BF02806383
 Walter Knödel, Carmichaelsche Zahlen, Math. Nachr. 9 (1953), 343–350 (German). MR 55360, DOI https://doi.org/10.1002/mana.19530090603 EMMA LEHMER, "On the infinitude of Fibonacci pseudoprimes," Fibonacci Quart., v. 2, 1964, pp. 229230.
 D. H. Lehmer, On the converse of Fermat’s theorem. II, Amer. Math. Monthly 56 (1949), 300–309. MR 29925, DOI https://doi.org/10.2307/2306041
 D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI https://doi.org/10.1017/s1446788700019364 D. E. G. MALM, "On MonteCarlo primality tests," Notices Amer. Math. Soc., v. 24, 1977, p. A529; Abstract #77TA22.
 Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI https://doi.org/10.1016/S00220000%2876%29800438
 L. Mirsky, The number of representations of an integer as the sum of a prime and a $k$free integer, Amer. Math. Monthly 56 (1949), 17–19. MR 28335, DOI https://doi.org/10.2307/2305811
 Edward A. Parberry, On primes and pseudoprimes related to the Fibonacci sequence, Fibonacci Quart. 8 (1970), no. 1, 49–60. MR 262199
 J. D. Swift, Errata to D. H. Lehmer’s “Table errata: ‘Table des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu’à 100.000.000’ by P. Poulet” (Math. Comp. 25 (1971), no. 116, 944945), Math. Comp. 26 (1972), 814. MR 655816, DOI https://doi.org/10.1090/S00255718197206558164
 Michael O. Rabin, Probabilistic algorithms, Algorithms and complexity (Proc. Sympos., CarnegieMellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR 0464678 B. ROSSER, "The nth prime is greater than n $\log n$," Proc. London Math. Soc. (2), v. 45, 1939, pp. 2144.
 A. Rotkiewicz, Sur les progressions arithmétiques et géométriques formées de trois nombres pseudopremiers distincts, Acta Arith. 10 (1964), 325–328 (French). MR 171768, DOI https://doi.org/10.4064/aa103325327
 Daniel Shanks, Solved and unsolved problems in number theory, 2nd ed., Chelsea Publishing Co., New York, 1978. MR 516658
 R. Solovay and V. Strassen, A fast MonteCarlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI https://doi.org/10.1137/0206006
 H. J. A. Duparc, On Carmichael numbers, Simon Stevin 29 (1952), 21–24. MR 48492
 K. Szymiczek, On pseudoprimes which are products of distinct primes, Amer. Math. Monthly 74 (1967), no. 1, 35–37. MR 205921, DOI https://doi.org/10.2307/2314051
 Samuel S. Wagstaff Jr., Pseudoprimes and a generalization of Artin’s conjecture, Acta Arith. 41 (1982), no. 2, 141–150. MR 674829, DOI https://doi.org/10.4064/aa412141150
 Masataka Yorinaga, A technique of numerical production of a sequence of pseudoprime numbers, Math. J. Okayama Univ. 19 (1976/77), no. 1, 1–4. MR 432522
 Masataka Yorinaga, On a congruencial property of Fibonacci numbers–numerical experiments, Math. J. Okayama Univ. 19 (1976/77), no. 1, 5–10. MR 432525
 Masataka Yorinaga, On a congruencial property of Fibonacci numbers–considerations and remarks, Math. J. Okayama Univ. 19 (1976/77), no. 1, 11–17. MR 432526
 Andrzej Rotkiewicz, On the number of pseudoprimes $\leq x$, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 381–409 (1972), 43–45. MR 0321891
 A. Rotkiewicz, On the pseudoprimes with respect to the Lucas sequences, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 21 (1973), 793–797 (English, with Russian summary). MR 332640
 H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133–143. MR 447099, DOI https://doi.org/10.4153/CMB19770259
 D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI https://doi.org/10.2307/1968235
 J. Brillhart, J. Tonascia, and P. Weinberger, On the Fermat quotient, Computers in number theory (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969) Academic Press, London, 1971, pp. 213–222. MR 0314736
 H. C. Williams, Primality testing on a computer, Ars Combin. 5 (1978), 127–185. MR 504864
 P. Erdös, On the converse of Fermat’s theorem, Amer. Math. Monthly 56 (1949), 623–624. MR 32691, DOI https://doi.org/10.2307/2304732
Retrieve articles in Mathematics of Computation with MSC: 10A40, 1004, 10A25
Retrieve articles in all journals with MSC: 10A40, 1004, 10A25
Additional Information
Keywords:
Pseudoprime,
strong pseudoprime,
Euler pseudoprime,
Carmichael number,
primality testing,
Lucas sequence
Article copyright:
© Copyright 1980
American Mathematical Society