Complete each problem to the best of your ability.  The TAs and I are available and eager to help.  Be clear and thorough about your reasoning.

Euclid’s Algorithm (15 points)

Euclid’s Algorithm is an old algorithm for calculating the greatest common divisor of two numbers. It has surprising staying power, due to its efficiency for solving an interesting problem. Given two numbers like A0  = 161, A1  = 133, Euclid iteratively divides An  by An+1  and takes the remainder as An+2 .

161 divided by 133 is 1 with a remainder of 28, A2  = 28.

133 divided by 28 is 4 with a remainder of 21, A3  = 21.

28 divided by 21 is 1 with a remainder of 7, A4  = 7.

21 divided by 7 is 3 with a remainder of 0, A5  = 0.

When this algorithm hits An  = 0 for some n, it terminates, and returns An − 1  as the GCD. In this case, given the above, A4  = 7 is the greatest common divisor of A0  = 161 and A1  = 133. This is a very efficient algorithm in practice - it is interesting that this ‘joint’ factoring problem is much easier than the general factoring problem we discussed previously.

We can also take the result of this algorithm and flip it around in an interesting way. Given the example above, note that the remainder results can be re-expressed as the sequence of equations, starting with the second to last.

28 = 1*21 + 7

133 = 4*28 + 21

161 = 1*133 + 28

We can re-arrange them and substitute into one another:

7 = 28 一 1 * 21

21 = 133 一 4 * 28

28 = 161 一 1 * 133

7 = 28 一 1 * 21

= 28 一 1 * (133 一 4 * 28) substituting for 21

= 5 * 28 一 1 * 133 simplifying

= 5 * (161 一 1 * 133) 一 1 * 133 substituting for 28

= 5 * 161 一 6 * 133 simplifying

This final equation expresses the GCD of 161 and 133 in terms of these numbers themselves.  This process (taking the results of Euclid’s algorithm, substituting them into each other) is known as Euclid’s Extended Algorithm, and can be used to generate solutions to the equation

A0 x + A1 y = GCD(A0 , A1 )                                                                    (3) In this case, with A0  = 161, A1  = 133, with GCD(A0 , A1 ) = 7, the above process solved for x = 5, y = 一6.

1)  Solve for integers x, y where 1223x + 541y = 1. Show your work.

2)  Find the smallest positive k where 541k = 1(mod 1223).

3)  Find a, b, c, d so that x(t) = a + bt, y(t) = c + dt parameterizes every integer solution to 1223x + 541y = 1 for integers t. Show your work.

The Last Digits (15 points)

Fermat’s Last Theorem says that for any prime number p, if a is not a multiple of p, then

ap − 1  = 1(mod p).

Define a power tower in the following way: X1  = 2, and Xn+1  = 2Xn . This generates the following:

X2  = 2X1   = 22  = 4

X3  = 2X2   = 24  = 16

X4  = 2X3   = 216  = 65536

X5  = 2X4   = 265536  = a truly titanic number

1)  How many digits does X5  have, exactly?

2)  Prove that Xn  = 1(mod 5) for all n > 3.

3)  Prove that the last digit of Xn  is 6 for all n > 3.

RSA (20 points)

An RSA cryptosystem consists of five numbers (p, q, n, e, d) such that p, q are prime,

n = p * q

GCD(e, (p 一 1)(q 一 1)) = 1                                                                             

ed = 1 (mod (p 一 1)(q 一 1))

The pair (e, n) are published for all to see, so they can encrypt messages to send you, while (p, q, d) are held privately by you; these are the public encryption keys and the private decryption keys respectively.

To encrypt a message like ‘ABCDEF’, translate that into a series of digits (for instance A to 01, B to 02, Z to 26) etc, so the message becomes 010203040506 and partition that into a sequence of blocks numbers such that each number is less than n. In this case, you might have 010, 203, 040, 506. A block M is then encrypted using the following map:

M 1→ Me  (mod n),