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 ]