1. a. (15 pt) The prime number theorem states &pi(x) &sim x / ln(x).
Use the approximation pln (20) = 3 to estimate the number of primes between 3200000 and 3200400.
(Note: 3200000 = 205 and 3200400 = 205 + 202.)
b. (15 pt) The number 2003 is prime.
Compute the smallest positive X which solves
X &equiv 52004 mod 2003.
Justify your answer. (You may wish to state Fermat's Little Theorem.)
2. The table ``Multiplication Modulo 31'' may be helpful, but you do not
have to use it.
A certain Diffie-Helman key exchange uses the prime P=31 and base b
= 3.
The Home Team has chosen private exponent H = 19.
The Away Team has a secret private exponent A.
a. (15 pt) Use "repeated squaring" to compute 319 mod 31.
b. (15 pt) The Away Team reports 3A &equiv 13 mod 31.
Compute the Home Team/Away Team shared secret.
3. a. (15 pt) The Home Team's RSA cryptosystem uses the primes p= 11 and q = 19, and, thus, modulus m = pq = 209.
The Home Team's encryption
exponent is e = 7 and decryption exponent is d = 103.
Justify that the exponents e and d work as an encryption/decryption pair.
(You may wish to use Euler's &phi(m) function and state the related theorem.)
b. (20 pt) The Away Team sets up an RSA cryptosystem using their own modulus which,
written in binary, is B bits long.
Let f(B) be the time required to encrypt one message block using the Away
Team RSA system.
Which of the following is the smallest complexity class containing f(B):
I. O( BK), K > 0
II. O( KB), K > 1
III. O( (log B)K), K > 0
IV. O( 1 )
where, in each case, K is a some constant independent of B.
Bonus. (10 pt) Find an integer Z between 2 and 207 which solves Z2 &equiv 1 mod 209.