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

Показать описание

In this video we review the theory of quadratic residues of an odd prime and then implement the Tonelli-Shanks algorithm in Python to find a square root. We end the video by showing how we can use this algorithm to find points with given x-values on real world elliptic curves.

Code:

JacksonInfoSec

Рекомендации по теме

Комментарии

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

MrCoreyTexas

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

Ubertech-vt

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

schrodingerbracat

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?

MrCoreyTexas

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.

trollmole

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

MrCoreyTexas

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

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

Square roots mod p -- Number Theory 25

Quadratic Residues - Finding Square Roots (mod p) - Part 11

Square Root Modulo Prime Number

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

Number Theory | When is there a square root of 2 modulo p?

Square Roots Modulo P — Number Theory 25

MATA02 - Lecture 10d - Roots in modular arithmetic using Euler's Theorem

KCET 2025 Chemistry Weekly Test Series | Mock Test 9 Solution

Square roots modulo p, number theory

Something Strange Happens When You Keep Squaring

MATA02 - Lecture 9d - Roots in modular arithmetic (with prime modulus)

Quadratic Residues - Finding Square Roots (mod n) - Part 12

Solving congruences, 3 introductory examples

Mod of a Number - How to find using calculator?

What does a ≡ b (mod n) mean? Basic Modular Arithmetic, Congruence

This completely changed the way I see numbers | Modular Arithmetic Visually Explained

Cryptography Fundamentals 7: Quadratic residues Mod N Podcast

Number Theory | Primitive Roots modulo n: Definition and Examples

What is a Quadratic Residue? - Definition and Example

why sqrt(36) is just positive 6

Number Theory | When is 5 a perfect square mod p?

Mod 1 square roots

Square Roots mod 4m+3 Example