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
-
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 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 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.
- 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 EMMA LEHMER, "On the infinitude of Fibonacci pseudo-primes," Fibonacci Quart., v. 2, 1964, pp. 229-230.
- 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 D. E. G. MALM, "On Monte-Carlo primality tests," Notices Amer. Math. Soc., v. 24, 1977, p. A-529; Abstract #77T-A22.
- 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 B. ROSSER, "The n-th prime is greater than n $\log n$," Proc. London Math. Soc. (2), v. 45, 1939, pp. 21-44.
- 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
Additional Information
- © Copyright 1980 American Mathematical Society
- 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