Copyright | (c) 2011 Daniel Fischer |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Modular square roots.
Synopsis
- sqrtsMod :: KnownNat m => Mod m -> [Mod m]
- sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer]
- sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer]
- sqrtsModPrime :: Integer -> Prime Integer -> [Integer]
- sqrtModP :: Integer -> Integer -> Maybe Integer
- sqrtModPList :: Integer -> Integer -> [Integer]
- sqrtModP' :: Integer -> Integer -> Integer
- tonelliShanks :: Integer -> Integer -> Integer
- sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer
- sqrtModPPList :: Integer -> (Integer, Int) -> [Integer]
- sqrtModF :: Integer -> [(Integer, Int)] -> Maybe Integer
- sqrtModFList :: Integer -> [(Integer, Int)] -> [Integer]
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, the factorisation of which is passed as a second argument.
>>>
sqrtsModFactorisation 1 (factorise 60)
[1,49,41,29,31,19,11,59]
sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer] Source #
List all square roots modulo the power of a prime.
>>>
import Data.Maybe
>>>
import Math.NumberTheory.Primes
>>>
sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
[4,5]>>>
sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
[3,12,21,24,6,15]
sqrtsModPrime :: Integer -> Prime Integer -> [Integer] Source #
List all square roots by prime modulo.
>>>
import Data.Maybe
>>>
import Math.NumberTheory.Primes
>>>
sqrtsModPrime 1 (fromJust (isPrime 5))
[1,4]>>>
sqrtsModPrime 0 (fromJust (isPrime 5))
[0]>>>
sqrtsModPrime 2 (fromJust (isPrime 5))
[]
Old interface
sqrtModP :: Integer -> Integer -> Maybe Integer Source #
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
.
sqrtModPList :: Integer -> Integer -> [Integer] Source #
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.
sqrtModP' :: Integer -> Integer -> Integer Source #
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.
tonelliShanks :: Integer -> Integer -> Integer Source #
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.
sqrtModPP :: Integer -> (Integer, Int) -> Maybe Integer Source #
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.