# Fermat Primality Test

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$$.

### Fermat Primality Test

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.