Copyright	(c) 2011 Daniel Fischer
License	MIT
Maintainer	Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell	None
Language	Haskell2010

Math.NumberTheory.Moduli.Sqrt

Contents

Modular square roots
Jacobi symbol

Description

Modular square roots and Jacobi symbol.

Synopsis

sqrtsMod :: forall (m :: Nat). 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
- = MinusOne
- | Zero
- | One
jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol
symbolToNum :: Num a => JacobiSymbol -> a

Modular square roots

sqrtsMod :: forall (m :: Nat). 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.

Constructors

MinusOne

Zero

One

Instances

Instances details

Semigroup JacobiSymbol Source #

Instance details

Defined in Math.NumberTheory.Moduli.JacobiSymbol

Methods

(<>) :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol #

sconcat :: NonEmpty JacobiSymbol -> JacobiSymbol #

stimes :: Integral b => b -> JacobiSymbol -> JacobiSymbol #

Show JacobiSymbol Source #

Instance details

Defined in Math.NumberTheory.Moduli.JacobiSymbol

Methods

showsPrec :: Int -> JacobiSymbol -> ShowS #

show :: JacobiSymbol -> String #

showList :: [JacobiSymbol] -> ShowS #

Eq JacobiSymbol Source #

Instance details

Defined in Math.NumberTheory.Moduli.JacobiSymbol

Methods

(==) :: JacobiSymbol -> JacobiSymbol -> Bool #

(/=) :: JacobiSymbol -> JacobiSymbol -> Bool #

Ord JacobiSymbol Source #

Instance details

Defined in Math.NumberTheory.Moduli.JacobiSymbol

Methods

compare :: JacobiSymbol -> JacobiSymbol -> Ordering #

(<) :: JacobiSymbol -> JacobiSymbol -> Bool #

(<=) :: JacobiSymbol -> JacobiSymbol -> Bool #

(>) :: JacobiSymbol -> JacobiSymbol -> Bool #

(>=) :: JacobiSymbol -> JacobiSymbol -> Bool #

max :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol #

min :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol #

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 -- arguments have a common factor 11
Zero
>>> jacobi 1001 9907
MinusOne

symbolToNum :: Num a => JacobiSymbol -> a Source #

Convenience function to convert out of a Jacobi symbol