On the number of false witnesses for a composite number

Erdős, Paul; Pomerance, Carl

doi:10.1090/S0025-5718-1986-0815848-X

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

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, 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

Introduction to the Theory of Numbers

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