Question 4: Let p be an odd prime. We say that a Z p is a square number if there is x Z p so that x 2 = a mod p .

(a) Show that the number of squares is exactly ( p 1) / 2.

(b) Let p be a prime. Consider the function square ( a ) , a Z p that equals 1 if a is a square, and equals 1 otherwise. Prove that a ( p 1) / 2 mod p is a square.

(c) Say that p = 4 x + 3 (it can only be 4 x + 1 or 4 x + 3 so we assume its not 4 x + 1). Say that a is a square with respect to p . Show that x = a k +1 mod p is a square root of a . Namely x 2 = a mod p . 1

(d) Give a polynomial algorithm (assuming that you can tell if a number n is prime in O (log n ) time) that find a non square a in Z p