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 ]