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


-- | Arithmetic in finite fields
--   
--   Implementation of arithmetic in finite fields (prime fields and fields
--   of prime power order). Finite fields are ubiquitous in algebraic
--   geometry, number theory and cryptography. For now the focus is on
--   relatively small fields, but algorithms for big fields (required in
--   cryptography) may be added later.
@package finite-fields
@version 0.1


-- | Type class interface to different implementations of finite fields
module Math.FiniteField.Class
class (Eq f, Ord f, Show f, Num f, Fractional f, Show (Witness f)) => Field f where {
    
    -- | witness for the existence of the field (this is an injective type
    --   family!)
    type family Witness f = r | r -> f;
}

-- | the prime characteristic
characteristic :: Field f => Witness f -> Integer

-- | dimension over the prime field (the exponent <tt>m</tt> in
--   <tt>q=p^m</tt>)
dimension :: Field f => Witness f -> Integer

-- | the size (or order) of the field
fieldSize :: Field f => Witness f -> Integer

-- | The additive identity of the field
zero :: Field f => Witness f -> f

-- | The multiplicative identity of the field
one :: Field f => Witness f -> f

-- | check for equality with the additive identity
isZero :: Field f => f -> Bool

-- | check for equality with the multiplicative identity
isOne :: Field f => f -> Bool

-- | an element of the prime field
embed :: Field f => Witness f -> Integer -> f
embedSmall :: Field f => Witness f -> Int -> f

-- | a uniformly random field element
randomFieldElem :: (Field f, RandomGen gen) => Witness f -> gen -> (f, gen)

-- | a random invertible element
randomInvertible :: (Field f, RandomGen gen) => Witness f -> gen -> (f, gen)

-- | a primitive generator
primGen :: Field f => Witness f -> f

-- | extract t he witness from a field element
witnessOf :: Field f => f -> Witness f

-- | exponentiation
power :: Field f => f -> Integer -> f
powerSmall :: Field f => f -> Int -> f

-- | list of field elements (of course it's only useful for very small
--   fields)
enumerate :: Field f => Witness f -> [f]
data SomeField
SomeField :: Witness f -> SomeField

-- | The multiplicate inverse (synonym for <a>recip</a>)
inverse :: Field f => f -> f

-- | Enumerate the elements of the prime field only
enumPrimeField :: forall f. Field f => Witness f -> [f]

-- | The nonzero elements in cyclic order, starting from the primitive
--   generator (of course this is only useful for very small fields)
multGroup :: Field f => Witness f -> [f]

-- | Computes a table of discrete logarithms with respect to the primitive
--   generator. Note: zero is not present in the resulting map.
discreteLogTable :: forall f. Field f => Witness f -> Map f Int

-- | Generic exponentiation
powerDefault :: forall f. Field f => f -> Integer -> f
instance GHC.Show.Show Math.FiniteField.Class.SomeField


-- | Signs
module Math.FiniteField.Sign
data Sign
Plus :: Sign
Minus :: Sign
isPlus :: Sign -> Bool
isMinus :: Sign -> Bool

-- | <tt>+1</tt> or <tt>-1</tt>
signValue :: Num a => Sign -> a

-- | Negate the second argument if the first is <a>Minus</a>
signed :: Num a => Sign -> a -> a

-- | <a>Plus</a> if even, <a>Minus</a> if odd
paritySign :: Integral a => a -> Sign

-- | <pre>
--   (-1)^k
--   </pre>
paritySignValue :: Integral a => a -> Integer

-- | Negate the second argument if the first is odd
negateIfOdd :: (Integral a, Num b) => a -> b -> b
oppositeSign :: Sign -> Sign
mulSign :: Sign -> Sign -> Sign
productOfSigns :: [Sign] -> Sign
instance GHC.Read.Read Math.FiniteField.Sign.Sign
instance GHC.Show.Show Math.FiniteField.Sign.Sign
instance GHC.Classes.Eq Math.FiniteField.Sign.Sign
instance GHC.Base.Semigroup Math.FiniteField.Sign.Sign
instance GHC.Base.Monoid Math.FiniteField.Sign.Sign


