×

Improved error bounds for the Fermat primality test on random inputs. (English) Zbl 1441.11302

As is well-known for every prime \(p\) and \(1<b\le p-1\) one has that \(b^{p-1}\equiv 1 \bmod p\) (Fermat test), but unfortunately also exist composite odd numbers verifying that congruence (pseudoprimes to the base \(b\)). This paper investigates the density of such pseudoprimes, improving previous results.
Let \(P(x)\) be the probability that an odd integer \(n,\, 1< n \le x\), is composite and it is pseudoprime to a random base \(b\), \( 1 < b < n- 1\). In a previous paper I. Damgård et al. [Math. Comput. 61, No. 203, 177–194 (1993; Zbl 0788.11059)] proved that for \(x\ge 10^{10^5}\) \(P(x)\le (log x)^{197}\) and they gave upper bounds for \(10^{60}\le x\le 10^{90}\). The present paper provides better bounds for \(10^{60}\le x \le 10^{90}\) (Table 1) and new bounds for \(2^{40} \le x < 10^{60}\), values not contemplated in the S. H. Kim and C. Pomerance’s paper [Math. Comput. 53, No. 188, 721–741 (1989; Zbl 0687.10001)] (Table 2).
The paper also studies \(P_1(x)\), the equivalent to \(P(x)\) for \(n\) strong pseudoprime (that is to say \(n\) passes the Miller-Rabin test).
Refining Kim and Pomerance’s methods Section 3 develops their basic method and Theorem 3.3 give an explicit bound for \(P(x)\). Section 4 refines the basic method considering the two largest prime factors of \(n\), see Theorem 4.4.
Section 5 deals with bounds for the probability \(P_1(x)\), see Theorem 5.1. Finally Section 6 is devoted to numerical results. Table 3 gives the bounds found for \(P(2^k|\, 40\le k \le 330)\) and Table 4 the exact values of \(P(2^k)\) for \(3\le k \le 36\).

MSC:

11Y11 Primality
11A51 Factorization; primality
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alford, W. R.; Granville, Andrew; Pomerance, Carl, There are infinitely many Carmichael numbers, Ann. of Math. (2), 139, 3, 703-722 (1994) · Zbl 0816.11005 · doi:10.2307/2118576
[2] Alford, W. R.; Granville, Andrew; Pomerance, Carl, On the difficulty of finding reliable witnesses. Algorithmic number theory, Ithaca, NY, 1994, Lecture Notes in Comput. Sci. 877, 1-16 (1994), Springer, Berlin · Zbl 0828.11074
[3] Baker, R. C.; Harman, G., Shifted primes without large prime factors, Acta Arith., 83, 4, 331-361 (1998) · Zbl 0994.11033
[4] Beauchemin, Pierre; Brassard, Gilles; Cr\'epeau, Claude; Goutier, Claude; Pomerance, Carl, The generation of random numbers that are probably prime, J. Cryptology, 1, 1, 53-64 (1988) · Zbl 0669.10014 · doi:10.1007/BF00206325
[5] Burthe, Ronald Joseph, Jr., Further investigations with the strong probable prime test, Math. Comp., 65, 213, 373-381 (1996) · Zbl 0852.11071 · doi:10.1090/S0025-5718-96-00695-3
[6] B\"uthe, Jan, Estimating \(\pi(x)\) and related functions under partial RH assumptions, Math. Comp., 85, 301, 2483-2498 (2016) · Zbl 1343.11083 · doi:10.1090/mcom/3060
[7] Bue J. B\"uthe, An analytic method for bounding \(\psi (x)\). Math.Comp., Published electronically October 26, 2017. DOI 10/1090/mcom/3264.
[8] Erd\H os, Paul; Pomerance, Carl, On the number of false witnesses for a composite number, Math. Comp., 46, 173, 259-279 (1986) · Zbl 0586.10003 · doi:10.2307/2008231
[9] Damg\aa rd, Ivan; Landrock, Peter; Pomerance, Carl, Average case error estimates for the strong probable prime test, Math. Comp., 61, 203, 177-194 (1993) · Zbl 0788.11059 · doi:10.2307/2152945
[10] Kim, Su Hee; Pomerance, Carl, The probability that a random probable prime is composite, Math. Comp., 53, 188, 721-741 (1989) · Zbl 0687.10001 · doi:10.2307/2008733
[11] Lichtman, Jared D.; Pomerance, Carl, Explicit estimates for the distribution of numbers free of large prime factors, J. Number Theory, 183, 1-23 (2018) · Zbl 1433.11109
[12] Monier, Louis, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci., 12, 1, 97-108 (1980) · Zbl 0443.10002 · doi:10.1016/0304-3975(80)90007-9
[13] Platt, D. J.; Trudgian, T. S., On the first sign change of \(\theta(x)-x\), Math. Comp., 85, 299, 1539-1547 (2016) · Zbl 1409.11065 · doi:10.1090/mcom/3021
[14] Rabin, Michael O., Probabilistic algorithm for testing primality, J. Number Theory, 12, 1, 128-138 (1980) · Zbl 0426.10006 · doi:10.1016/0022-314X(80)90084-0
[15] Rankin, R. A., The Difference between Consecutive Prime Numbers, J. London Math. Soc., S1-11, 4, 242 pp. (1936) · Zbl 0019.39403 · doi:10.1112/jlms/s1-13.4.242
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.