On the number of false witnesses for a composite number
HTML articles powered by AMS MathViewer
- by Paul Erdős and Carl Pomerance PDF
- Math. Comp. 46 (1986), 259-279 Request permission
Abstract:
If a is not a multiple of n and ${a^{n - 1}}\;\nequiv \;1\bmod n$, then n must be composite and a is called a "witness" for n. Let $F(n)$ denote the number of "false witnesses" for n, that is, the number of $a\bmod n$ with ${a^{n - 1}} \equiv 1\bmod n$. Considered here is the normal and average size of $F(n)$ for n composite. Also considered is the situation for the more stringent Euler and strong pseudoprime tests.References
- A. O. L. Atkin and R. G. Larson, On a primality test of Solovay and Strassen, SIAM J. Comput. 11 (1982), no. 4, 789–791. MR 677668, DOI 10.1137/0211064
- 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
- Antal Balog, $p+a$ without large prime factors, Seminar on number theory, 1983–1984 (Talence, 1983/1984) Univ. Bordeaux I, Talence, 1984, pp. Exp. No. 31, 5. MR 784077
- P. T. Bateman, C. Pomerance, and R. C. Vaughan, On the size of the coefficients of the cyclotomic polynomial, Topics in classical number theory, Vol. I, II (Budapest, 1981) Colloq. Math. Soc. János Bolyai, vol. 34, North-Holland, Amsterdam, 1984, pp. 171–202. MR 781138
- 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
- P. D. T. A. Elliott, Probabilistic number theory. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 239, Springer-Verlag, New York-Berlin, 1979. Mean-value theorems. MR 551361, DOI 10.1007/978-1-4612-9989-9 P. Erdös, "On the normal number of prime factors of $p - 1$ and some related questions 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, Some asymptotic formulas in number theory, J. Indian Math. Soc. (N.S.) 12 (1948), 75–78. MR 29406
- Étienne Fouvry, Théorème de Brun-Titchmarsh: application au théorème de Fermat, Invent. Math. 79 (1985), no. 2, 383–407 (French). MR 778134, DOI 10.1007/BF01388980
- H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR 0424730 G. H. Hardy & E. M. Wright, Introduction to the Theory of Numbers, 4th ed., Oxford Univ. Press, London, 1965.
- Christopher Hooley, On the intervals between numbers that are sums of two squares. III, J. Reine Angew. Math. 267 (1974), 207–218. MR 342479
- Karl-Heinz Indlekofer, Scharfe untere Abschätzung für die Anzahlfunktion der $B$-Zwillinge, Acta Arith. 26 (1974/75), 207–212 (German). MR 354586, DOI 10.4064/aa-26-2-207-212
- Donald E. Knuth and Luis Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci. 3 (1976/77), no. 3, 321–348. MR 498355, DOI 10.1016/0304-3975(76)90050-5
- D. H. Lehmer, Strong Carmichael numbers, J. Austral. Math. Soc. Ser. A 21 (1976), no. 4, 508–510. MR 417032, DOI 10.1017/s1446788700019364
- Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
- Karl K. Norton, On the number of restricted prime factors of an integer. I, Illinois J. Math. 20 (1976), no. 4, 681–705. MR 419382
- Carl Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math. 293(294) (1977), 217–222. MR 447087, DOI 10.1515/crll.1977.293-294.217
- Carl Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), no. 1, 84–89. MR 581999, DOI 10.1112/S0025579300009967
- Carl Pomerance, Recent developments in primality testing, Math. Intelligencer 3 (1980/81), no. 3, 97–105. MR 642128, DOI 10.1007/BF03022861
- Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, DOI 10.1090/S0025-5718-1981-0628717-0
- Carl Pomerance, A new lower bound for the pseudoprime counting function, Illinois J. Math. 26 (1982), no. 1, 4–9. MR 638549
- Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, DOI 10.1090/S0025-5718-1980-0572872-7
- Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
- 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
Additional Information
- © Copyright 1986 American Mathematical Society
- Journal: Math. Comp. 46 (1986), 259-279
- MSC: Primary 11Y11; Secondary 11N56
- DOI: https://doi.org/10.1090/S0025-5718-1986-0815848-X
- MathSciNet review: 815848