1. Give an example of the execution of the SYNCH-CCP algorithm that requires exactly 6 iterations. Note that not every processor needs to be active during each iteration. For each iteration, show all of the information that was shown in the examples in class.

2. Give an example of the execution of the ASYNCH-CCP algorithm that requires exactly 6 iterations (that is, a total of 6 iterations for the two processors combined). Give your results in a serialized form, as was done in class. For each iteration, show all of the information that was shown in the examples in class. In particular, make sure that it is clear (a) which register is assigned to each processor initially, (b) which processor is active during each iteration, and (c) what the new B value is, if the register is required to compute one.

1. Find a generator for Z₁₇. List in order the first 16 powers of this generator.
2. What is the discrete logarithm, mod 17, of 10, where the base is the generator that you found in the previous part of this problem?
3. What is the discrete logarithm of the reciprocal of 10 mod 17, where the base is the generator that you found in the previous part of this problem. What is the reciprocal itself?
4. Use the algorithm described in class for reciprocals mod n to find the reciprocal of 17 mod 10. Do you get the same answer that you got for the previous part of this question?

1. directly from the recursive definition of exponentiation (that is, the one that defines xⁿ in terms of x^n-1)
2. using the divide-and-conquer algorithm for exponentiation (that is, the algorithm analogous to the one on p. 879 of Cormen et al), assuming that n is a power of 2.
3. using the divide-and-conquer algorithm for exponentiation (that is, the algorithm analogous to the one on p. 879 of Cormen et al), assuming that n is 1 less than a power of 2.

EXTRA CREDIT: For 2 points per part, find exact (nonasymptotic) solutions to each of the three parts of this question, in terms of b and n.

1. For modulus n = (11)(19) = 209, RSA encryption of the message 2 with key 7 gives (unsurprisingly) 128. Trace the behavior of the divide-and-conquer exponentiation algorithm given in class when this encrypted message 128 is decrypted with the key 103. Show at least the results of each multiplication, and which power of M is represented by each such product.

2. Show what happens if a Carmichael number is accidentally assumed to be prime in the RSA algorithm. Specifically, show what happens when n = (11)(561) = 6171 and the message 2 is encrypted with the key 171 and decrypted with the key 131. Note that (171)(131) = 22401 = 1 mod (10)(560). Don't worry about the fact that φ(6171) is not equal to (10)(560).