# How many times should Fermat's primality test be applied?

For a prime number $p$, and an $a$ such that $\ \ 1<a<p-1$,

we have: $\ \ \ a^{p-1} \equiv 1\ \pmod p$

To test the primality of a number, this is applied multiple times for randomly chosen $a$ until either the number of iterations are up or the above equivalence becomes untrue, meaning the given number is composite. If the number of iterations are up, then the number is flagged as possibly prime.

Clearly, an upper limit on the number of iterations is $p - 3$ as there are $p - 3$ unique values for $a$ to take.

However, $p-3$ seems excessive and all computer implementations or resources I've seen for this algorithm (I haven't seen too many) always leave it up to the 'user' to set the number of iterations.

I was wondering, is there a formula or a guideline that gives the ideal number of iterations to be performed for Fermat's primality test?

• I guess it depends on what you try to achieve. For example, if you need 100% certainty you could do few fermat tests and only then use a slower non-probabilistic algorithm. On the other hand, using this test may be bad in general since there are so many Carmichael numbers en.wikipedia.org/wiki/Carmichael_number#Distribution . Better use Miller-Rabin for sieveing out possible prime candidates Jan 9 '18 at 15:19
• @Michael I heard through the grapevine that a famous old mathematician almost had a nervous breakdown when he realized there is a tiny chance Mathematica's PrimeQ function could falsely flag as prime a number greater than $10^{16}$. I bring this up because PrimeQ uses Miller-Rabin. Jan 9 '18 at 17:10
• @Aayush In testing 561 for primality, what are the odds that the computer will happen to randomly choose only $a$ that are not divisible by 3, 11 or 17? It seems to me that you're slightly better off going through the $a$ in order starting with 2. Jan 9 '18 at 17:21

## 1 Answer

The weak Fermat-pseudoprime-test is a good start, but there are infinite many composite numbers passing the test for every base coprime to the number, namely the Carmichael numbers.

However, if your number is large (say $$100$$ digits or more), and if it is a "random number" (no special form) and you choose a random base, the probability that the number is prime is already very high if the number passes the test.

The strong-Fermat-pseudoprime-test is much better. If a number passes the test with $$N$$ random bases, the probability that it is a composite number is at most $$(\frac{1}{4})^N$$. If the number fails the test, it must be composite.

If you want to be absolutely sure that a number is prime, either use the Adleman-Pomerance-Rumely-test (APR) or Elliptic-Curve-Primality-Proving. The APR-test is implemented in most programs with long-integer-arithmetic, for example in PARI/GP.