Math 110: 2/23 Computing square roots mod p (Tonelli's algorithm)

In live lecture, we've been talking about quadratic residues and non-residues, but so far actually finding square roots mod a prime p has been a matter of making a table of squares -- is this really the best we can do? There turns out to be a much better algorithm (the Tonelli-Shanks algorithm) that runs in a fraction of the time, found by Tonelli in 1891 and rediscovered by Shanks in 1973. On our way to understanding this algorithm, we uncover additional structure of the quadratic residues mod p.

[lavafroth]

The most understandable explanation of Tonelli's algorithm I've come across so far. Thanks a lot!

[ferverrel]

You sir are the man. The best video breakdown I’ve come across! Thank you

[SigSelect]

There are a couple instances of this proof online, notably it is used on the Wikipedia page. They are some of the most opaque derivations I have stumbled across but this version was very clear and each step was well motivated and justified. It is still a hard proof, but this breaks it apart and modularizes it allowing one to better reason about the inspiration behind it rather than simply verifying it is correct.

[JorgeIbanez]

Hey, very nice video and such a great explanation, I hadn't found detailed information about this on the internet without using group theory until I checked out this video, it was very helpful.

[ferverrel]

How do you have such a small following you have great vids

[vlyoni]

Hey man, great video, I'm surprised it has only a few views! It really helped me understand the Tonelli algorithm (by the way, is this the same as Tonelli-Shanks or is that a variation?) and you explained it very well.

Funny timing on this video - you uploaded it on February 24, 2022, which is exactly the date that Tavis Ormandy (Google Project Zero) reported his vulnerability CVE-2022-0778 to OpenSSL. This is a vulnerability in the implementation of the Tonelli-Shanks algorithm in OpenSSL - it does not verify that the input prime is actually a prime, and if you feed it a composite number it can be made to go into an infinite loop. This was actually the source of my interest in the algorithm which led me to your video!

[aymenaymen]

hello friends i m from the future 2050 and the quantum computer is here he is really big step for cryptography and hacking and all of the other things,
the world is good place then 2027 so i hope you can live until 2050 goodbye