arithmoi-0.6.0.1: Efficient basic number-theoretic functions.

Copyright (c) 2011 Daniel Fischer MIT Andrew Lelechenko Provisional Non-portable (GHC extensions) None Haskell2010

Math.NumberTheory.Moduli.Sqrt

Description

Modular square roots.

Synopsis

Documentation

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 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' 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 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 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] Source #

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 Source #

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] Source #

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.