Improved error bounds for the Fermat primality test on random inputs

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.

20 pages; minor edits to improve the results slightly and to elaborate the argument

References in corpus (2)

• Estimating $\pi (x)$ and related functions under partial RH assumptions
• Explicit estimates for the distribution of numbers free of large prime factors

Cited by in corpus (1)

• Algorithms for the Multiplication Table Problem