Improved error bounds for the Fermat primality test on random inputs

Lichtman, Jared; Pomerance, Carl

doi:10.1090/mcom/3314

Improved error bounds for the Fermat primality test on random inputs
HTML articles powered by AMS MathViewer

by Jared Duker Lichtman and Carl Pomerance PDF

Math. Comp. 87 (2018), 2871-2890 Request permission

Abstract:

We investigate the probability that a random odd composite number passes a random Fermat primality test, improving on earlier estimates in moderate ranges. For example, with random numbers to $2^{200}$, our results improve on prior estimates by close to 3 orders of magnitude.

References

W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
W. R. Alford, Andrew Granville, and Carl Pomerance, On the difficulty of finding reliable witnesses, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1–16. MR 1322705, DOI 10.1007/3-540-58691-1_{3}6
R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361. MR 1610553, DOI 10.4064/aa-83-4-331-361
Pierre Beauchemin, Gilles Brassard, Claude Crépeau, Claude Goutier, and Carl Pomerance, The generation of random numbers that are probably prime, J. Cryptology 1 (1988), no. 1, 53–64. MR 935901, DOI 10.1007/BF00206325
Ronald Joseph Burthe Jr., Further investigations with the strong probable prime test, Math. Comp. 65 (1996), no. 213, 373–381. MR 1325864, DOI 10.1090/S0025-5718-96-00695-3
Jan Büthe, Estimating $\pi (x)$ and related functions under partial RH assumptions, Math. Comp. 85 (2016), no. 301, 2483–2498. MR 3511289, DOI 10.1090/mcom/3060
J. Büthe, An analytic method for bounding $\psi (x)$. Math. Comp., Published electronically October 26, 2017. DOI 10/1090/mcom/3264.
Paul Erdős and Carl Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), no. 173, 259–279. MR 815848, DOI 10.1090/S0025-5718-1986-0815848-X
Ivan Damgård, Peter Landrock, and Carl Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), no. 203, 177–194. MR 1189518, DOI 10.1090/S0025-5718-1993-1189518-9
Su Hee Kim and Carl Pomerance, The probability that a random probable prime is composite, Math. Comp. 53 (1989), no. 188, 721–741. MR 982368, DOI 10.1090/S0025-5718-1989-0982368-4
Jared D. Lichtman and Carl Pomerance, Explicit estimates for the distribution of numbers free of large prime factors, J. Number Theory 183 (2018), 1–23. MR 3715225, DOI 10.1016/j.jnt.2017.08.039
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
D. J. Platt and T. S. Trudgian, On the first sign change of $\theta (x)-x$, Math. Comp. 85 (2016), no. 299, 1539–1547. MR 3454375, DOI 10.1090/mcom/3021
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. A. Rankin, The Difference between Consecutive Prime Numbers, J. London Math. Soc. 11 (1936), no. 4, 242–245. MR 1574971, DOI 10.1112/jlms/s1-13.4.242