-- | Prime numbers and related number theoretical stuff.
module Math.FiniteField.Primes

-- | Largest integer <tt>k</tt> such that <tt>2^k</tt> is smaller or equal
--   to <tt>n</tt>
integerLog2 :: Integer -> Integer

-- | Smallest integer <tt>k</tt> such that <tt>2^k</tt> is larger or equal
--   to <tt>n</tt>
ceilingLog2 :: Integer -> Integer
isSquare :: Integer -> Bool

-- | Integer square root (largest integer whose square is smaller or equal
--   to the input) using Newton's method, with a faster (for large numbers)
--   inital guess based on bit shifts.
integerSquareRoot :: Integer -> Integer

-- | Smallest integer whose square is larger or equal to the input
ceilingSquareRoot :: Integer -> Integer

-- | We also return the excess residue; that is
--   
--   <pre>
--   (a,r) = integerSquareRoot' n
--   </pre>
--   
--   means that
--   
--   <pre>
--   a*a + r = n
--   a*a &lt;= n &lt; (a+1)*(a+1)
--   </pre>
integerSquareRoot' :: Integer -> (Integer, Integer)

-- | Newton's method without an initial guess. For very small numbers
--   (&lt;10^10) it is somewhat faster than the above version.
integerSquareRootNewton' :: Integer -> (Integer, Integer)

-- | <pre>
--   d <a>divides</a> n
--   </pre>
divides :: Integer -> Integer -> Bool

-- | Divisors of <tt>n</tt> (note: the result is <i>not</i> ordered!)
divisors :: Integer -> [Integer]

-- | List of square-free divisors together with their Mobius mu value
--   (note: the result is <i>not</i> ordered!)
squareFreeDivisors :: Integer -> [(Integer, Sign)]

-- | List of square-free divisors (note: the result is <i>not</i> ordered!)
squareFreeDivisors_ :: Integer -> [Integer]

-- | Sum ofthe of the divisors
divisorSum :: Integer -> Integer

-- | Sum of <tt>k</tt>-th powers of the divisors
divisorSum' :: Int -> Integer -> Integer

-- | The Moebius mu function (naive implementation)
moebiusMu :: (Integral a, Num b) => a -> b

-- | Euler's totient function
eulerTotient :: Integer -> Integer

-- | The Liouville lambda function (naive implementation)
liouvilleLambda :: (Integral a, Num b) => a -> b

-- | Infinite list of primes, using the TMWE algorithm.
primes :: [Integer]

-- | A relatively simple but still quite fast implementation of list of
--   primes. By Will Ness
--   <a>http://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html</a>
primesSimple :: [Integer]

-- | List of primes, using tree merge with wheel. Code by Will Ness.
primesTMWE :: [Integer]
factorize :: Integer -> [(Integer, Int)]
factorizeNaive :: Integer -> [(Integer, Int)]
productOfFactors :: [(Integer, Int)] -> Integer

-- | The naive trial division algorithm.
integerFactorsTrialDivision :: Integer -> [Integer]

-- | Groups integer factors. Example: from [2,2,2,3,3,5] we produce
--   [(2,3),(3,2),(5,1)]
groupIntegerFactors :: [Integer] -> [(Integer, Int)]

-- | Efficient powers modulo m.
--   
--   <pre>
--   powerMod a k m == (a^k) `mod` m
--   </pre>
powerMod :: Integer -> Integer -> Integer -> Integer

-- | Prime testing using trial division
isPrimeTrialDivision :: Integer -> Bool

-- | Miller-Rabin Primality Test (taken from Haskell wiki). We test the
--   primality of the first argument <tt>n</tt> by using the second
--   argument <tt>a</tt> as a candidate witness. If it returs
--   <tt>False</tt>, then <tt>n</tt> is composite. If it returns
--   <tt>True</tt>, then <tt>n</tt> is either prime or composite.
--   
--   A random choice between <tt>2</tt> and <tt>(n-2)</tt> is a good choice
--   for <tt>a</tt>.
millerRabinPrimalityTest :: Integer -> Integer -> Bool

