Suppose p is an odd prime and a QR_p . Show that: (a) p 1 (mod 4) a QR_p .

(b) p 3 (mod 4) a QR_p

Hints: When is even/odd? When is 1 QR_p?

(Q => Rational Number, R => Real Number)

. |A the number of elements in set A. . Euler's Theorem: For each n > 1 and a e zi: ar(n) 1 (mod n) g is a primitive element ofZi iff (g1,g2,.. .g)-Z . Suppose g is a primitive element of Z, For a E Zn, the discrete log of a to the base g mod p (written: dlog8(a)) is the solution for x of a (mod m), ie., gog) a (mod m). DEFINITION. Suppose a, n e Z with n > 1 and a 0. (a) a is a quadratic residue mod n when x2a (mod n) has a solution, otherwise a is a nonresidue (b) QRn -the quadratic residues mod n CoNVENTIoN. Below, let p be an odd prime and a E (Z-10 EULER'S CRITERION. a e QRp a 1 (mod p) LEMMA 1.-": 1 (mod p). PROPOSITION 2. Suppose p 3 (mod 4) and b-a (mod p) Then: either a E QRp with roots b or else-a e QRp with roots b Suppose g is a primitive ele- THEorem 3 (ANoTHER CR ment of Z: Then: g' Rp j is even. ITERION). Shamir's Secret Sharing Scheme Parameters. k = # of participants, t-threshold where 0