3/17 15-682 Randomized Algorithms Randomized algorithms for number-theoretic problems. Today: number theory intro. ============================================================================== number problems: if you're given number n, goal is to be poly in log(n). E.g., GCD(a,b). Euclid: for a>b, gcd(a,b) = gcd(b, a mod b). (note: a+b goes down by a constant factor each step) Extended GCD: finds gcd d and numbers x and y such that d=ax+by. One nice thing about extended GCD: lets you check your answer. (it's easy to check that d divides both, but how do you know d is the largest? --> if d'|a and d'|b then d'|ax+by so d'|d.) ("|" = "divides") Z_n = {0,1,...,n-1}. Z_n^* = {a in Z_n s.t. gcd(a,n)=1} -> group under *. Given a in Z_n^*, can compute a^{-1} in poly time. --> compute gcd(a,n), get x,y s.t. ax+ny=1. So, x = a^{-1} mod n. Chinese Remainder Theorem ------------------------- Say n1, n2, ..., nk are (pairwise) relatively prime. n=n1*n2*...*nk. Chinese remainder theorem: for any r1 in Z_n1, r2 in Z_n2, ..., rk in Z_nk there is a unique r such that r = r_i mod n_i. (and we can compute this efficiently). Another way to look at this is: note that |Z_n| = |Z_n1 x Z_n2 x ... x Z_nk|. Consider the mapping from Z_n to Z_n1 x Z_n2 x ... x Z_n r -> (r mod n1, r mod n2, ..., r mod nk). Chinese remainder Theorem: this map is 1-1, and furthermore there's an efficient inverse. Story: want to figure out how many troops. We know less than 1000, but want to calculate exactly. So, ask to get into groups of 9, how many left over? 11, how many left over? 13, how many left over? ==> figure out how many. Proof: Sufficient to show that the mapping is onto (which implies 1-1 since the domain and the range are the same size). Let's first figure out how to map back from (0...010...0). Look at n/ni. This is congruent to 0 mod nj for j!=i, and rel prime to ni. So, we're almost there. Just multiply by mi = (n/ni)^{-1} mod ni. I.e., mi*(n/ni) = (0...010...0). Now, we can map back from (r1,...,rk) by just adding multiples: sum_i ri*mi*(n/ni) (mod n). ========================================================================= Euler phi function: phi(n) = |Z_n^*|. If n= p1^e1 * p2^e2 *...* pk^ek, then phi(n) = (p1 - 1)*p1^{e1 - 1}*...*(pk - 1)*pk^{ek - 1} So, from the factorization of n we can get phi(n). Also vice-versa. E.g., n=pq. phi(n)=(p-1)(q-1). So, m = n - phi(n) + 1 = p+q. Given pq and p+q can solve quadratic equation to get p and q. Euler's Theorem: a^{phi(n)} = 1 (mod n). Proof: Standard defn: order(a) = smallest t such that a^t = 1 (mod n). Note that {1, a, a^2, ..., a^{t-1}} is a subgroup of Z_n^*: it's closed under multiplication and inverses. Now we can use a basic fact from group theory that the order of any subgroup divides the order of the group. Pf: Say H is a subgroup of G and y is not in H. Then the coset yH = {yh : h in H} is a set of size |H| (if y*h1 = y*h2 then h1 = h2) and is disjoint from H (if y*h1 = h2 then y = h2*h2^{-1}, which is in H by H's group closure properties). Furthermore, all cosets are disjoint (if z*h1 = y*h2 then z = y*h3 for some h3 in H). So, phi(n) = b*t for some b, and a^{phi(n)} = (a^t)^b = 1 (mod n). ====================================================================== Generators g is a generator of G if order(g) = |G|. If there exists a generator, then G is cyclic. E.g., (Z_n, +) is cyclic with generator 1. E.g., any group of prime order (size) is cyclic. Why? Theorem: for prime p, Z_p^* is cyclic. (Note: Z_p^* does NOT have prime order) Proof: Will follow from two claims: Claim 1: at most phi(k) elements of order k. Claim 2: sum_{k dividing p-1} phi(k) = p-1. Given these claims, can argue as follows: every element has some order that divides p-1, so, grouping them by order, we have: sum_{k dividing p-1} (# elts with order k) = p-1. By claims 1&2, this can only happen if a stronger version of claim 1 holds, namely if there are *exactly* phi(k) elements of order k. Therefore, there are phi(p-1) generators. Proof of claim 1: All elements with order k are roots of (x^k - 1) = 0 mod p. Since we have a field, there are at most k roots. If a has order k, then {1, a, a^2, ..., a^{k-1}} are these k roots. But, only those a^l such that gcd(l,k)=1 can possibly have order *exactly* k (all the rest can only have some order that divides k) and there are phi(k) such l's. Proof of claim 2: p-1 = sum_{k dividing p-1} (#a in {1,...,p-1} : gcd(a,p-1)=k) = sum_{k dividing p-1} (#b in {1,...,(p-1)/k} : gcd(b,(p-1)/k)=1) = sum_{k dividing p-1} phi((p-1)/k) = sum_{k dividing p-1} phi(k). ======================================================================== Quadratic residues: a is a quadratic residue (mod n) if there exists x such that x^2 = a (mod n) Claim: Every residue has exactly two square roots x, -x modulo a prime p. Proof: if x^2 = y^2 (mod p), then (x-y)*(x+y) = 0 (mod p), so either p | x-y (i.e., x=y) or p | x+y (i.e., x=-y). Note this implies a key fact: exactly half of the numbers in Z_p^* are quadratic residues. Slight digression: if n=pq, and we have an algorithm that computes square roots, then we can factor. Proof: take a random x and square it to get a. a has 4 roots: x, -x, y, -y (mod n). Pf: define xp, xq s.t., xp^2 = a (mod p) and xq^2 = a (mod q). The roots are: (xp, xq), (xp, -xq), (-xp, xq), (-xp, -xq) using CRT notation. Now, if we run our square-root-finder, it will return one of {y,-y} with prob 1/2. So, (x-y)*(x+y) = 0 (mod n) and p | x-y and q | x+y. Take gcd(n, x-y) and get p, etc. Legendre symbol: [a/p] = +1 if a is a residue mod p, and -1 if a is a nonresidue mod p. Theorem: [a/p] = a^{(p-1)/2} (mod p). Proof: If a=x^2 (mod p) then a^{(p-1)/2} = x^{p-1} = 1 (mod p). If a is a non-residue, then we use the fact that Z_p^* is cyclic and therefore has a generator g. Since a is a nonresidue, it must be that a=g^k (mod p) for some odd k. So, a^{(p-1)/2} = g^{(p-1)/2} = -1 (mod p). This suggests an idea for primality testing: we know that a^{(p-1)/2} is 1 or -1 (mod n) when n is prime. So if we ever see something else, then we know n is composite. We'll see a provably good version of this next time.