-- | For very small numbers, we use trial division, for larger numbers, we
--   apply the Miller-Rabin primality test <tt>log4(n)</tt> times, with
--   candidate witnesses derived deterministically from <tt>n</tt> using a
--   pseudo-random sequence (which <i>should be</i> based on a
--   cryptographic hash function, but isn't, yet).
--   
--   Thus the candidate witnesses should behave essentially like random,
--   but the resulting function is still a deterministic, pure function.
--   
--   TODO: implement the hash sequence, at the moment we use <a>Random</a>
--   instead...
isProbablyPrime :: Integer -> Bool

-- | A more exhaustive version of <a>isProbablyPrime</a>, this one tests
--   candidate witnesses both the first log4(n) prime numbers and then
--   log4(n) pseudo-random numbers
isVeryProbablyPrime :: Integer -> Bool


-- | Type level naturals, singletons, prime witnesses and stuff.
--   
--   This would be much simpler in a dependently typed language; alas, we
--   are in Haskell, so for now we have to feel the pain.
--   
--   How to use this, the over-complicated way:
--   
--   <ul>
--   <li>create a <a>SomeSNat</a> from an integer using the function
--   <a>someSNat</a></li>
--   <li>pattern match on it with a <tt>case</tt> expression. Within the
--   matched scope, the type parameter is "instantiated". So all your
--   program will be "inside" this case branch (of course you can call out
--   to functions)</li>
--   <li>create witnesses for this being prime and/or being small using the
--   functions <a>isPrime</a> and <a>fits31Bits</a></li>
--   <li>if you want small primes, create a "small prime witness" using
--   <a>mkSmallPrime</a></li>
--   <li>now you are ready to use the resulting witness (of type
--   <tt>IsPrime n</tt> or <tt>IsSmallPrime n</tt>) to create finite
--   fields.</li>
--   </ul>
--   
--   Or you can just the functions provided with each field implementation
--   to create the fields directly (in form of existantials, ie. sigma
--   types, so you still have to do the <tt>case _ of</tt> thing).
module Math.FiniteField.TypeLevel

-- | Nat-singletons
data SNat (n :: Nat)
fromSNat :: SNat n -> Integer
proxyOfSNat :: SNat n -> Proxy n
proxyToSNat :: KnownNat n => Proxy n -> SNat n

-- | You are responsible here!
--   
--   (this is exported primarily because the testsuite is much simpler
--   using this...)
unsafeSNat :: Integer -> SNat n

-- | Word-sized nat-singletons
data SNat64 (n :: Nat)
fromSNat64 :: SNat64 n -> Word64
proxyOfSNat64 :: SNat64 n -> Proxy n
proxyToSNat64 :: KnownNat n => Proxy n -> SNat64 n

-- | You are responsible here!
--   
--   (this is exported primarily because the testsuite is much simpler
--   using this...)
unsafeSNat64 :: Word64 -> SNat64 n
data SomeSNat
SomeSNat :: SNat n -> SomeSNat
someSNat :: Integer -> SomeSNat
data SomeSNat64
SomeSNat64 :: SNat64 n -> SomeSNat64
someSNat64 :: Int64 -> SomeSNat64
someSNat64_ :: Word64 -> SomeSNat64
data Fits31Bits (n :: Nat)
from31Bit :: Fits31Bits n -> Word64
from31BitSigned :: Fits31Bits n -> Int64
from31Bit' :: Fits31Bits n -> SNat64 n

-- | Creating a witness for a number being small (less than <tt>2^31</tt>)
fits31Bits :: SNat64 n -> Maybe (Fits31Bits n)

-- | Prime witness
data IsPrime (n :: Nat)
fromPrime :: IsPrime n -> Integer
fromPrime' :: IsPrime n -> SNat n

-- | Prime testing.
--   
--   Note: this uses trial division at the moment, so it's only good for
--   small numbers for now
isPrime :: SNat n -> Maybe (IsPrime n)

-- | Escape hatch
believeMeItsPrime :: SNat n -> IsPrime n
data IsSmallPrime (n :: Nat)
fromSmallPrime :: IsSmallPrime n -> Word64
fromSmallPrimeSigned :: IsSmallPrime n -> Int64
fromSmallPrimeInteger :: IsSmallPrime n -> Integer
fromSmallPrime' :: IsSmallPrime n -> SNat64 n

-- | Prime testing.
--   
--   Note: this uses trial division at the moment, so it's only good for
--   small numbers for now
isSmallPrime :: SNat64 n -> Maybe (IsSmallPrime n)

-- | Escape hatch
believeMeItsASmallPrime :: SNat64 n -> IsSmallPrime n
smallPrimeIsPrime :: IsSmallPrime n -> IsPrime n
smallPrimeIsSmall :: IsSmallPrime n -> Fits31Bits n

-- | Creating small primes
mkSmallPrime :: IsPrime p -> Fits31Bits p -> IsSmallPrime p
proxyOf :: a -> Proxy a
proxyOf1 :: f a -> Proxy a
checkSomeSNat :: SomeSNat -> String
checkSomeSNat64 :: SomeSNat64 -> String
instance GHC.Show.Show (Math.FiniteField.TypeLevel.IsPrime n)
instance GHC.Show.Show (Math.FiniteField.TypeLevel.Fits31Bits n)
instance GHC.Show.Show (Math.FiniteField.TypeLevel.IsSmallPrime n)


-- | Small prime fields, up to <tt>p &lt; 2^31</tt> (using <tt>Word64</tt>
--   under the hood).
--   
--   This should be faster than the generic implementation which uses
--   <tt>Integer</tt> under the hood.
--   
--   NB: Because the multiplication of two 32 bit integers needs 64 bits,
--   the limit is <tt>2^32</tt> and not <tt>2^64</tt>. And because I'm lazy
--   right now to check if everything works properly unsigned, the actual
--   limit is <tt>2^31</tt> instead :)
module Math.FiniteField.PrimeField.Small

