## 03-30 Faster Primality Test

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