Fermat Primality Test

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

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.