## 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

• API
Udacity Robot
• Gundega