arithmoi-0.8.0.0: Efficient basic number-theoretic functions.

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

Math.NumberTheory.Moduli.Sqrt

Contents

Description

Modular square roots.

Synopsis

# New interface

sqrtsMod :: KnownNat m => Mod m -> [Mod m] Source #

List all modular square roots.

>>> :set -XDataKinds
>>> sqrtsMod (1 :: Mod 60)
> [(1 modulo 60),(49 modulo 60),(41 modulo 60),(29 modulo 60),(31 modulo 60),(19 modulo 60),(11 modulo 60),(59 modulo 60)]


sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer] Source #

List all square roots modulo a number, which factorisation is passed as a second argument.

>>> sqrtsModFactorisation 1 (factorise 60)
[1,49,41,29,31,19,11,59]


List all square roots modulo power of a prime.

>>> sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
[4,5]
>>> sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
[3,12,21,24,6,15]


List all square roots by prime modulo.

>>> sqrtsModPrime 1 (fromJust (isPrime 5))
[1,4]
>>> sqrtsModPrime 0 (fromJust (isPrime 5))
[0]
>>> sqrtsModPrime 2 (fromJust (isPrime 5))
[]


# Old interface

Deprecated: Use sqrtsModPrime instead

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.

Deprecated: Use sqrtsModPrime instead

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.

Deprecated: Use sqrtsModPrime instead

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.

Deprecated: Use sqrtsModPrime instead

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.

Deprecated: Use sqrtsModPrimePower instead

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 #

Deprecated: Use sqrtsModPrimePower instead

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 #

Deprecated: Use sqrtsModFactorisation or sqrtsMod instead

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 #

Deprecated: Use sqrtsModFactorisation or sqrtsMod instead

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.