0:00

Previously, we looked at Fermat's primality test and saw that,

Â while it was simple and efficient,

Â it had a significant flaw in that,

Â there exists some numbers,

Â such as the Carmichael numbers,

Â for which it is incapable of identifying the fact that they are not prime.

Â There are many more sophisticated tests at the expense of speed,

Â that are able to identify prime numbers with a higher degree of certainty.

Â And while some of them are deterministic,

Â meaning that they will tell us definitively if the number is prime or not,

Â most of them are still probabilistic in nature.

Â The deterministic tests are just too slow for most purposes,

Â so we won't consider them further.

Â Perhaps the most common next step up in probabilistic tests is Miller-Rabin.

Â This test takes an observation regarding the square roots of one in

Â a modular field and then uses for Fermat's little theorem to exploit that observation.

Â Consider the square root of 1 in a modular world.

Â Our defining relationship is the square of our root,

Â must be congruent to 1 modulo n. For the moment,

Â we are not placing any constraint on n as far as whether or not it is prime.

Â There are always two trivial solutions to this relation, namely;

Â when x is congruent to 1 and when x is congruent to -1,

Â which is the same thing as x being congruent to -1.

Â But there could be other non-trivial solutions.

Â For instance, consider a mod 8 world where three squared is congruent to 1.

Â How is this even possible?

Â We can write our square equation as the difference between x squared and 1 and this

Â has to be congruent to 0 mod n. Next we factor the left hand side.

Â This says, that n divides the product of x -1 and x +1.

Â When n is a composite then some of its factors might

Â divide x -1 and the rest divide x +1.

Â In the case of our mod 8 example with x equals 3 we are dealing with 2 times 4.

Â But what about when n is prime?

Â In this case, n must divide either x-1 or x+1.

Â Since we can't split its factors between the two in any non-trivial way.

Â This means that x must be congruent to either 1 or -1 (mod n).

Â These are the only two possibilities.

Â And therefore, if the modulus is prime,

Â then we are guaranteed that there are no non-trivial square roots of 1.

Â The contrapositive of this,

Â is that if we succeed in finding a non-trivial square root of 1,

Â then we are guaranteed that the modulus is not prime.

Â That's the foundation of the Miller-Rabin primality test.

Â But if one has a non-trivial square root,

Â how do we find it?

Â Fortunately, Fermat's little theorem lets us cheat.

Â Recall this theorem says that a raised to 1 less than

Â the modulus is congruent to 1 if the modulus is prime.

Â We can start with a carefully chosen power of

Â our randomly chosen value of a and then square this number repeatedly,

Â which we know how to do very efficiently using the square and multiply technique,

Â until we reach a to the n-1.

Â If this is congruent to 1,

Â then it passes the Fermat's primality test for that choice of a.

Â But now we have a potentially non-trivial square root of 1,

Â namely the last value that we squared in order to get a to the n-1.

Â And if this value is congruent to one,

Â then its square root is just the next prior number.

Â We can proceed back down this chain all the way to our carefully chosen power of a.

Â At that point, if we still haven't ruled out the possibility that the n is prime,

Â we can either assume that it is or pick another value of a and repeat the test.

Â The more we repeat the test,

Â the more confident we are that the n is prime.

Â In fact, if n is an odd composite number,

Â at least three-fourths of the values of a are witnesses for the compositeness of a.

Â This can be proven, but we are just going to accept it as a proven fact.

Â Thus the probability that we still think that

Â an odd composite number is prime after K tests,

Â is no more than one-fourth raised to the K power.

Â Because of the distribution of prime numbers,

Â the probability that a randomly chosen odd number is

Â not prime after K tests have failed to prove it isn't,

Â is significantly less than this.

Â In fact, we have the unusual situation that the larger the number,

Â the smaller the number of tests that are needed to achieve the same level of confidence.

Â Sometimes we do get something for nothing.

Â NIST recommends just five iterations of Miller-Rabin to achieve 112 bits of security,

Â when testing the 1024-bit prime numbers needed to generate 24-bit RSA moduli.

Â In contrast, they recommend 39 iterations for the four,

Â 133-bit prime numbers used by that same algorithm.

Â Getting back to constructing our test,

Â we need to figure out how to carefully choose that power of a that we start with.

Â Since our candidate prime is going to be an odd number,

Â n-1 is an even number,

Â which means we can factor two out of it.

Â If it is still even, we can do this again.

Â Eventually, after pulling out s factors of 2,

Â we will be left with an odd integer.

Â Such that, P-1 is the product of an integer power of 2 and some odd integer.

Â Note that the smallest value that s can be as 1,

Â since we know that P-1 is even.

Â Rewriting Fermat's little theorem in light of this,

Â we get this expression.

Â Exploiting the properties of exponents,

Â we can see that this is just a to the d squared s times.

Â So a to the d is our carefully chosen power of a.

Â If the left hand side turns out to not be congruent to 1,

Â then we know that n is not prime and can stop right there.

Â But if it is congruent to one then we need to see if its square roots are trivial.

Â Because the exponent is even,

Â we can take the square root trivially by just decrementing the value of

Â s. If this number is not congruent to either 1 or -1,

Â then we have a non-trivial square root and we know that n is not prime.

Â If this number is congruent to -1,

Â then we have one of our two trivial roots and we can't go any further.

Â We know only that it is possible that n is prime.

Â If this number is congruent to +1,

Â then we also have a trivial square root which still means that n might be prime.

Â But in addition, we also have a new number that is congruent to 1 (mod n).

Â And this new number has to satisfy the same requirement,

