Stability of Floating Bodies

Lecture 11 Square Roots, Tonelli's Algorithm, Number of Consecutive Pairs of Squares mod p Defined the Jacobi Symbol - used to compute Legendre Symbol efficiently (quadratic character) Eg. (1729|223) = (168|223) = (4 · 42|223) = (42|223) = (2|223)(21|223) = (21|223) = (223|21) = (13|21) = (21|13) = (8|13) = (2|13) = −1 ( −1 if p ≡ 3 mod 4 (−1|p) = 1 if p ≡ 1 mod 4 ( −1 if p ≡ ±3 (2|p) = 1 if p ≡ ±1 mod 8 mod 8 Lemma 43. If p, q, r are distinct odd primes, and q ≡ r mod 4p, then (p|q) = (p|r). Proof. We know (q|p) = (r|p) since q ≡ r mod p. Also, q and r are both either 1 mod 4 or both 3 mod 4. So (−1) p−1 q−1 2 2 = (−1) p−1 r −1 2 2 (p|q) = (q|p)(−1) = (r|p)(−1) = (p|r) p−1 q−1 2 2 p−1 r −1 2 2  Eg. Characterize the primes p for which 17 is a square mod p. It’s clear that 17 is square mod 2. We see that since 17 ≡ 1 mod 4, so if q ≡ r mod 17 then (17|q) = (17|r). So we only need to look mod 17 to see when (17|q) = (q|17) = 1. Go through mod 17: ±1, ±2, ±4, ±8 mod 17 are nonzero square classes, so 17 is a square mod q iff q = 2, 17, or ±1, ±2, ±4, ±8 mod 17. If we had asked for 19, we need to look at classes mod (4 · 19), since 19 6≡ 1 mod 4. (If q = 1 mod 4 then (19|q) = (q|19), so we need q to be a square mod 19. If q = 3 mod 4 then (19|q) = −(q|19), we need q to be not square mod 19) Euclidean gcd Algorithm - Given a, b ∈ Z, not both 0, find (a, b) 1 1. If a, b < 0, replace with negative 2. If a > b, switch a and b 3. If a = 0, return b 4. Since a > 0, write b = aq + r with 0 ≤ r < a. Replace (a, b) with (r, a) and go to Step 3. Tonelli’s Algorithm - To compute square roots mod p (used to solve x2 ≡ a mod p). Need a quadratic non-residue mod p, called n. Let g be a primitive root mod p. Now let p − 1 = 2s t, for t odd. We know n is a power of g, say n ≡ g k . Set c ≡ nt ≡ g kt . Claim: The order of c is exactly 2s . Proof. s c2 ≡ (g kt )2 s s ≡ (g t2 )k ≡ (g p−1 )k ≡ 1 mod p s−1 So ord(c) has to divide 2s , so it’s a power of 2. If we can show that c2 mod p then order has to be 2s . s−1 c2 6≡ 1 s−1 ≡ (g kt )2 ≡ (g t2 s−1 )k ≡ (g (p−1)/2 )k k ≡ (−1) mod p mod p, since g is a primitive root Note that k is odd since otherwise n ≡ g k would be a quadratic residue, so we s−1 get c2 ≡ −1 mod p, proving claim that ord(c) = 2s  Lemma 44. If a, b are coprime to p and have order 2j mod p (for j > 0) then ab has order 2k for some k < j. j j−1 Proof. Since a2 ≡ 1 mod p, (a2 )2 ≡ 1 mod p, we have a2j−1 ≡ ±1 mod p. j−1 j −1 So we must have a2 ≡ −1 mod p, since ord(a) = 2j . Similarly b2 ≡ −1 j−1 mod p. Therefore, (ab)2 ≡ 1 mod p, so order has to divide 2j−1 , so k < j.  2 Proof of Tonelli’s Algorithm. First check (by repeated squaring) if a(p−1)/2 ≡ 1 mod p . If not, terminate with ”false.” So assume now on that a(p−1)/2 ≡ 1 mod p. Set A = a and b = 1. At each step a = Ab2 (a ≡ Ab2 mod p) At the end, want A = 1, so b is square root of a mod p. Each step: decrease the power of 2 dividing the order of A. To start with, s−1 A(p−1)/2 = A2 t ≡ 1 mod p. Check if A(p−1)/4 ≡ 1 mod p. s−2 s−2 If not, then A2 t ≡ −1 mod p (since (A2 t )2 ≡ 1 mod p). So powers of 2 dividing ord(A) is exactly 2s−1 . Same as the power of 2 diving ord (c2 ) = 2s−1 . So set A = Ac−2 , b = bc mod p. Notice that s−2 s−2 (Ac−2 )2 t A2 t c2s−1 t ≡ (−1)(−1)t ≡ 1 mod p = ord (Ac−2 ) divides 2s−2 t, so power of 2 dividing the order is at most 2s−2 , so has decreased by 1. s−2 If yes, (ie., A2 t ≡ 1 mod p), do nothing. s−3 Next step: check if A2 t = A(p−1)/8 ≡ 1 mod p. s−3 If no, (ie., A2 t ≡ −1 mod p, set A := Ac−4 , b := bc2 (c4 has order 2s−2 ). s−3 (Ac−4 )2 t ≡ 1. If yes, do nothing. After at most s steps we’ll reach the stage when a ≡ Ab2 mod p and the power of 2 dividing ord(A) is 1 - ie., ord(A) is odd. Now we just compute a square root of A as follows: ord(A) odd and divides p − 1 ≡ 2s t, so divides t. So At ≡ 1 mod p (t odd). Claim A(t+1)/2 is a square root of A mod p. (A(t+1)/2 )2 = At+1 = At A ≡1·A ≡ A mod p √ So algorithm just returns bA(t+1)/2 as a  Eg. If p ≡ 3 mod 4, a is quadratic residue mod p, then a square root of a is a(p+1)/4 (square = a(p+1)/2 = a(p−1)/2 a ≡ a mod p) Efficient poly-log time assuming we can find a quadratic non-residue n efficiently. A random number is quadratic non-residue with probability 12 so if 3 k we run k trials, probability of not getting a quadratic non-residue is 12 which is p1k if k is log p. So, this is an efficient randomized algorithm. No efficient deterministic algorithm has yet been found. Simplest is to check all primes, expect quadratic non-residue mod p which is less than c(log(p))2 ⇒ true if assume ERH. Question: Pairs of squares problem. How many numbers x mod p such that x and x + 1 mod p are both squares mod p? Rough heuristic - if x, x + 1 were independent, roughly p4 solutions. P Define (0|p) = 0. Then x mod p (x|p) = 0. Also, number of solutions to y 2 ≡ x mod p for fixed x is 1 + (x|p). Also, if x 6≡ 0 then 12 (1 + (x|p)) is 1 if x is a square, 0 if x is not a square. So, number of x that x, x + 1 are squares: X 1 1 1 1 + (1 + (−1|p)) + (1 + (x|p)) (1 + (x + 1|p)) |{z} 2 2 2 | {z } x mod p x=0 x=−1 Now X x mod p x=0,−1 6 x=0,−1 6 1 (1 + (x|p) + (x + 1|p) + (x|p)(x + 1|p)) 4 4 1X p−2 1= 4 4 ! X 1 1 X (x|p) = (x|p) − (0|p) − (−1|p) 4 4 all 1 = − (−1|p) 4 ! 1X 1 X (x + 1|p) = (x + 1|p) − (1|p) − (0|p) 4 4 all 1 =− 4 1X 1X (x|p)−1 (x + 1|p) (x|p)(x + 1|p) = 4 4   1X x+1 = |p 4 x   1 1 X = 1 + |p 4 x 6 ,−1 x=0 1 X = (x|p) 4 6 ,−1 x=0 1 =− 4 Add them up to get p + 2 + (−1|p) 4 If we want x − 1, x, x + 1 to all be squares, much more complicated 5