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.
