Copyright | (c) 2011 Daniel Fischer |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Modular square roots and Jacobi symbol.
Synopsis
- sqrtsMod :: SFactors Integer m -> Mod m -> [Mod m]
- sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer]
- sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer]
- sqrtsModPrime :: Integer -> Prime Integer -> [Integer]
- data JacobiSymbol
- jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol
- symbolToNum :: Num a => JacobiSymbol -> a
Modular square roots
sqrtsMod :: SFactors Integer m -> Mod m -> [Mod m] Source #
List all modular square roots.
>>>
:set -XDataKinds
>>>
sqrtsMod sfactors (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))
[]
Jacobi symbol
data JacobiSymbol Source #
Represents three possible values of Jacobi symbol.
Instances
jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol Source #
Jacobi symbol of two arguments. The lower argument ("denominator") must be odd and positive, this condition is checked.
If arguments have a common factor, the result
is Zero
, otherwise it is MinusOne
or One
.
>>>
jacobi 1001 9911
Zero -- arguments have a common factor 11>>>
jacobi 1001 9907
MinusOne
symbolToNum :: Num a => JacobiSymbol -> a Source #
Convenience function to convert out of a Jacobi symbol