1. The number of generators of Zp* is \phi(p-1), as we saw in class. Since p-1 is even, write it as p-1 = 2^s * t, where s >= 1 and t is odd. Thus \phi(p-1) = \phi(2^s)*\phi(t) = 2^{s-1} * \phi(t) The fraction of elements of Zp* that are generators is \phi(p-1) / (p-1) = 2^{s-1} * \phi(t) / 2^s * t = 1/2 * \phi(t) / t Since \phi(t) < t, this fraction is less than 1/2. [15 points for this ] To maximize the fraction, we need to pick t such that \phi(t) is as large as possible, the natural choice being a prime t. Consider a sequence of safe primes p = 2q + 1 where q is prime. The fraction of elements of Zp* that are generators is q-1 / 2q = 1/2 - 1/2q that tends to 1/2 as q tends to infinity. Since there are conjectured to be infinitely many safe primes, this gives us what we need. [ 5 points for this ] 2. We compute the following table of powers of 2 mod 51. 2^1 = 2 mod 51 2^2 = 4 mod 51 2^4 = 16 mod 51 2^8 = 1 mod 51 2^16 = 1 mod 51 2^32 = 1 mod 51 Thus, 2^50 = 2^32 * 2^16 * 2^2 = 4 mod 51. [5 points for this ] There are other ways of doing it faster, and any one way is fine. This does not violate Fermat since 51 is not prime. If 2^m-1 \neq 1 mod m, m must be composite. [ 5 points for this ] 3. a) 2^1 = 2 mod 63 2^2 = 4 mod 63 2^4 = 16 mod 63 2^8 = 4 mod 63 2^16 = 16 mod 63 2^32 = 4 mod 63 2^42 = 2^32 * 2^8 * 2^2 mod 63 = 4 * 4 * 4 mod 63 = 1 mod 63 [2.5 points for this ] b) Since 2^12 = 1 mod 13 (Fermat), 2^2013 mod 13 = 2^{2013 mod 12} mod 13 = 2^9 mod 13. 2^1 = 2 mod 13 2^2 = 4 mod 13 2^4 = 3 mod 13 2^8 = 9 mod 13 Thus, 2^9 mod 13 = 2^8 * 2 = 9 * 2 = 5 mod 13. [ 2.5 points for this ] 4. The last two digits of 3^1999 is precisely 3^1999 mod 100. [ 2 points for realizing this ] Now, since \phi(100) = \phi(25) * \phi(4) = 5*4*2 = 40, by Euler's theorem, we know that 3^40 = 1 mod 100. Thus, 3^1999 mod 100 = 3^{1999 mod 40} mod 100 = 3^{-1} mod 100 = 67 mod 100. Thus, the last two digits are 67. [3 for the rest ] 5. The procedure is as follows: Check if, for some prime factor q_i, whether g^{(p-1)/q_i} = 1 mod p. If this is the case, then g is clearly not a generator, so output "NOT A GENERATOR". If not, output that "g IS A GENERATOR". [ 5 points for the procedure ] If g is a generator of Zp*, then by definition, g^{(p-1)/q_i} \neq 1 mod p for any of the prime factors q_i. Thus, the procedure will output "g IS A GENERATOR", which is the correct answer. [ 5 points for the proof of the "if" direction ] If g is not a generator of Zp*, its order is a proper divisor of p-1. Thus, if one writes down the prime factorization of ord(g), it will be of the form ord(g) = \prod q_i^{f_i} where at least one of the f_i < e_i. Fix such an i. When the procedure computes g^{(p-1)/q_i}, the exponent p-1/q_i is a multiple of ord(g) and thus, g^{(p-1)/q_i} = 1 mod p. The procedure will immediately output "NOT A GENERATOR", which is the correct answer. [ 5 points for the proof of the "only if" direction ] The cost of the procedure is k exponentiations where k is the number of distinct primes factors of p-1. Since k <= log_2 (p-1), we have efficiency. 6. a) phi(19) = 18 = 2^2 * 3^2 (compute the prime factorization of p-1) g = 2. g^{p-1/q_1} = 2^{18/2} = 2^9 mod 19 = (2^4)^2 * 2 = (-3)^2 * 2 = 18 mod 19 \neq 1 g^{p-1/q_2} = 2^{18/3} = 2^6 mod 19 = 7 mod 19 \neq 1 Thus, 2 is a generator of Z_19*. [ 2.5 points ] To compute dlog_2(15), do the baby step giant step algorithm. (I'll leave the simulation of this algorithm as an exercise). The answer is 11. [ 2.5 points ] b) a) phi(23) = 22 = 2^11 (compute the prime factorization of p-1) g = 2. g^{p-1/q_1} = 2^{22/2} = 2^11 mod 23 = (2^5)^2 * 2 = (9)^2 * 2 = 24 mod 19 = 1 Thus, 2 is NOT a generator of Z_23*. [ 2.5 points ] To compute dlog_2(7), do the baby step giant step algorithm. (I'll leave the simulation of this algorithm as an exercise). The discrete log does not exist. [ 2.5 points ] 7. Say x = 2^{(p-1)/2} mod p x^2 = 2^{p-1} = 1 mod p by Fermat x^2 - 1 = 0 mod p Factoring the polynomial x^2 - 1, we have: (x + 1) (x - 1) = 0 mod p. Thus, p divides (x+1)(x-1). Since p is prime, it must be the case that p divides x + 1 or p divides x - 1. Thus, x = 1 mod p OR x = -1 mod p. Thus, +1 and -1 are the two possible values of 2^{(p-1)/2} mod p. [ 5 points for the answer, 10 for a correct proof ] 8. 1a) 3 and 4 1b) 7 is a non-square mod 11. 1c) 4 and 7 [ 3 points ] 2) p-x [2 points ] 3) 1 has four square roots mod 8 -- 1, 3, 5 and 7. The theorem only applies to prime moduli. 8 is composite. [ 5 points ] 4) Suppose k is even. Say k = 2m. Then, g^m is a square root of b = g^k mod p. On the other hand, suppose b is a square. Then, b can be written as b = c^2 mod p. Since g is a generator, c can be written as c = g^n for some integer n. So, g^{2n} = g^{k} mod p. Thus, 2n = k (mod p-1). Since p-1 is even and 2n is even, k must be even. QED. [ 10 points -- 5 for the "if" direction and 5 for the "only if" direction ]