-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Natural number arithmetic
--   
--   This package implements a library of natural number arithmetic,
--   including Montgomery multiplication, the Miller-Rabin primality test,
--   Lucas sequences, the Williams p+1 factorization method, continued
--   fraction representations of natural number square roots, the Jacobi
--   symbol, the Tonelli-Shanks algorithm for finding square roots modulo a
--   prime, and the Chakravala method for solving the Pell equation.
@package arithmetic
@version 1.6


module Arithmetic.ContinuedFraction
newtype ContinuedFraction
ContinuedFraction :: (Natural, [Natural]) -> ContinuedFraction
[unContinuedFraction] :: ContinuedFraction -> (Natural, [Natural])
fromNatural :: Natural -> ContinuedFraction
goldenRatio :: ContinuedFraction
naturalLogarithmBase :: ContinuedFraction
convergentsFn :: (Natural -> a) -> (a -> a -> a) -> (a -> a -> a) -> [Natural] -> a -> a -> [a]
numerators :: (Natural -> a) -> (a -> a -> a) -> (a -> a -> a) -> ContinuedFraction -> [a]
denominators :: (Natural -> a) -> (a -> a -> a) -> (a -> a -> a) -> ContinuedFraction -> [a]
convergents :: (Natural -> a) -> (a -> a -> a) -> (a -> a -> a) -> (a -> a -> a) -> ContinuedFraction -> [a]
unstableConvergents :: Eq a => [a] -> [a]
fractionalConvergents :: Fractional a => ContinuedFraction -> [a]
rationalConvergents :: ContinuedFraction -> [Rational]
toDouble :: ContinuedFraction -> Double
fromRealFrac :: RealFrac a => a -> ContinuedFraction
invert :: ContinuedFraction -> Maybe ContinuedFraction
instance GHC.Classes.Eq Arithmetic.ContinuedFraction.ContinuedFraction
instance GHC.Show.Show Arithmetic.ContinuedFraction.ContinuedFraction


module Arithmetic.Lucas
advance :: (a -> a -> a) -> (a -> a -> a) -> a -> a -> a -> a -> a
sequence :: (a -> a -> a) -> (a -> a -> a) -> a -> a -> a -> a -> [a]
uSequence :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> a -> a -> [a]
vSequence :: a -> (a -> a -> a) -> (a -> a -> a) -> a -> a -> [a]


module Arithmetic.Random
randomPairWith :: (a -> b -> c) -> (Random -> a) -> (Random -> b) -> Random -> c
randomPair :: (Random -> a) -> (Random -> b) -> Random -> (a, b)
randomMaybe :: (Random -> Maybe a) -> Random -> a
randomFilter :: (a -> Bool) -> (Random -> a) -> Random -> a
randomWidth :: Natural -> Random -> Natural
randomOdd :: Natural -> Random -> Natural
randomCoprime :: Natural -> Random -> (Natural, Natural)


module Arithmetic.Utility
distance :: Natural -> Natural -> Natural
functionPower :: (a -> a) -> Natural -> a -> a
multiplyExponential :: (a -> a -> a) -> a -> a -> Natural -> a
factorTwos :: Natural -> (Natural, Natural)
factorOut :: Natural -> Natural -> (Natural, Natural)


module Arithmetic.Ring
data Ring a
Ring :: (Natural -> a) -> (a -> a -> a) -> (a -> a) -> (a -> a -> a) -> (a -> a -> Maybe a) -> Ring a
[fromNatural] :: Ring a -> Natural -> a
[add] :: Ring a -> a -> a -> a
[negate] :: Ring a -> a -> a
[multiply] :: Ring a -> a -> a -> a
[divide] :: Ring a -> a -> a -> Maybe a
zero :: Ring a -> a
one :: Ring a -> a
two :: Ring a -> a
double :: Ring a -> a -> a
subtract :: Ring a -> a -> a -> a
square :: Ring a -> a -> a
exp :: Ring a -> a -> Natural -> a
exp2 :: Ring a -> a -> Natural -> a
divides :: Ring a -> a -> a -> Bool
invert :: Ring a -> a -> Maybe a


