Assignment 4 Solutions

1.  Denote p = 227. The element alpha = 2 is primitive in Z_p*.

(a) 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^32 = 176 = 2^4 x 11
    2^40 = 110 = 2 x 5 x 11
    2^59 = 60 = 2^2 x 3 x 5
    2^156 = 28 = 2^2 x 7
   
(b) 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). 
    
    log 2 = 1
    log 3 = 46
    log 5 = 11
    log 7 = 154
    log 11 = 28   
    
(c) 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. 
    
    173 x 2^177 = 168 = 2^3 x 3 x 7
    log 173 = 2 x log 2 + log 3 + log 7 - 177 = 26

2.  In this question, we consider a generic algorithm for 
    the discrete log problem in (Z_19,+).  

(a) 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).
    
    Good(C) = {0, 1, ... , 9, 11,12,13,14,16}
    
(b) 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"?  
    
    Since all of the encodings are different, 
    "a" is in Z_19 \ Good(C) = {10,15,17,18}  
 
3.  Let E be the elliptic curve y^2 = x^3 + x + 28 defined over 
    Z_{71}.

(a) Determine the number of points on E.

    There are 72 points on E.

(b) Show that E is not a cyclic group.

    The equation x^3 + x + 28 = 0 has three solutions in Z_71: 27, 53, and 62.
    By the result proven in question 4, E has three points of
    order 2 and hence it is not cyclic.

(c) What is the maximum order of an element in E? 
    Find an element having this order.
    
    Since |E| = 72 and E is not cyclic, the maximum possible
    order of an element in E is 36. There are in fact elements of order
    36 in E, e.g., (4,5).

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.)
    
    Let a_1, a_2 and a_3 be the three roots. It is easy to prove that
    x_1 = (a_1,0), x_2 = (a_2,0) and x_3 = (a_3,0) are points on E 
    having order 2.
    
    First solution: E has at least three points of order 2. A well-known
    result in group theory assets that any cyclic
    group G has exactly phi(d) elements of order d, for any d dividing |G|.
    Since phi(2) = 1 and G has 3 points of order 2, it is not cyclic.
    
    Second solution (following the hint):  Using the fact that 
    a_1 + a_2 + a_3 = 0, which follows because the coefficient of 
    x^2 in the cubic equation x^3+ax+b = 0 is 0, it is straightforward to 
    show that x_1 + x_2 = x+3, x_1 + x_3 = x_2 and x_2 + x_3 = x_1.
    Hence {x_1,x_2,x_3,O} is isomorphic to Z_2 x Z_2. 
    Since G contains a subgroup that is not cyclic, G is not cyclic.