1. One possible computation for SYNCH-CPP is given below. Here ri is used as in the asynchronous case to indicate which register the ith processor is inspecting. Bits in italics are randomly generated.

               r0 r1    R0 R1  B0 B1  C0 C1    r0 r1
                                0  0   0  0     0  1
   subcase 3    0  1     0  0   1  1   1  1     1  0
   subcase 3    1  0     1  1   0  0   0  0     0  1
   subcase 3    0  1     0  0   0  0   0  0     1  0
   subcase 3    1  0     0  0   1  0   0  1     0  1
   subcase 2/3  0  1     0  1   1  1   #  1     -  0
   subcase 1    -  0     -  #    halt

2. Despite my having coded and tested an ASYNCH-CPP simulator to test this very point, it seems that there is no computation using this protocol that takes exactly 6 iterations (or rounds) -- or any other even number greater than 4. Apparently I fixed the bug while I was making some changes that I thought were merely cosmetic.

   So I gave most of the credit for this part of the problem to any computation that basically made sense, and also liberalized the grading scale a bit.

1. One generator is 3. Its first 16 powers are:
   3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1

   The other generators are the residues in odd-numbered positions of this list (assuming that the first list position is position 1).

2. The discrete log of 10 to the base 3 (mod 17) is 3, since 10 is in the 3rd position of the list above. For other generators (and thus other bases), the discrete log will be different.

3. The discrete log of 10's reciprocal should be 16-3, or 13. The reciprocal itself is 12, which appropriately lies in the 13th position of the list above. Again, for other generators (and thus other bases), the discrete log will be different, but the discrete log of this section and the previous section should add to 16 (or some multiple of 16), no matter what the base is.

4. The recursive argument for the Euclidean GCD algorithm are given at left below, and are computed top down. The coefficients in parentheses at right below are computed bottom up.

     GCD(17,10)         1 = 17(3)  + 10(-5)
     GCD(10, 7)         1 = 10(-2) + 7(3)
     GCD( 7, 3)         1 = 7(1)   + 3(-2)
     GCD( 3, 1)         1 = 3(0)   + 1(1)
     GCD( 1, 0)

   So the reciprocal of 10 mod 17 is -5, or 12, which agrees with the value calculated above. And the reciprocal of 17 mod 10 is 3.

1. In the first case we get the simple recurrence t₁=0; t_n = t_n-1 + b[b(n-1)] This is clearly quadratic in b; the master theorem on p. 73 of Cormen et al says that it is also quadratic in n. So t(n) is Θ(b²n²).

2. In the second case, let n=2^k and s_k = t_n, For s_k, we get the recurrence s₀=0; s_k = s_k-1 + [b2^k-1][b2^k-1] This is clearly quadratic in b; the master theorem on p. 73 of Cormen et al says that it is also Θ(2^2k), or Θ(n²). So t(n) is Θ(b²n²).

3. In the third case, let n=2^k-1 and s_k = t_n. For s_k, we get the recurrence s₁=0; s_k = s_k-1 + [b(2^k-1-1)][b(2^k-1-1)] + [b(2^k-2)][b] This is clearly quadratic in b; the master theorem on p. 73 of Cormen et al says that it is also Θ(2^2k), or Θ(n²). So t(n) is Θ(b²n²).

EXTRA CREDIT:

1. The first few terms of the sequence (t_n) are 0, b², 3b², 6b², and 10b². This suggests that t_n = n(n-1)b²/2. This guess may be verified by an easy induction:

   Basis:

   When n=1, t_n = 0, which agrees with the given function.

   Induction step:

   When n>1, the inductive hypothesis gives a value of (n-1)(n-2)b²/2 for t_n-1. The recurrence then gives a value for t_n of

           (n-1)(n-2)b2/2 + b[b(n-1)],  or
           [b2/2][(n-1)(n-2) + 2(n-1)],  or
           [b2/2][n(n-1)]

   which is equal to the desired value.

2. The first few terms of this sequence are 0, b², 5b², 21b², and 85b².

   These terms increase by roughly a factor of 4. By comparing the coefficients with the powers of 4, the hypothesis s_k = (4^k-1)b² / 3 is suggested. This may be verified by an easy induction:

   Basis:

   When k=0, s_k = 0, which agrees with the given function.

   Induction step:

   When k>0, so that n>1, by assumption the n/2 power has size b(n/2) = b2^k-1 and by induction it takes time (4^k-1-1)b² / 3 to compute. So the cost of computing the nth power is (4^k-1-1)b² / 3 + [b2^k-1][b2^k-1], or [b²/3][(4^k-1-1) + 3(4^k-1)], or [b²/3][4(4^k-1)-1], which is equal to the desired value.

   Note that in terms of n, the time cost is (n²-1)b² / 3, or about 2/3 of the cost of computing the nth power directly from the definition.

3. The first few terms of this sequence are 0, b², 3b², 18b², and 81b².

   These terms are just less by k than the terms of the previous sequence (noting that the previous sequence begins at k=0 and not k=1). This suggests that s_k = [-k+(4^k-1)/3]b². This may be verified easily by induction:

   Basis:

   When k=0, s_k = 0, which agrees with the given function.

   Induction step:

   When k>1, so n>1, by assumption the (n-1)/2 power has size b(n-1)/2 = b(2^k-1-1) and by induction it takes time [-k+1+(4^k-1-1)/3]b² to compute. So the cost of computing the nth power is

           [-k+1+(4k-1-1)/3]b2 + [b2k-1-1][b2k-1-1]?? + [b2k-2][b]??, or
           [b2/3][(4k-1-3k+2) + 3(4k-1-2k+1) + 3(2k-2)], or
           [b2/3][4(4k-1)-3k+2+3-6], or
           [b2/3][4k-3k-1]

   which is equal to the desired value.

   Note that in terms of n, the time cost is [(n+1)²-3log₂(n+1)+-1][b²/3], or [-log₂(n+1)+(n²+2n)/3]b², which is once again about 2/3 of the cost of computing the nth power directly from the definition.

1. 1281 = 128
   1282 = 82
   1283 = 46
   1286 = 26
   12812 = 49
   12824 = 102
   12825 = 98
   12850 = 199
   12851 = 183
   128102 = 49
   128103 = 2
   

2. 22 = 4
   24 = 16
   25 = 32
   210 = 1024
   220 = 5677
   221 = 5183
   242 = 1126
   284 = 2821
   285 = 5642
   2170 = 2146
   2171 = 4292
   

   42922 = 829
   42924 = 2260
   42928 = 4183
   429216 = 2704
   429232 = 5152
   429264 = 1633
   429265 = 4751
   4292130 = 4654
   4292131 = 5612
   

   Note that 5612 is not the original message. So the problem with assuming that Carmichael numbers are prime is not with the security of the method, but with its accuracy. In other words, the algorithm will fail obviously and early on, with high probability.

The computation will differ for the other test, depending on the value of x. But for example, if x = 0101010011₂ = 339, then 3x = 1017, and the exponentiation algorithm would start with the witness 2 and compute the powers of 2 with exponents 2, 3, 6, 7, 14, 15, 30, 31, 62, 63, 126, 127, 254, 508, and 1016. The respective powers are 4, 8, 64, 128, 112, 224, 343, 686, 742, 467, 451, 902, 4, 16, and 256. Since this last power is not 1, we may safely conclude that 1017 is composite. For other values of 3x, additional witnesses may be required.