-- | A witness for the existence of the prime field <tt>F_p</tt>
newtype WitnessFp (p :: Nat)
WitnessFp :: IsSmallPrime p -> WitnessFp (p :: Nat)
[fromWitnessFp] :: WitnessFp (p :: Nat) -> IsSmallPrime p
data SomeWitnessFp
SomeWitnessFp :: WitnessFp p -> SomeWitnessFp

-- | Note: currently this checks the primality of the input using trial
--   division, so it's only practical for (very) small primes...
--   
--   But you can use <a>unsafeSmallPrimeField</a> to cheat.
mkSmallPrimeField :: Int -> Maybe SomeWitnessFp

-- | You are responsible for guaranteeing that the input is a prime.
unsafeSmallPrimeField :: Int -> SomeWitnessFp

-- | An element of the prime field <tt>F_p</tt>
data Fp (p :: Nat)
primRoot :: IsSmallPrime p -> Fp p
instance GHC.Show.Show (Math.FiniteField.PrimeField.Small.WitnessFp p)
instance GHC.Show.Show Math.FiniteField.PrimeField.Small.SomeWitnessFp
instance GHC.Classes.Eq (Math.FiniteField.PrimeField.Small.Fp p)
instance GHC.Classes.Ord (Math.FiniteField.PrimeField.Small.Fp p)
instance GHC.Show.Show (Math.FiniteField.PrimeField.Small.Fp p)
instance GHC.Num.Num (Math.FiniteField.PrimeField.Small.Fp p)
instance GHC.Real.Fractional (Math.FiniteField.PrimeField.Small.Fp p)
instance Math.FiniteField.Class.Field (Math.FiniteField.PrimeField.Small.Fp p)


-- | Arbitrary prime fields, naive implementation
module Math.FiniteField.PrimeField.Generic

