10/29 15-859(D) Randomized algorithms Randomized algorithms for number-theoretic problems. Today: number theory intro, develop from first principles. ============================================================================== 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). (If d divides a, and d divides b, then d divides a-kb.) 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?) Extended GCD helps because anything of the form ax+by must be a multiple of gcd. (since gcd divides a and gcd divides b, it also divides ax+by) 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. 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^*|. E.g., phi(p) = p-1. If n= p1^e1 * p2^e2 *...* pk^ek, then: phi(n) = (p1 - 1)*p1^{e1 - 1}*...*(pk - 1)*pk^{ek - 1} E.g., if n=pq, then phi(n)=(p-1)(q-1), which we can see by listing the numbers {1,...,n} then removing the q multiples of p, then removing the p multiples of q, and then realizing that we removed n twice. In general, you can figure out the formula by straight calculation. From the factorization of n we can get phi(n). Also vice-versa. Not obvious in general but easy for n=pq. E.g., n=pq. phi(n)=(p-1)(q-1). So, phi(n) = (n/q - 1)(q - 1), and we can solve the quadratic equation to get 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). ====================================================================== This suggests a primality test: take a^{n-1} mod n. If you don't get 1, then you know that n is not prime. This is a nice easy certificate of compositeness. Of course maybe a^{n-1} = 1 mod n, and yet n is composite. We'll see a primality testing algorithm based on this later. ====================================================================== 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. In fact, we can see what's going on in terms of the generator, by writing Z_p^* as: {1, g, g^2, ..., g^{p-2}} All the even powers of g are clearly quadratic residues, so the odd powers of g must be the non-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.