If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

## Computer science

### Course: Computer science>Unit 2

Lesson 7: Randomized algorithms

# Fermat primality test

A quick outline of how & why it works. Created by Brit Cruise.

## Want to join the conversation?

• maybe if a =1 then the gdc(a,p) will be 1, 1^(p-1)=1 and then will flag as prime no matter what number p is
• Good point! I forgot to mention in the video that a starts at 2. It is chosen such that 1 < a < p-1
• Does the flaw have to do with trying to raise a number to a high exponent for very large test numbers?
• Great video, Brit! The flaw is that there exist composite numbers c where a^(c-1) mod c ≣ 1 whenever gcd(a, c) = 1. These are the Carmichael Numbers (http://en.wikipedia.org/wiki/Carmichael_number), and they fool the Fermat primality test. You can always trust the test when it tells you a number is composite, but you can't be sure you don't have a Carmichael Number when it tells you a number is prime!
• Remember, the thing only has to be accurate 99.999 percent of the time. And then I looked at your website and saw that there were many more than 1 Carmichael number in every ten thousand. Good catch. I presume there will be like a follow up video about this.
• This is so cool. It is really like magic! I was working with Stern-Brocot to produce rational number for gear ratios and wondering how to check/avoid primes. In general the numbers I am going to use are small and the brute force trial division wouldn't be too bad, but I really like the elegance of this.

I'm guessing the gcd determination for a,p is going to be the sticking point. Euclidean algorithm or something cleverer?
• Finding gcd's is actually pretty fast. Euclidean algorithm is fine.(Some minor speed improvements can be found using the Binary GCD Algorithm)

The major bottleneck is modular exponentiation. We can use fast modular exponentiation, but it is only "fast" compared to other methods for modular exponentiation. It is still a slow and computation intensive operation.
• I've heard of something called AKS test. What's that?
• AKS test is a deterministic polynomial time algorithm for checking if a number is prime.
- deterministic means it doesn't rely on randomness
- polynomial time means it is faster than exponential time
-its running time and correctness don't rely on any unproven conjectures from mathematics

So theoretically, for super large numbers, we can use the AKS test to tell us with 100% accuracy if the number is prime, and it won't take exponential time.

However, in practice, the AKS test is really slow and complicated, so instead we use non-deterministic algorithms, like Miller-Rabin, that will tells us, with some probability, that a number is probably prime. We then repeat those algorithms over and over until we are satisfied that the chances of the algorithm giving us a false result is sufficiently small.

So the AKS test is interesting theoretically, but not really useful in real life.

https://en.wikipedia.org/wiki/AKS_primality_test
• What's the flaw?
• Endeavor to figure it out yourself. Really think about it: What's the problem in a Primality Test that runs a set number of tests and then deems a number prime if no tests deemed the number composite? It seems perfect as it puts a limit on the number of steps it takes for it to stop and just deems a number prime without going all the way through. But in its seemingly perfection lies the problem...
• The number 133333777 seems to be always fooling the Fermats prim. test. Is this something on my end?
(1 vote)
• This is caused by how javaScript stores numbers internally. If your numbers are too big (>8 digits) the calculations start to lose numbers, leading to mistakes. To prevent this, a Big Integer library, which allows large numbers, would be required.
• I'm not sure if this has anything to do with the "tiny flaw" Brit mentioned, but here is one thought:

The number of steps doesn't scale with the input, but as the candidates for prime have more and more digits, the number of trials will have to be increased as well. Is this going to affect the number of steps, eventually leading to the Fermat test being inefficient?
• Not for smaller numbers. It only does multiple tests for numbers with fools or primes. As a result, for smaller composites or even larger ones without fools, it only takes the first trial before leaving.
• Why is he emphasizing a and p share no common factors in the cancellation at ?

I could think of cancelling the a and replace p with p-1 by the cancellation law but I don't see how that is related to the condition p and a sharing no common factors.
• Cancellation in modular arithmetic is based on multiplying both sides by the modular inverse of the number being "cancelled". However, a modular inverse for a number only exists if it is coprime to the modulus (i.e. it has no common factors with the modulus).

Let's see what happens when we use cancellation correctly:
15 mod 6 = 75 mod 6 (both equal to 3)
(3 * 5) mod 6 = (15 * 5) mod 6
Since 5 is coprime to 6, it has a modular inverse, 5^-1
So we can "cancel" the 5s
5 mod 6 = 15 mod 6
This is equivalent to multiplying both sides by 5^-1:
(3 * 5 * 5^-1) mod 6 = (15 * 5 * 5^-1) mod 6
(3 * 1) mod 6 = (15 * 1) mod 6
3 mod 6 = 15 mod 6
3 = 3
Which is true

Let's see what happens when we use it incorrectly:
But what happens if we try this for 3, which is not coprime to 6 ?
15 mod 6 = 75 mod 6 (both equal to 3)
(5 * 3) mod 6 = (25 * 3) mod 6
Let's (incorrectly) cancel the threes
5 mod 6 = 25 mod 6
5 = 1
Uh oh! That's not right.

Trying to cancel numbers which aren't coprime to the modulus is like trying to divide by zero. It gives you crazy results.

Hope this makes sense