Problem Set #5, CS 255, due May 14, 2007

Final version
Each problem is worth 20 points; there are 90 points in all
(including 10 points of extra credit)
 

 

  1. Why is there no provision in the distributed Echo algorithm (Algorithm 12.5.5 of Johnsonbaugh & Schaefer) for a processor's attempting to send a message to a processor that has already terminated? In other words, why will it never be the case that a processor attempts to send a message to a processor that has already terminated?

     

  2. A primitive kth root of 1 mod n is a residue r mod n such that rk = 1, but rj is not equal to 1 for 0 < j < k (cf. p 877 of Cormen et al). So for example, 9 is a 4th root of 1 mod 10, but it is not a primitive 4th root, since 92 = 1 mod 10. Note that k need not equal φ(n); for example 9 is a 4th root of 1 mod 20, but not a primitive 4th root of 1.

    Find a generator of the units of Z29. Modulo 29, what are the primitive square roots of 1? what are the primitive 4th roots of 1? what are the primitive 7th roots of 1? what are the primitive 14th roots of 1? how many generators are there? what are these generators?

    EXTRA CREDIT: (10 points) The definition of primitive kth root above suggests that to determine whether r is a primitive kth root of 1 mod n, it is necessary to copmute rj for values of j less than k. Show how, if g is known to be a generator of Z*n, one can find the primitive kth roots of 1, without having to do these computations.

     

    1. For a modulus of n = 247 = (13)(19), show how the EXTENDED-EUCLID algorithm of p. 860 of Cormen et al would determine that the key 31 is the appropriate decryption key for an encryption key of 7.

    2. For the modulus n above, RSA encryption of the message 2 with key 7 gives (unsurprisingly) 128. Trace the behavior of the MODULAR-EXPONENTIATION algorithm of p. 879 of Cormen et al when this encrypted message 128 is decrypted with the key 31. Show at least the results of each multiplication, and which power of M is represented by each such product.

     

  4. Apply the probabilistic primality testing algorithm described in class, with a confidence level of 95%, to the numbers 19 and 3x, where x is the 10-bit integer whose first 5 bits are the last 5 bits in the ASCII representation of the initial of your given name and whose last 5 bits are the last 5 bits in the ASCII representation of the initial of your given name. Use as witnesses the integers in the sequence 2, 3, 5, 7, ... of primes (you may assume these are independent witnesses). Note that 3x cannot be prime.