Square Roots Modulo P - Number Theory 25

[@JM-us3fr]

For the warmup problems: 1) There is no solution since 12=2 mod 5 which is not a quadratic residue. 2) Also no solution, because 55=6 mod 7 which is not a quadratic residue. I don't think these were particularly good examples. More interesting examples might be: 3) x^2=4 mod 15 4) x^2=23 mod 77 Solutions for 3: x=2, 7, 8, 13 Solutions for 4: x=10, 32, 45, 67

[@JM-us3fr]

There is an algorithm for computing the 1 mod 8 case. It's called the Tonelli-Shanks algorithm, and it runs pretty fast. It's not as pretty as a formula, and it only runs probabilistically, but it gets the job done really well.

[@AntoshaPushkin]

As far as I remember, the probabilistic part comes only from finding a quadratic non-residue, and that's not a big deal since half residues are qnr

[@JM-us3fr]

@@AntoshaPushkin Yes that’s right. Deterministically, looking for a nonresidue could take as much as (p-1)/2 steps (which would _not_ be polynomial time), but in practice the algorithm takes on average 2 steps.

[@AntoshaPushkin]

@@JM-us3fr hmmm, I wonder if this is actually true. Let's say we just go from 2 up to (p-1)/2, could we actually reach the worst case? I suspect that it could be much better than O(p), maybe O(p^c) for some 0 < c < 1, but I doubt it could be polylog(p)

[@AntoshaPushkin]

@@JM-us3fr oh, it turns out that if generalized Riemann hypothesis is true, minimal QNR is O((log p)^2), so it is polylog assuming GRH

[@JM-us3fr]

@@AntoshaPushkin yeah we definitely wouldn’t reach this worst case. There’s an even more elementary proof that shows the smallest QNR is at more sqrt(p), where the only exceptions are p=3, 7, and 23

[@lexinwonderland5741]

I love the shirt, professor!

[@AbuMaxime]

The warm-up problems are of the form x^2=na (mod np). Suppose there's an integer root r such that r^2=n (mod np). Then there's an X such that x=rX and x^2=r^2 X^2=nX^2 (mod np) . You can then solve X^2 = a (mod p). Finding r means finding a simultaneous solution to r^2=n (mod p) and r^2=n (mod n) = 0 mod n. For the first problem x^2=12 mod 15, n=3 and p=5. But it is not possible to find the root r such that r^2=3 (mod 5) (just check the Legendre symbol) , so no solution. In the second problem, n=11 and p=7. You can check that r=44 satisfies r^2=11 (mod 77). But then X^2=7 (mod 11) does not have a solution, so again no solution. I would suggest solving x^2=22 (mod 77) instead.

[@Happy_Abe]

Why does p being 5 mod 8 imply a^2 congruent to 1 mod p means a is +/-1 mod p

[@simons2006]

since p==5 (mod 8), then we square it and get p==25==1 (mod 8)

[@schweinmachtbree1013]

It doesn't, michael made a mistake; _a_ ^2 == 1 mod _p_ ⇒ _a_ == ±1 mod _p_ is true for any prime _p_ . To see this, if _a_ ^2 == 1 mod _p_ then _a_ ^2 - 1 = ( _a_ - 1)( _a_ + 1) == 0 mod _p_ so _p_ divides ( _a_ - 1)( _a_ + 1), but then _p_ must divide either _a_ - 1 or _a_ + 1 (possibly both) which correspond to _a_ - 1 == 0 and _a_ + 1 == 0 respectively, hence _a_ == ±1 mod _p_

[@Happy_Abe]

@@schweinmachtbree1013 I see so what was the mistake Saying it’s true for only 5 mod 8 primes?

[@schweinmachtbree1013]

@@Happy_Abe Yup, it's also true for the primes that are 1 mod 8, 3 mod 8, 7 mod 8, or the prime that is 2 (mod 8), because the proof _a_ ^2 ≡ 1 mod _p_ ⇔ _a_ ^2 - 1 = ( _a_ - 1)( _a_ + 1) ≡ 0 mod _p_ ⇔ _p_ divides ( _a_ - 1)( _a_ + 1) ⇔ _p_ | _a_ - 1 or _p_ | _a_ + 1 ⇔ _a_ - 1 ≡ 0 mod _p_ or _a_ + 1 ≡ 0 mod _p_ ⇔ _a_ ≡ ±1 mod _p_ doesn't use anything about the residue of _p_ modulo 8 :)

[@Happy_Abe]

@@schweinmachtbree1013 makes perfect sense thank you! I asked the question a few months ago so I forgot the context but I believe I knew this and was just confused why Michael said it’s because p is 5 mod 8. Thank you for confirming that was a mistake.

[@gregheffeley4922]

I'm kinda confused at 6:56 because how does 18/23 = (9/23) * (2/23)? Wouldn't it be (9/23) * (2/1)? Or is it just a modular thing where 23 mod (23) is the same as 46 mod (23)?

[@Boringpenguin]

These are Legendre symbols, not fractions. Maybe you should watch video 22-24 first?

[@gregheffeley4922]

@@Boringpenguin Ah okay! I understand now. Thank you!!!

[@Boringpenguin]

@@gregheffeley4922 No problem at all :)

[@JM-us3fr]

It's a property of Legendre symbols. (ab | p)=(a | p)(b | p) for all a and b, and odd primes p (personally I prefer this notation because it doesn't get confused with fractions).

[@2070user]

The thumbnail has a typo, it should be video 25 not 24