Return to Video

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
Amara Bot added a translation

English subtitles

Revisions