Expand description
Tonelli-Shanks algorithm implementation for computing square roots modulo a prime.
This library provides functions to compute square roots in the finite field Z/pZ where p is an odd prime number.
Functionsยง
- find_
quadratic_ non_ residue - Finds the first quadratic non-residue modulo p
- legendre_
symbol - Computes the Legendre symbol (a/p)
- pow_mod
- Computes modular exponentiation: x^n mod p
- square_
roots - Computes both square roots of n modulo p
- tonelli_
shanks - Computes a square root of n modulo p using the Tonelli-Shanks algorithm