-- | A witness for the existence of the prime field <tt>F_p</tt>
newtype WitnessFp (p :: Nat)
WitnessFp :: IsPrime p -> WitnessFp (p :: Nat)
[fromWitnessFp] :: WitnessFp (p :: Nat) -> IsPrime p
data SomeWitnessFp
SomeWitnessFp :: WitnessFp p -> SomeWitnessFp

-- | Note: currently this checks the primality of the input using trial
--   division, so it's not really practical...
--   
--   But you can use <a>unsafePrimeField</a> to cheat.
mkPrimeField :: Integer -> Maybe SomeWitnessFp

-- | You are responsible for guaranteeing that the input is a prime.
unsafePrimeField :: Integer -> SomeWitnessFp

-- | An element of the prime field <tt>F_p</tt>
data Fp (p :: Nat)
instance GHC.Show.Show (Math.FiniteField.PrimeField.Generic.WitnessFp p)
instance GHC.Show.Show Math.FiniteField.PrimeField.Generic.SomeWitnessFp
instance GHC.Classes.Eq (Math.FiniteField.PrimeField.Generic.Fp p)
instance GHC.Classes.Ord (Math.FiniteField.PrimeField.Generic.Fp p)
instance GHC.Show.Show (Math.FiniteField.PrimeField.Generic.Fp p)
instance GHC.Num.Num (Math.FiniteField.PrimeField.Generic.Fp p)
instance GHC.Real.Fractional (Math.FiniteField.PrimeField.Generic.Fp p)
instance Math.FiniteField.Class.Field (Math.FiniteField.PrimeField.Generic.Fp p)


-- | Table of Conway polynomials
--   
--   The data is from
--   <a>http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html</a>
module Math.FiniteField.Conway
data HasConwayPoly (p :: Nat) (m :: Nat)
data SomeConwayPoly
SomeConwayPoly :: HasConwayPoly p m -> SomeConwayPoly

-- | The prime characteristic <tt>p</tt>
conwayPrime :: HasConwayPoly p m -> IsSmallPrime p

-- | The dimension <tt>m</tt> of <tt>F_q</tt> over <tt>F_p</tt>
conwayDim :: HasConwayPoly p m -> Int

-- | The pair <tt>(p,m)</tt>
conwayParams :: HasConwayPoly p m -> (Int, Int)
conwayParams' :: HasConwayPoly p m -> (SNat64 p, SNat64 m)
conwayCoefficients :: HasConwayPoly p m -> [Word64]

-- | Usage: <tt>lookupSomeConwayPoly p m</tt> for <tt>q = p^m</tt>
lookupSomeConwayPoly :: Int -> Int -> Maybe SomeConwayPoly

-- | Usage: <tt>lookupConwayPoly sp sm</tt> for <tt>q = p^m</tt>
lookupConwayPoly :: SNat64 p -> SNat64 m -> Maybe (HasConwayPoly p m)
unsafeLookupConwayPoly :: SNat64 p -> SNat64 m -> HasConwayPoly p m

-- | We have some Conway polynomials for <tt>m=1</tt> too; the roots of
--   these linear polynomials are primitive roots in <tt>F_p</tt>
lookupConwayPrimRoot :: Int -> Maybe Int
instance GHC.Show.Show Math.FiniteField.Conway.SomeConwayPoly
instance GHC.Show.Show (Math.FiniteField.Conway.Internal.HasConwayPoly p m)


-- | Small Galois fields via a precomputed table of Conway polynomials.
--   
--   This covers:
--   
--   <ul>
--   <li>all fields with order &lt;= 2^30</li>
--   <li>all fields with characteristic &lt; 2^16 and order &lt; 2^64
--   (?)</li>
--   <li>higher powers for very small prime characteristic</li>
--   <li>some more</li>
--   </ul>
--   
--   To look up Conway polynomials, see the module
--   <a>Math.FiniteField.Conway</a>.
module Math.FiniteField.GaloisField.Small