module Arithmetic.Polynomial
data Polynomial a
Polynomial :: Ring a -> [a] -> Polynomial a
[carrier] :: Polynomial a -> Ring a
[coefficients] :: Polynomial a -> [a]
fromCoefficients :: Eq a => Ring a -> [a] -> Polynomial a
zero :: Ring a -> Polynomial a
isZero :: Polynomial a -> Bool
constant :: Eq a => Ring a -> a -> Polynomial a
destConstant :: Polynomial a -> Maybe a
isConstant :: Polynomial a -> Bool
fromNatural :: Eq a => Ring a -> Natural -> Polynomial a
one :: Eq a => Ring a -> Polynomial a
multiplyByPower :: Polynomial a -> Natural -> Polynomial a
monomial :: Eq a => Ring a -> a -> Natural -> Polynomial a
variablePower :: Eq a => Ring a -> Natural -> Polynomial a
variable :: Eq a => Ring a -> Polynomial a
degree :: Polynomial a -> Natural
leadingCoefficient :: Polynomial a -> Maybe a
nthCoefficient :: Polynomial a -> Natural -> a
isMonic :: Eq a => Polynomial a -> Bool
evaluate :: Polynomial a -> a -> a
addCoefficients :: Ring a -> [a] -> [a] -> [a]
add :: Eq a => Polynomial a -> Polynomial a -> Polynomial a
negate :: Polynomial a -> Polynomial a
multiply :: Eq a => Polynomial a -> Polynomial a -> Polynomial a
multiplyByScalar :: Eq a => Polynomial a -> a -> Polynomial a
invert :: Polynomial a -> Maybe (Polynomial a)
subtract :: Eq a => Polynomial a -> Polynomial a -> Polynomial a
quotientRemainder :: Eq a => Polynomial a -> Polynomial a -> Maybe (Polynomial a, Polynomial a)
divide :: Eq a => Polynomial a -> Polynomial a -> Maybe (Polynomial a)
ring :: Eq a => Ring a -> Ring (Polynomial a)
instance (GHC.Classes.Eq a, GHC.Show.Show a) => GHC.Show.Show (Arithmetic.Polynomial.Polynomial a)


module Arithmetic.Montgomery
data Parameters
Parameters :: Natural -> Natural -> Natural -> Natural -> Natural -> Natural -> Natural -> Parameters
[nParameters] :: Parameters -> Natural
[wParameters] :: Parameters -> Natural
[sParameters] :: Parameters -> Natural
[kParameters] :: Parameters -> Natural
[rParameters] :: Parameters -> Natural
[r2Parameters] :: Parameters -> Natural
[zParameters] :: Parameters -> Natural
data Montgomery
Montgomery :: Parameters -> Natural -> Montgomery
[pMontgomery] :: Montgomery -> Parameters
[nMontgomery] :: Montgomery -> Natural
align :: Natural -> Natural -> Natural
customParameters :: Natural -> Natural -> Parameters
alignedParameters :: Natural -> Natural -> Parameters
standardParameters :: Natural -> Parameters
normalize :: Parameters -> Natural -> Montgomery
normalize1 :: Parameters -> Natural -> Montgomery
reduce :: Parameters -> Natural -> Natural
toNatural :: Montgomery -> Natural
fromNatural :: Parameters -> Natural -> Montgomery
zero :: Parameters -> Montgomery
one :: Parameters -> Montgomery
two :: Parameters -> Montgomery
add :: Montgomery -> Montgomery -> Montgomery
double :: Montgomery -> Montgomery
negate :: Montgomery -> Montgomery
subtract :: Montgomery -> Montgomery -> Montgomery
multiply :: Montgomery -> Montgomery -> Montgomery
square :: Montgomery -> Montgomery
exp :: Montgomery -> Natural -> Montgomery
exp2 :: Montgomery -> Natural -> Montgomery
modexp :: Natural -> Natural -> Natural -> Natural
modexp2 :: Natural -> Natural -> Natural -> Natural
instance GHC.Show.Show Arithmetic.Montgomery.Montgomery
instance GHC.Show.Show Arithmetic.Montgomery.Parameters


module Arithmetic.Modular
normalize :: Natural -> Natural -> Natural
add :: Natural -> Natural -> Natural -> Natural
negate :: Natural -> Natural -> Natural
multiply :: Natural -> Natural -> Natural -> Natural
divide :: Natural -> Natural -> Natural -> Maybe Natural
ring :: Natural -> Ring Natural
double :: Natural -> Natural -> Natural
subtract :: Natural -> Natural -> Natural -> Natural
square :: Natural -> Natural -> Natural
exp :: Natural -> Natural -> Natural -> Natural
exp2 :: Natural -> Natural -> Natural -> Natural
invert :: Natural -> Natural -> Maybe Natural
divides :: Natural -> Natural -> Natural -> Bool


