Tip:
Highlight text to annotate it
X
We need a faster test for primes.
What we're going to use is a probabilistic test.
That means if some number x passes the test,
the probability that x's composite is less than some value.
We're going to use probabilities like 2^(-128).
This is certainly low enough for most uses in crytography.
One way to think about that is if the key size is 128 bits,
we already have that probability that someone would randomly guess that key correctly.
The main basis of probabilistic primality tests is properties of prime numbers.
One useful theorem about prime numbers is Fermat's Little Theorem,
which states that if p is prime, if we select some number a between 1 and p
and raise a^(p-1) power--modulo p--the result must always be 1.
Maybe we could try lots of a's.
If this equation always holds that a^(p-1) is congruent to 1 mod p,
that would mean that p is probably prime.
The problem is that there are some composite numbers
that are known as Carmichael numbers where this test also holds for most a values.
Indeed, it holds for all the a values that are relatively prime with p.
Unless we try all the a numbers between 1 and p
there is a high probability that this will always hold.
If we need to try them all, this test isn't fast enough.
It's still going to be exponential in the size of p.
The good news is there is a faster test, which is known as the Rabin-Miller test.
Sometimes it's known as the Miller-Rabin test.
It was discovered independently by both Miller and Rabin.
The main idea was originally proposed by Gary Miller in 1976.
He provided the deterministic test based on the assumption that Riemann hypothesis was true.
Michael Rabin, who won the Turing award in 1976,
probably did some of his more important work after winning the Turing award, which is quite unusual,
proposed this in 1980, and that's the one that we'll talk about.
Here is how this works, and I'm not going to cover the mathematics behind it,
but just enough to be able to implement the test.
We're going to start with our guess n, which must be odd.
Obviously, if it's even it's not prime.
Because it's odd, that means we can write it as a multiple of 2 + 1.
That means we can break it into 2^t s + 1.
Next we want to choose some random a value in this range from 1 to n -1.
If n is prime, we know that either a^s is equal to 1 mod n
or we know that a^(s(2^j)) is equal to n - 1 mod n for some j.
The j values are in the range from 0 to t -1, which is the power here.
That's the big advantage that we only need to try a small number of values.
If we don't find any value that satisfies this, we know it's composite.
The important property that this test has that's different from the Fermat test
is that the probability that a composite number of passes
is always less than some constant.
In this case it is less than one quarter.
There are no bad composite numbers like the Carmichael numbers.
If we choose a randomly, for any composite number the probability that the test
is less than one-quarter.