Finding Mod-p Square Roots with the Tonelli-Shanks Algorithm

[@MrCoreyTexas]

I had never heard that odd primes are congruent to either 1 or 3 mod 4, thanks for teaching me something new today! I'll have to think about that.

[@MrCoreyTexas]

Euler was an astounding mathematician, I didn't know about Euler's criterion until now

[@anntakamaki1960]

Awesome video sir ❤

[@Ubertech-v6t]

where is i can find code from video?please answer🙏🙏🙏

[@pizdataya6604]

thank you!

[@MrCoreyTexas]

Maybe you could give some insight as to why it's called a quadratic residue? I guess that sounds better than "has an integer square root mod p"? Would a cube root be called a cubic residue and so on?

[@JacksonInfoSec]

You should interpret "residue" as a synonym for "remainder" (with respect to some modulus). Also "quadratic" should be interpreted as "squaring". So, an integer r is a quadratic residue modulo n if there exists an integer x such that x^2=r( mod n). Namely, r is the remainder of a perfect square modulo n. For example with the modulus of 4, the congruence x^2=r (mod 4) is solvable only for r=0 or r=1, and not solvable for r=2 or r=3. So 0 and 1 are the quadratic residues modulo 4. So, we would say r is a cubic residue modulo n if the congruence x^3=r(mod n) is solvable.

[@schrodingerbracat2927]

nice! btw, on Python 3, one can use formatted strings in print statements.

[@trollmole8637]

For the loop where you dividing by two can’t you just do bit search … as in it is odd only if least significant bit is 1… ie you just searching for first occurrence of 1 .. and shift that number of bits.

[@JacksonInfoSec]

Yes you could.

[@MrCoreyTexas]

Now I know one of the reasons Bitcoin picked SECP256K1, the prime it uses is congruent to 3 mod 4, so it's way easier to find your y's given an x, which is important when they compress public keys and only say whether y is even or odd