-- | We need either a Conway polynomial, or in the <tt>m=1</tt> case, a
--   proof that <tt>p</tt> is prime
data WitnessGF (p :: Nat) (m :: Nat)
[WitnessFp] :: IsSmallPrime p -> WitnessGF p 1
[WitnessFq] :: HasConwayPoly p m -> WitnessGF p m
data SomeWitnessGF
SomeWitnessGF :: WitnessGF p m -> SomeWitnessGF

-- | Usage:
--   
--   <pre>
--   mkGaloisField p m
--   </pre>
--   
--   to construct the field with <tt>q = p^m</tt> elements
--   
--   Implementation note: For <tt>m=1</tt> we may do a primality test,
--   which is very slow at the moment. You can use <a>unsafeGaloisField</a>
--   below to avoid this.
mkGaloisField :: Int -> Int -> Maybe SomeWitnessGF

-- | In the case of <tt>m=1</tt> you are responsible for guaranteeing that
--   <tt>p</tt> is a prime (for <tt>m&gt;1</tt> we have to look up a Conway
--   polynomial anyway).
unsafeGaloisField :: Int -> Int -> SomeWitnessGF

-- | An element of the Galois field of order <tt>q = p^m</tt>
data GF (p :: Nat) (m :: Nat)
instance GHC.Show.Show (Math.FiniteField.GaloisField.Small.WitnessGF p m)
instance GHC.Show.Show Math.FiniteField.GaloisField.Small.SomeWitnessGF
instance GHC.Classes.Eq (Math.FiniteField.GaloisField.Small.GF p m)
instance GHC.Classes.Ord (Math.FiniteField.GaloisField.Small.GF p m)
instance GHC.Show.Show (Math.FiniteField.GaloisField.Small.GF p m)
instance GHC.Num.Num (Math.FiniteField.GaloisField.Small.GF p m)
instance GHC.Real.Fractional (Math.FiniteField.GaloisField.Small.GF p m)
instance Math.FiniteField.Class.Field (Math.FiniteField.GaloisField.Small.GF p m)


-- | Small Galois fields via precomputed tables of Zech's logarithms.
--   
--   <a>https://en.wikipedia.org/wiki/Zech%27s_logarithm</a>
--   
--   When "creating" a field, we precompute the Zech logarithm table. After
--   that, computations should be fast.
--   
--   This is practical up to fields of size <tt>10^5 -- 10^6</tt>
--   
--   TODO: also export the tables to C, and write C implementation of of
--   the field operations.
module Math.FiniteField.GaloisField.Zech
data ZechTable
makeZechTable :: forall p m. WitnessGF p m -> ZechTable
newtype WitnessZech (p :: Nat) (m :: Nat)
WitnessZech :: ZechTable -> WitnessZech (p :: Nat) (m :: Nat)
[fromWitnessZech] :: WitnessZech (p :: Nat) (m :: Nat) -> ZechTable
data SomeWitnessZech
SomeWitnessZech :: WitnessZech p m -> SomeWitnessZech
mkZechField :: Int -> Int -> Maybe SomeWitnessZech
unsafeZechField :: Int -> Int -> SomeWitnessZech
data Zech (p :: Nat) (m :: Nat)
instance GHC.Show.Show Math.FiniteField.GaloisField.Zech.ZechTable
instance GHC.Show.Show (Math.FiniteField.GaloisField.Zech.WitnessZech p m)
instance GHC.Show.Show Math.FiniteField.GaloisField.Zech.SomeWitnessZech
instance GHC.Classes.Eq (Math.FiniteField.GaloisField.Zech.Zech p m)
instance GHC.Classes.Ord (Math.FiniteField.GaloisField.Zech.Zech p m)
instance GHC.Show.Show (Math.FiniteField.GaloisField.Zech.Zech p m)
instance GHC.Num.Num (Math.FiniteField.GaloisField.Zech.Zech p m)
instance GHC.Real.Fractional (Math.FiniteField.GaloisField.Zech.Zech p m)
instance Math.FiniteField.Class.Field (Math.FiniteField.GaloisField.Zech.Zech p m)