Return to Video

Primality Test - Applied Cryptography

  • 0:00 - 0:03
    So that suggests a strategy for finding a large prime--
  • 0:03 - 0:06
    which is to keep trying guesses until we find one that's prime.
  • 0:06 - 0:10
    If it's not a prime, then we add 1 and we try again.
  • 0:10 - 0:14
    Because of what we know about the number of primes being finite
  • 0:14 - 0:19
    and the density of primes, we know that after a reasonable number of iterations
  • 0:19 - 0:22
    this will actually find a prime and return that value.
  • 0:22 - 0:26
    We could do a little better if we assume we start with an odd number
  • 0:26 - 0:29
    and we'll assert that X is not divisible by 2
  • 0:29 - 0:32
    since that is very obvious that it would be prime
  • 0:32 - 0:34
    and increment by 2 here.
  • 0:34 - 0:37
    What's missing is we need some way to do this "is prime" test.
  • 0:37 - 0:41
    So here is a naive way to test to the finest prime.
  • 0:41 - 0:44
    We're going to go through the numbers from 2 to X minus 1,
  • 0:44 - 0:48
    checking whether X is divisible by each of those.
  • 0:48 - 0:50
    If it is divisible by any of those,
  • 0:50 - 0:52
    that would mean that it is a composite number
  • 0:52 - 0:54
    and we should return False.
  • 0:54 - 0:57
    If we try them all and it's not divisible by any of those, well then it's prime.
  • 0:57 - 0:59
    So the question is: Would this work?
  • 0:59 - 1:02
    The possible answers are: Yes, this would work fine.
  • 1:02 - 1:07
    No, it's too slow because the running time is exponential in the value of X.
  • 1:07 - 1:11
    No because it's too slow because the running time is exponential in the size of X.
  • 1:11 - 1:14
    And no, because there's a silly bug in my Python code.
Title:
Primality Test - Applied Cryptography
Video Language:
English
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
01:15
Udacity Robot edited English subtitles for Primality Test - Applied Cryptography
Gundega added a translation

English subtitles

Revisions Compare revisions