The Mathematics of Public-Key Cryptography, Assignment 4 (corrected)

due 11:30 AM, November 21, 2000

1. Denote p = 227. The element alpha = 2 is primitive in Z_p*.
   1. Compute alpha^32, alpha^40, alpha^59 and alpha^156 mod p, and factor them over the factor base {2,3,5,7,11}.
   2. Using the fact that log 2 = 1, compute log 3, log 5, log 7 and log 11 from the factorizations obtained above (all logarithms are logarithms in Z_p* to the base alpha).
   3. Now suppose we wish to compute log 173. Multiply 173 by the "random" value 2^177 mod p. Factor the result over the factor base, and proceed to compute log 173 using the previously computed logarithms of the numbers in the factor base.
2. In this question, we consider a generic algorithm for the discrete log problem in (Z_19,+).
   1. Suppose that the set C is defined as follows: C = { (1-i^2 mod 19, i mod 19) : i = 0,1,2,4,7,12}. Compute Good(C).
   2. Suppose that the output of the group oracle, given the ordered pairs in C, is as follows: (0,1) -> 10111, (1,0) -> 01100, (16,2) -> 00110, (4,4) -> 01010, (9,7) -> 00100, (9,12) -> 11001, where group elements are encoded as (random) binary 5-tuples. What can you say about the value of "a"?
3. Answer question 5.8 from the textbook.
4. Suppose that p > 3 is an odd prime, and a,b are elements of Z_p. Further, suppose that the equation x^3+ax+b = 0 has three distinct roots in Z_p. Prove that the corresponding elliptic curve group (E,+) is not cyclic. (Hint: show that the points of order two generate a subgroup of (E,+) that is isomorphic to Z_2 x Z_2.)