Many classical primality tests are based on Fermat's Little Theorem which tells us that if,

\[ a^{p-1} \equiv 1 \pmod{p} \,.\]where \(a \in \mathbb{Z}\), then \(p\) is prime, for all \(1 \leq a < p\).

Since there are more composites than there are primes, a common test is to randomly select some \(1 \leq a < p\) and check to see if \((1)\) is satisfied. However, there are some cases where the test will pass even though \(p\) is in fact composite. For example, \(341 = 11 \cdot 31\), so \(341\) is definitely composite. However, it will pass the *Fermat Primality Test*, for any \(a\) which is a power of \(2\), e.g. \(2^{340} \equiv 1 \pmod{341}\). However, \(341\) will fail the test for other values of \(a\). Another problem we have is that of *Carmichael numbers* which will actually pass for all values of \(a\) which are relatively prime to \(p\) even though \(p\) is a composite number. The smallest Carmichael number is \(561\).

We therefore have two problems to consider. The first is the problem of those composite numbers which will pass the primality test for some values of \(a\).

In order to combat this problem, we repeat the Fermat primality test \(k\) times.

```
function fermatprimality(k, p)
for _ in 1:k
a = rand(1:p-1)
res = mod(big(a)^(p-1), p) == 1
if res == false
return :composite
end
end
return :likelyprime
end
fermatprimality(1, 341)
> :likelyprime
```

We can run an experiment and plot how repetitions impact the validity of the primality test.

```
ks = 5
experimentcount = 10
results = zeros(Int, (experimentcount, 2, ks))
table = zeros(Float64, (ks, 2))
for k in 1:ks
for i in 1:experimentcount
res = [ fermatprimality(k, 341) for _ in 1:1000 ]
c = filter(x -> x == :composite, res) |> length
lp = 1000 - c
results[i, :, k] = [c, lp]
end
table[k, :] = [
mean(results[:, 1, k])/1000,
mean(results[:, 2, k])/1000
]
end
bar(table, label=["Composite" "Likely Prime"], xlabel="Test Repeats")
```

We can clearly see that by re-running the test a minimum of \(5\) times, we can reduce the potential of error to approximately \(0.1\%\) which means this is a pretty good tool for verifying primality.

The second problem is that of Carmichael numbers. Fortunately, they are so few that we can manually check for a large chunk of them.

© Daniel Marvin. Last modified: July 19, 2021.