Let p = 2203, q = 2207, n = p q = 4862021, and a = 4472388; p and q are prime and a QR_n . Compute the four square roots of a in . Use the Chinese Remainder Theorem technique.

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

. |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 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