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

• API
Udacity Robot
• Gundega