Math.NumberTheory.Moduli.Sqrt

Modular square roots.

Documentation

sqrtModP :: Integer -> Integer -> Maybe Integer

sqrtModP n prime calculates a modular square root of n modulo prime if that exists. The second argument must be a (positive) prime, otherwise the computation may not terminate and if it does, may yield a wrong result. The precondition is not checked.

If prime is a prime and n a quadratic residue modulo prime, the result is Just r where r^2 ≡ n (mod prime), if n is a quadratic nonresidue, the result is Nothing.

sqrtModPList :: Integer -> Integer -> [Integer]

sqrtModPList n prime computes the list of all square roots of n modulo prime. prime must be a (positive) prime. The precondition is not checked.

sqrtModP' :: Integer -> Integer -> Integer

sqrtModP' square prime finds a square root of square modulo prime. prime must be a (positive) prime, and square must be a positive quadratic residue modulo prime, i.e. 'jacobi square prime == 1. The precondition is not checked.

tonelliShanks :: Integer -> Integer -> Integer

tonelliShanks square prime calculates a square root of square modulo prime, where prime is a prime of the form 4*k + 1 and square is a positive quadratic residue modulo prime, using the Tonelli-Shanks algorithm. No checks on the input are performed.

sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer

sqrtModPP n (prime,expo) calculates a square root of n modulo prime^expo if one exists. prime must be a (positive) prime. expo must be positive, n must be coprime to prime

sqrtModPPList :: Integer -> (Integer, Int) -> [Integer]

sqrtModPPList n (prime,expo) calculates the list of all square roots of n modulo prime^expo. The same restriction as in sqrtModPP applies to the arguments.

sqrtModF :: Integer -> [(Integer, Int)] -> Maybe Integer

sqrtModF n primePowers calculates a square root of n modulo product [p^k | (p,k) <- primePowers] if one exists and all primes are distinct. The list must be non-empty, n must be coprime with all primes.

sqrtModFList :: Integer -> [(Integer, Int)] -> [Integer]

sqrtModFList n primePowers calculates all square roots of n modulo product [p^k | (p,k) <- primePowers] if all primes are distinct. The list must be non-empty, n must be coprime with all primes.