Main content
Computer science theory
Course: Computer science theory > Unit 2
Lesson 7: Randomized algorithmsFermat 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(16 votes)
Good point! I forgot to mention in the video that a starts at 2. It is chosen such that 1 < a < p-1(13 votes)
Does the flaw have to do with trying to raise a number to a high exponent for very large test numbers?(10 votes)- Great question! In this video I didn't mention the cost of the gcd() and modular exponentiation operations. It is true that modular exponentiation is the bottle neck, though it is not the flaw. Here is an article demonstrating how modular exponentiation can be executed fairly efficiently with large integers:
https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/modular-exponentiation(14 votes)
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!(11 votes)- 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.(6 votes)
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?(4 votes)
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.(10 votes)
I've heard of something called AKS test. What's that?(3 votes)- 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.
For more info see:
https://en.wikipedia.org/wiki/AKS_primality_test(3 votes)
- What's the flaw?(2 votes)
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...(5 votes)
- 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.(6 votes)
I'm not sure if this has anything to do with the "tiny flaw" Brit mentioned, but here is one thought:6:28The 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?(2 votes)
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.(3 votes)
- Why is he emphasizing a and p share no common factors in the cancellation at1:22?
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.(2 votes)- 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(3 votes)
At5:18command Z comes up why does it?(3 votes)
6:28Video transcript
- [Instructor] Our goal is to define a series of instructions which can prove whether some input integer is
composite or else identify it as prime with some very
high degree of accuracy. Which we can define, and it must be efficient to do so. Meaning it should be fast
to calculate on any machine and even if the input size grows, which is our input integer N, it should still be fast. And so far we've learned
that at the lowest level this requires some known
pattern that all primes follow and very few composites follow. However, in the previous video
we did a visual demonstration of Fermat's little theorem and it provides us with
a very interesting rule. Given some prime number P
and some other integer A. Which is just less than P. We know now that P divides
A to the power of P minus A. We write this as A to the
power of P equals A mod P and that's the way you'll normally see it. Now because A and P share no common factor since P's a prime, we can use a cancellation law, and you'll sometimes see this written as A to the power of P
minus one is one mod P, and remember we can only do this because the greatest common divisor
of A and P equals one, and here I've just set up a demo so we can at first just
see this equation in action and get comfortable with it. Notice now if I input a prime for P, the output is always one
no matte what A I choose. If we input a composite number for P, we see that it usually isn't one, and anytime this equation output something that isn't one, we have a composite witness. This is now proof that the
P we chose cannot be prime, and that's the essence of this test, and before going any deeper, let's just step back and
construct the frame work for this test using this
pattern I just showed you. So our test starts. We are provided with some integer. Let's call it P, as input. Next we generate a random integer A. Which is less than P, and now we can as, is the
greatest common divisor of A and P one? If not, if the greatest
common divisor of A and P is greater than one, then
they share a common factor and we've proven that P is composite because a factor exists
and we can halt and exit and our algorithm will output composite. However, if yes, and we
can ask the key question, does A to the power of P
minus one mod P equal one? If not, we have a witness
that P is composite. We can halt and say we're
done, P's composite. Otherwise, if yes, if
our equation outputs one, then it should be prime, right? I coded up this series of instructions, and on the left hand side
we have Fermat's test, and on the right I just have
an existing trial division test and that's there because we
know that test is always correct and just at first glance
it seems like it's working. However, I found a problem. I hit the number 511,
and now the Fermat's test is saying it's prime, and
the trial division test is telling me that it's composite. 511 seems prime from the tests
perspective but it's not. Now let's just return back to our equation and see what happened. Well this is an example of
what we call a pseudoprime. It's a composite number
but there are certain A's we can choose that will output a one. That's incorrect again. So these A's which result
in a composite number outputting a one, we can call fools, because they're fooling us into
thinking the number's prime, but notice that if we
choose different A's, we seem to find many composite
witnesses instead of fools. So we could maybe just
step back and let's apply the same logic we used
in the divisibility test where we simply repeat
the experiment a few times and generate a new random A each time and hopefully we won't
pick a fool each time. Now it's been proven
that the number of fools must divide the total size
of the group we select from. Which means at most, half of the choices or half of the elements in
this pool could be fools. So since A is chosen randomly, the chance of finding a composite witness, which is what we want,
is at lest one half. After T iterations, the
probability that no witness will be found with a
composite number is at most one divided by two to the power of T. So after 20 trials the probability of mistakenly outputting a prime is just over one in a million. So that's the case where we just keep getting really unlucky
and generating random A's and every time we choose I fool. If you can let that sink in, that's really powerful to understand, and here now we can see our test in action with the increase number of trials. It seems to be working perfectly, and notice that in the worst case, which we know is when
we provide our algorithm with a prime, it's gonna do
the maximum amount of work. The Fermat test is much more
efficient than trial division. Especially because the number of steps doesn't scale with the input
and that's a key distinction. We set the number of trials and that's it. We never have to worry about our algorithm running millions and
millions of iterations as we did before. So I mean this is
quintessentially applied math. We are taking a pattern someone discovered and we're saving an immense
amount of computational cycles. However, there is one tiny
flaw for error in this system. Can you find it?