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

Хэрэв та вэб шүүлтүүртэй газар байгаа бол домэйн нэрийг *.kastatic.org and *.kasandbox.org блоклосон эсэхийг нягтална уу.

Үндсэн товъёог

# Fermat primality test

## Video transcript

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 Prime's follow and very few composites follow however in the previous video we did a visual demonstration of fir maas 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 8 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 factors since P is a prime we can use the cancellation law and you'll sometimes see this written as a to the power of P minus 1 is 1 mod p and remember we can only do this because the greatest common divisor of a and P equals 1 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 1 no matter what a I choose if we input a composite number for P we see that it usually isn't 1 and any time this equation outputs something that isn't 1 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 and construct the framework 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 ask is the greatest common divisor of a and P one if not if the greatest common divisor of an P is greater than one then they share a common factor and we've proven that P is composite because the 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 1 mod p equal 1 if not we have a witness that P is composite we can halt and say that we're done Peas composite otherwise if yes if our equation outputs 1 then it should be prime right I coded up this series of instructions and on the left hand side we have firm AHS on the right I just have an existing trial division test and that's there because we know that test is always corrected and just at first glance it seems like it's working however I found a problem I hit the number 511 and now the firm AHS test is saying its prime and the trial division test is telling me that its 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 pseudo prime it's a composite number but there are certain days we can choose that will output a 1 so it's incorrect again so these days which result in a composite number outputting a 1 we can call fools because they're fooling us into thinking the number is 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 are 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 least 1/2 after T iterations the probability that no witness will be found with a composite number is at most 1/2 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 a 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 with the increased 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 Fermata 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 or err in this system can you find it