1. a. (15 pt) The prime number theorem states &pi(x) &sim x / ln(x).
Use the approximation ln (20) = 3 to estimate the number of primes between 3200000 and 3200400.
(Note: 3200000 = 205 and 3200400 = 205 + 202.)
Solution We estimate &pi(3200400) - &pi(3200000).
By the prime number theorem, this is about 3200400 / ln(3200400) - 3200000 / ln(3200000).
Using rules of logarithms, ln(3200000) is approximately 5 × 3 = 15.
Notice that 3200400 = 8001 × 400, so ln(3200400) = ln(8001) + ln(400).
ln(8001) really close to ln(8000). It's about ln(8000) + 1/8000.
The short story is ln(3200400) is really close to ln(3200400), which is about 15.
3200400 / 15 - 3200000 / 15 = 400 / 15 = 80 / 3 = 26.67.
We estimate there are 27 primes in the range 3200000 to 3200400.
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.)
Solution By Fermat's Little Theorem, 52002 &equiv 1 mod 2003, because 2003 is prime, and 5 is not a multiple of 2003.
Therefore, 52004 &equiv 52 &equiv 25 mod 2003.
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.
Solution Repeated squaring of 3 gives 32 &equiv 9, 34 &equiv 19, 38 &equiv 20, and 316 &equiv 28.
319 &equiv 316+2+1 &equiv 28 × 9 × 3 &equiv 12 mod 31.
b. (15 pt) The Away Team reports 3A &equiv 13 mod 31.
Compute the Home Team/Away Team shared secret.
Solution The shared secret is 3AH mod 31.
We compute (3A)H = 1319.
The repeated squares of 13 are: 14, 10, 7, 18.
We multiply 13 × 14 × 18 &equiv 21 mod 31.
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.)
Solution By Euler's Theorem, a&phi(m) &equiv 1 mod m for a and m relatively prime.
&phi(209) = 10 × 18 = 180.
de = 7 × 103 = 721 = 4 × 180 + 1.
ade &equiv a4 × 180 + 1 &equiv a mod 209 for a and m relatively prime.
Therefore, d and e function as an encryption/decryption pair.
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.
Solution The encryption exponent E will be at most B bits long.
The message X will be at most B bits long.
Computing XE by repeated squaring needs at most B squarings
and B multiplications of B bit numbers by B bit numbers.
Those each use about B3 one bit multiplications.
Together with the required addition, the total time requirement is O(B3). This is class I, polynomial order.
Bonus. (10 pt) Find an integer Z between 2 and 207 which solves Z2 &equiv 1 mod 209.
Solution If Z2 &equiv 1 mod 209, then Z2 &equiv 1
mod 11.
So Z &equiv ± 1 mod 11.
Ditto, Z &equiv ± 1 mod 19.
Both plus signs gives Z &equiv 1 mod 209. Both minus gives Z &equiv 208 mod 209.
If Z &equiv 1 mod 11 and Z &equiv -1 mod 19, we can run through
the list of -1 mod 19 numbers until we hit one that is 1 mod 11:
18, 37, 56, bingo. Z = 56.
Check: 56 × 56 = 3136 = 209 × 15 + 1.