The pseudoprimes to 25⋅10⁹

Pomerance, Carl; Selfridge, J. L.; Wagstaff, Samuel S.

doi:10.1090/S0025-5718-1980-0572872-7

The pseudoprimes to $25\cdot 10^{9}$
HTML articles powered by AMS MathViewer

by Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff PDF

Math. Comp. 35 (1980), 1003-1026 Request permission

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

Math. Rev.

Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
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
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^{P-1} \equiv 1 \operatorname {mod} P$, Amer. Math. Monthly 19 (1912), no. 2, 22–27. MR 1517641, DOI 10.2307/2972687
A. Schinzel, On primitive prime factors of $a^{n}-b^{n}$, Proc. Cambridge Philos. Soc. 58 (1962), 555–562. MR 143728, DOI 10.1017/S0305004100040561

Quart. J. Math. Oxford Ser.

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 10.1007/BF02806383
Walter Knödel, Carmichaelsche Zahlen, Math. Nachr. 9 (1953), 343–350 (German). MR 55360, DOI 10.1002/mana.19530090603

Fibonacci Quart.

D. H. Lehmer, On the converse of Fermat’s theorem. II, Amer. Math. Monthly 56 (1949), 300–309. MR 29925, DOI 10.2307/2306041
D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI 10.1017/s1446788700019364

Notices Amer. Math. Soc.

Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
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 10.2307/2305811
Edward A. Parberry, On primes and pseudo-primes 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, 944-945), Math. Comp. 26 (1972), 814. MR 655816, DOI 10.1090/S0025-5718-1972-0655816-4
Michael O. Rabin, Probabilistic algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976) Academic Press, New York, 1976, pp. 21–39. MR 0464678

n

Proc. London Math. Soc.

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 10.4064/aa-10-3-325-327
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 Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 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 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 10.4064/aa-41-2-141-150
Masataka Yorinaga, A technique of numerical production of a sequence of pseudo-prime 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 10.4153/CMB-1977-025-9
D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI 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 10.2307/2304732