Â that its square root must be non-trivial.

Â The square root of this number has the same form as before,

Â just with a value of S that is one less.

Â We can repeat this process all the way down until s equal to zero If we have to.

Â At that point we would need to take the square root of an odd power of a.

Â And that's one of those hard problems that we don't know

Â whether or not an efficient solution exists.

Â In fact, the security of the Rabin cryptosystem

Â is based on this very problem remaining a hard problem.

Â So we have to stop at this point and once again,

Â either assume that n is prime,

Â repeat the test with a different value of a or perhaps use a different test.

Â In practice a commonly used follow up test,

Â is the Lucus play maladie test.

Â At each step, we have three possibilities based on the square root.

Â If it is not congruent to either 1 or -1,

Â we stop and declare n to be non-prime.

Â If it is congruent to -1,

Â we have to stop and pick a new base

Â because we don't have any constraint on the square root of -1,

Â just on the square root of 1.

Â If it is congruent to +1, we can continue.

Â Now the process just described would have a start with a to the n-1 and to

Â find this we would use square and multiply or

Â some other efficient modular exponentiation algorithm.

Â If the result was inconclusive,

Â we would then need to find the square root of this number.

Â Yes, we have a formula for it, we just decrement s,

Â but we would need to start over and go through the same square and multiply process,

Â except we get to stop with one fewer squaring.

Â There's no reason to redo all this work.

Â We could just remember a to the d and all of its squares,

Â and then just look up the square roots as we need them,

Â by walking back down the list.

Â But we can do better than this.

Â We can perform our checks as we build our way up toward a to the n-1 and abort

Â the test as soon as we can determine that

Â continuing is going to be unable to decide that n is composite.

Â To see how and when we can make this determination,

Â let's make a tree of all the possible paths starting from a to

Â the n-1 and work down to a to the d, our starting point.

Â We'll assume that s equals 3,

Â meaning that we need to square a to the d three times to get to a to the n-1.

Â We'll define x of zero to be a to the d and x of i to be the ith squaring of x of zero.

Â So at the top of the tree,

Â we have our x of s or in our case x of 3.

Â There are three possible values of x of 3, either -1,

Â +1 or K, where K just means something other than plus or -1.

Â If we have -1 we'd declare the test a pass,

Â meaning n might be prime and the current test is unable to prove otherwise.

Â While if we have K we declare n to be a composite.

Â But since we are working our way up from x to the zero,

Â we still need to take the square root of both of these,

Â as well as +1.

Â If we take the square root of -1 to get x of 2,

Â we can't end up with either +1 or -1,

Â since the square of both of these is +1.

Â So we have to end up with something else,

Â namely another K. If we take the square root of +1,

Â then we have the same three possibilities as the prior step, namely -1,

Â +1 or some other K. If we take the square root of K,

Â remember that's something other than -1 or +1,

Â then we can't end up with either -1 or +1,

Â since the square of either of these is +1.

Â So we have to end up with yet another K. We can now

Â flesh out every possible path all the way down to X of the zero.

Â Every path that has a -1 in it somewhere, passes the test.

Â In addition is X of 0 is +1 then it passes the test.

Â All of the other paths declare n to be a composite.

Â Now let's work our way up from the bottom.

Â If X of zero is either plus or -1, we passed the test.

Â Otherwise, we square it and if the result is -1 we passed the test.

Â If not we square it.

Â The key is to recognize that once we start squaring,

Â every path that passes the test encounters a -1 at some point.

Â While every path that declares n to be composite doesn't.

Â So let's recap the Miller-Rabin primality test algorithm.

Â First, we pick our Random value for n of the size we want.

Â We might pre-process this with a number sieve or with Fermat's primality test or not.

Â But however we get there,

Â we have a candidate value for n. We then compute n to the -1.

Â Then we determine the value of s by counting how many times we need to divide n-1 by 2,

Â until we get an odd number.

Â Now we calculate a to the d,

Â and see if it's congruent to either 1 or -1.

Â If it is congruent to either,

Â then we passed the test.

Â If a to the d is congruent to anything else then we square it a total of s times.

Â If any of these are congruent to -1,

Â we passed the test and can stop at that point.

Â If we don't pass the test somewhere along the way,

Â then n is confirmed as being a composite number.

Â Well, let's work a couple of examples.

Â First, let's pick the smallest Carmichael number which is 561.

Â Remember a Carmichael number is one that will pass the Fermat's primality test,

Â no matter what value we choose for a. n-1 is 560,

Â from which we can pull out four factors of 2,

Â leaving us with 35.

Â Lets choose a equals 7.

Â Using square and multiply we find that 7 to the

Â 35 is congruent to 241, so we can continue.

Â Our four squarings produce values of 298,

Â 166, 67 and 1.

Â Since none of these are -1, we declare that 561 is not prime.

Â Moving up to the next odd integer,

Â let's try n equals 563.

Â Here n -1 is equal to two times 281.

Â Using the same value of 7 for a,

Â 7 to the 281st power is congruent to -1.

Â We are done since this value of a can't be a witness for the compositeness of 563.

Â We could try more values of a, but we won't.

Â In fact, 563 is prime.

Â You might try on your own,

Â using Miller-Rabin to test if n equals 215 is prime,

Â using a value of a for 6.

Â Since it is obvious that 215 is divisible by five,

Â If this test passes then 6 is a liar for 215.

Â Now pick some other value for a,

Â your choice and repeat the test.

Â In fact, I constructed this value of n and a specifically to produce a liar.

Â You might try to see if you can figure out how to

Â construct a liar for some other n and a.

Â