module Arithmetic.Quadratic
rootFloor :: Natural -> Natural
rootCeiling :: Natural -> Natural
destSquare :: Natural -> Maybe Natural
isSquare :: Natural -> Bool
rootContinuedFraction :: Natural -> ContinuedFraction
rootContinuedFractionPeriodic :: Natural -> [Natural]
rootContinuedFractionPeriodicTail :: Natural -> Natural -> [Natural]
data Residue
Residue :: Residue
NonResidue :: Residue
Zero :: Residue
jacobiSymbol :: Natural -> Natural -> Residue
isResidue :: Natural -> Natural -> Bool
isNonResidue :: Natural -> Natural -> Bool
nextResidue :: Natural -> Natural -> Natural
nextNonResidue :: Natural -> Natural -> Natural
rootModuloPrime3Mod4 :: Natural -> Natural -> Natural
rootModuloPrime5Mod8 :: Natural -> Natural -> Natural
rootModuloPrime :: Natural -> Natural -> Natural
instance GHC.Show.Show Arithmetic.Quadratic.Residue
instance GHC.Classes.Ord Arithmetic.Quadratic.Residue
instance GHC.Classes.Eq Arithmetic.Quadratic.Residue


module Arithmetic.Pell
chakravala :: Natural -> [(Natural, Natural, Natural)]
solutions :: Natural -> [(Natural, Natural)]
solution :: Natural -> (Natural, Natural)


module Arithmetic.Utility.Heap
data Heap a
size :: Heap a -> Int
isEmpty :: Heap a -> Bool
empty :: (a -> a -> Bool) -> Heap a
add :: a -> Heap a -> Heap a
remove :: Heap a -> Maybe (a, Heap a)
toList :: Heap a -> [a]
instance GHC.Show.Show a => GHC.Show.Show (Arithmetic.Utility.Heap.Node a)
instance GHC.Show.Show a => GHC.Show.Show (Arithmetic.Utility.Heap.Heap a)


module Arithmetic.Prime.Sieve
newtype Sieve
Sieve :: Heap (Natural, Natural) -> Sieve
[unSieve] :: Sieve -> Heap (Natural, Natural)
initial :: Sieve
add :: Natural -> Sieve -> (Natural, Sieve)
bump :: Sieve -> (Natural, Sieve)
advance :: Natural -> Natural -> Sieve -> [Natural]
instance GHC.Show.Show Arithmetic.Prime.Sieve.Sieve


module Arithmetic.Prime
primes :: [Natural]
millerRabinWitness :: Natural -> Natural -> Bool
millerRabin :: Natural -> Natural -> Random -> Bool
isPrime :: Natural -> Random -> Bool
previousPrime :: Natural -> Random -> Natural
nextPrime :: Natural -> Random -> Natural
nextPrime3Mod4 :: Natural -> Random -> Natural
nextPrime5Mod8 :: Natural -> Random -> Natural
randomPrime :: Natural -> Random -> Natural
randomPrime3Mod4 :: Natural -> Random -> Natural
randomPrime5Mod8 :: Natural -> Random -> Natural


module Arithmetic.Prime.Factor
newtype Factor
Factor :: Map Natural Natural -> Factor
[unFactor] :: Factor -> Map Natural Natural
primePowers :: Factor -> [(Natural, Natural)]
one :: Factor
isOne :: Factor -> Bool
primePower :: Natural -> Natural -> Factor
destPrimePower :: Factor -> Maybe (Natural, Natural)
isPrimePower :: Factor -> Bool
prime :: Natural -> Factor
destPrime :: Factor -> Maybe Natural
isPrime :: Factor -> Bool
destRSA :: Factor -> Maybe (Natural, Natural)
isRSA :: Factor -> Bool
multiply :: Factor -> Factor -> Factor
exp :: Factor -> Natural -> Factor
root :: Natural -> Factor -> (Factor, Factor)
destRoot :: Natural -> Factor -> Maybe Factor
isRoot :: Natural -> Factor -> Bool
gcd :: Factor -> Factor -> Factor
trialDivision :: [Natural] -> Natural -> (Factor, Natural)
destSmooth :: [Natural] -> Natural -> Maybe Factor
isSmooth :: [Natural] -> Natural -> Bool
nextSmooth :: [Natural] -> Natural -> Factor
multiplicative :: (Natural -> Natural -> a) -> (a -> a -> a) -> a -> Factor -> a
toNatural :: Factor -> Natural
totient :: Factor -> Natural
factorPower :: Natural -> Natural -> Maybe (Natural, Natural)
factor :: Natural -> (Natural -> Random -> Maybe Natural) -> Natural -> Random -> Maybe Factor
randomRSA :: Natural -> Random -> Factor
instance GHC.Show.Show Arithmetic.Prime.Factor.Factor


module Arithmetic.Williams
sequence :: a -> a -> (a -> a -> a) -> (a -> a -> a) -> a -> [a]
nthExp :: a -> (a -> a -> a) -> (a -> a -> a) -> a -> Natural -> Natural -> a
nth :: a -> (a -> a -> a) -> (a -> a -> a) -> a -> Natural -> a
base :: Natural -> Natural -> Random -> Either Natural [Natural]
method :: Natural -> [Natural] -> [Natural] -> Maybe Natural
factor :: Natural -> Maybe Natural -> Natural -> Random -> Maybe Natural