L6 (Primality)

Question 1

What’s fermat’s little theorem?

Answer 1

if an integer p is prime, then for every integer a:

a^(p-1) ≡ 1 (mod p)

note: not if and only if

Question 2

Propose an algorithm for testing if an input number N is NOT a prime

Answer 2

1. pick some a in {2, … , N-1}
2. if a^(N-1) ≡ 1 (mod N), then N could be a prime
3. otherwise, it is NOT a prime

Question 3

We want to test if N is prime. Suppose we pick a in {2, … , N}, and then we see that a^(N-1) ≡ 1 (mod N)

If this is the first time we do this, then what is the probability that N is prime?

Answer 3

0.5

if a^(N-1) ≡ 1 (mod N), then it has a 50% chance of being prime or not prime

This is the primality2() function

Question 4

Suppose we run the primality2(N) function k times for the same N. If it returns “True” in all k times, what is the probability that N is not a Prime

primality2(N) function:
Input is N, we pick a in {2, … , N}. Return “true” if a^(N-1) ≡ 1 (mod N) and “false” otherwise

Answer 4

(1/2)^k

For each time that we run primality2(N), there is a 1/2 chance that it is not prime. If we run it k times, then we simply raise the 1/2 to the power of k to get a (1/2)^k probability of N not being prime

The point of this is so that we can run it many times to test if a number is prime with a VERY low error rate

Question 5

What’s Lagrange’s prime number theorem for π(x) as the number of primes between 1 and x?

Answer 5

If π(x) is the number of primes between 1 and x, then:

π(x) ≈ x / ln(x)

This becomes more and more accurate as x goes to infinity

Question 6

Write an algorithm to generate a random prime number using primality2

What would the runtime of this algorithm be?

Answer 6

The runtime would be O(n) where n is the number of bits in N, which is roof(log(N))

so O(log(N))