by Devesh Shetty
How to run the Fermat test for primality in under 3 minutes
The Fermat test is based on a result from number theory known as Fermat’s little theorem.
According to Fermat’s little theorem, if n is a prime number and d is any positive integer less than n, then d raised to the nth power is congruent to d modulo n.
If two numbers have the same remainder when divided by n then they are said to be congruent modulo n. d modulo n is simply the remainder of a number d when divided by n.
For example, 34 is congruent to 16 (modulo 3) as
34 modulo 3 = 1 and 16 modulo 3 = 1.
Fermat test for primality
- For a given number n, pick a random positive number d such that d <; n.
- Calculate (d^n) modulo n.
- d modulo n is always going to be d as we always pick d that satisfies the condition d <; n.
- If the result of (d^n) modulo n is not equal to d, then d is certainly not prime.
- If the result of (d^n) modulo n is equal to d, then the chances are good that n is prime.
- Pick another random d that satisfies the condition d < n and repeat the above steps.
Note: The examples in this post use Swift 4.1
We need a function to calculate the exponential of a number modulo another number.
We use modular exponentiation to compute values when the exponent is greater than 1 as this lets us perform computation while only dealing with numbers less than n (modulo in the above function).
The Fermat test chooses at random a number d between 1 and n-1 (number — 1 in the above function) inclusive. The aim is to check whether the remainder modulo n of the nth power of d is equal to d.
The Fermat test is run for the specified count. If a number fails the Fermat test, we are assured that it is not prime. If a number passes the Fermat test, it is not guaranteed to be prime. We try to reduce the probability of error in our primality test by running the test enough times.
By trying more and more values of d (a random positive number between 1 and n-1), we can increase our confidence in the result.