1. Try out the smoothness bounds L = 2.3 = 6, L^2 = 36 and so on... Let a = 2. gcd(a^L-1, N) = gcd(2^6-1, 1739) = gcd(63, 1739) = 1. gcd(a^{L^2}-1,N) = gcd(2^36-1, 1739) = gcd(2^36-1 mod 1739, 1739) = gcd(1517, 1739) = gcd(222, 1739) = 37. Thus, 37 divides N, and N can be written as N = 37 * 47 (which is its prime factorization.) [10 points for the idea + correct execution ] 2. a. x = 1, 3, 9. [3 marks] 2. b. Let x = g^k. Then, we want solutions to g^3k = 1 mod p. It must be that 3k is a multiple of p-1 since g is a generator of the group. Thus, the three distinct solutions are 1, g^{(p-1)/3} and g^{2(p-1)/3}. [ 7 marks] 2. c. The equations x^3 = 1 mod p and x^3 = 1 mod q have three solutions each. By Chinese remaindering each pair of solutions to the mod p and mod q equations gives us a distinct solution to x^3 = 1 mod N. Thus, we have 9 solutions. [3 marks] 2. d. Let x^3 = 1 mod N, and thus x^3 - 1 = 0 mod N. Factoring the left hand side, we get (x-1)(x^2 + x + 1) = 0 mod N. Thus, N | (x-1)(x^2 + x + 1). From (a), we know that N does not divide x - 1. From (b), we know that N does not divide x^2 + x + 1. It must be that p divides x-1 and q divides x^2+x+1, or the other way round. In either case compute gcd(x - 1, N) which gives us the answer. [7 marks] 3. I'll give the solution for Schnorr signatures. The idea for El Gamal signatures is essentially identical. Suppose Samantha releases two signatures with \sigma_1 = \sigma_1' = g^a, \sigma_2 = a + cx mod p-1 and \sigma_2' = a + c'x mod p-1 where c = H(M) and c' = H(M'). Given these two signatures, an adversary can now compute the secret key x as x = (\sigma_2' - \sigma_2) * (c'-c)^{-1} mod p-1 if the inverse of c-c' exists. [20 marks for the key idea]