Return to Video

Density Of Primes - Applied Cryptography

  • 0:00 - 0:03
    It turns out that the density of primes is such that
  • 0:03 - 0:05
    the number of primes below some number X
  • 0:05 - 0:09
    is proportional to X divided by the natural log of X.
  • 0:09 - 0:11
    So this is log base E.
  • 0:11 - 0:13
    And I won't attempt to prove this.
  • 0:13 - 0:15
    I'll resort to proof by intimidation.
  • 0:15 - 0:17
    This was conjectured by Gauss and then Legendre
  • 0:17 - 0:19
    and proven later.
  • 0:19 - 0:22
    And that means that the probability--if we pick some random number,
  • 0:22 - 0:24
    the probability that that number is prime
  • 0:24 - 0:27
    is approximately 1 over the natural log of X.
  • 0:27 - 0:30
    So the question is: how many guesses do we expect to need
  • 0:30 - 0:33
    to find a prime number that's around 100 decimal digits long?
  • 0:33 - 0:36
    And in computing this, you should assume that this probability
  • 0:36 - 0:40
    that a random X is prime is equal to 1 over the natural log of X
  • 0:40 - 0:43
    even though this is an approximation.
Title:
Density Of Primes - Applied Cryptography
Video Language:
English
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
0:44
Udacity Robot edited English subtitles for Density Of Primes - Applied Cryptography
Gundega added a translation

English subtitles

Revisions Compare revisions