Math 480, Spring 2015, Assignment 10

Carefully define the following terms:

1. Miller-Rabin witness (to the compositeness of $n$).
2. Miller-Rabin test.

Carefully state the following theorems (you do not need to prove them):

1. Lower bound on the number of Miller-Rabin witnesses when $n$ is composite.
2. Bound on the probability that $n$ passes $N$ Miller-Rabin tests, given that $n$ is composite.
3. Bound on the probability that $n$ is composite, given that it passed $N$ Miller-Rabin tests.

Carefully describe the following algorithms:

1. Algorithm to return an almost-certainly-prime number $p$ in the interval $[2^{b-1}, 2^b)$ (i.e. a $b$-bit prime).
2. Algorithm to return a $b$-bit safe prime.

Solve the following problems:

1. Problem 3.14(a-b).

Coding projects:

1. (Primes) Write a function that takes a positive integer $b$ as input, and return a $b$-bit prime. Write another function that returns a $b$-bit safe prime.

--------------------End of assignment--------------------