    {-# LANGUAGE DataKinds, DeriveDataTypeable, DeriveGeneric, GeneralizedNewtypeDeriving, TemplateHaskell #-}
    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Crypto.SecretSharing.Internal
    -- Copyright   :  Peter Robinson 2014
    -- License     :  LGPL
    --
    -- Stability   :  experimental
    -- Portability :  portable
    --
    -----------------------------------------------------------------------------

    module Crypto.SecretSharing.Internal
    where

    import Data.ByteString.Lazy( ByteString )
    import qualified Data.ByteString.Lazy as BL
    import qualified Data.ByteString.Lazy.Char8 as BLC
    import qualified Data.List as L
    import Data.Char
    import Data.Vector( Vector )
    import qualified Data.Vector as V
    import Data.Typeable
    import Control.Exception
    import Control.Monad
    import Data.Binary( Binary )
    import GHC.Generics
    import Data.FiniteField.PrimeField as PF
    import Data.FiniteField.Base(FiniteField,order)
    import System.Random.Dice

    -- | Evaluate a Lagrange interpolation polynomial
    -- passing through the specified set of points.
    polyInterp :: Fractional a => [(a, a)] -> a -> a
    polyInterp :: forall a. Fractional a => [(a, a)] -> a -> a
    polyInterp [(a, a)]
    xys a
    x = [a] -> a
    forall a. Num a => [a] -> a
    forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
    sum ([a] -> a) -> [a] -> a
    forall a b. (a -> b) -> a -> b
    $ (([(a, a)], (a, a), [(a, a)]) -> a)
    -> [([(a, a)], (a, a), [(a, a)])] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map ([(a, a)], (a, a), [(a, a)]) -> a
    forall {b}. ([(a, b)], (a, a), [(a, b)]) -> a
    evalBasisPoly ([([(a, a)], (a, a), [(a, a)])] -> [a])
    -> [([(a, a)], (a, a), [(a, a)])] -> [a]
    forall a b. (a -> b) -> a -> b
    $ [(a, a)] -> [([(a, a)], (a, a), [(a, a)])]
    forall a. [a] -> [([a], a, [a])]
    slidingFocus [(a, a)]
    xys
      where
        evalBasisPoly :: ([(a, b)], (a, a), [(a, b)]) -> a
    evalBasisPoly ([(a, b)]
    left, (a
    xj, a
    yj), [(a, b)]
    right) =
          a
    yj a -> a -> a
    forall a. Num a => a -> a -> a
    * [a] -> a
    forall a. Num a => [a] -> a
    forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
    product (((a, b) -> a) -> [(a, b)] -> [a]
    forall a b. (a -> b) -> [a] -> [b]
    map (\(a
    xm, b
    _) -> (a
    x a -> a -> a
    forall a. Num a => a -> a -> a
    - a
    xm) a -> a -> a
    forall a. Fractional a => a -> a -> a
    / (a
    xj a -> a -> a
    forall a. Num a => a -> a -> a
    - a
    xm)) ([(a, b)]
    left [(a, b)] -> [(a, b)] -> [(a, b)]
    forall a. [a] -> [a] -> [a]
    ++ [(a, b)]
    right))

    -- [1,2,3] -> [([], 1, [2,3]), ([1], 2, [3]), ([2,1], 3, [])]
    slidingFocus :: [a] -> [([a], a, [a])]
    slidingFocus :: forall a. [a] -> [([a], a, [a])]
    slidingFocus [] = []
    slidingFocus (a
    x : [a]
    xs) = [a] -> a -> [a] -> [([a], a, [a])]
    forall {t}. [t] -> t -> [t] -> [([t], t, [t])]
    go [] a
    x [a]
    xs
      where
        go :: [t] -> t -> [t] -> [([t], t, [t])]
    go [t]
    left t
    focus [t]
    right = ([t]
    left, t
    focus, [t]
    right) ([t], t, [t]) -> [([t], t, [t])] -> [([t], t, [t])]
    forall a. a -> [a] -> [a]
    : case [t]
    right of
          [] -> []
          t
    focus' : [t]
    right' -> [t] -> t -> [t] -> [([t], t, [t])]
    go (t
    focus t -> [t] -> [t]
    forall a. a -> [a] -> [a]
    : [t]
    left) t
    focus' [t]
    right'

    -- | A share of an encoded byte.
    data ByteShare = ByteShare
      { ByteShare -> Int
    shareId :: !Int                  -- ^ the index of this share
      , ByteShare -> Int
    reconstructionThreshold :: !Int  -- ^ number of shares required for
                                         -- reconstruction
      , ByteShare -> Int
    shareValue :: !Int        -- ^ the value of p(shareId) where p(x) is the
                                  --   generated (secret) polynomial
      }
      deriving(Typeable,ByteShare -> ByteShare -> Bool
    (ByteShare -> ByteShare -> Bool)
    -> (ByteShare -> ByteShare -> Bool) -> Eq ByteShare
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: ByteShare -> ByteShare -> Bool
    == :: ByteShare -> ByteShare -> Bool
    $c/= :: ByteShare -> ByteShare -> Bool
    /= :: ByteShare -> ByteShare -> Bool
    Eq,(forall x. ByteShare -> Rep ByteShare x)
    -> (forall x. Rep ByteShare x -> ByteShare) -> Generic ByteShare
    forall x. Rep ByteShare x -> ByteShare
    forall x. ByteShare -> Rep ByteShare x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    $cfrom :: forall x. ByteShare -> Rep ByteShare x
    from :: forall x. ByteShare -> Rep ByteShare x
    $cto :: forall x. Rep ByteShare x -> ByteShare
    to :: forall x. Rep ByteShare x -> ByteShare
    Generic)

    instance Show ByteShare where
      show :: ByteShare -> String
    show = Int -> String
    forall a. Show a => a -> String
    show (Int -> String) -> (ByteShare -> Int) -> ByteShare -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ByteShare -> Int
    shareValue

    -- | A share of the encoded secret.
    data Share = Share
      { Share -> [ByteShare]
    theShare :: ![ByteShare] }
      deriving(Typeable,Share -> Share -> Bool
    (Share -> Share -> Bool) -> (Share -> Share -> Bool) -> Eq Share
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Share -> Share -> Bool
    == :: Share -> Share -> Bool
    $c/= :: Share -> Share -> Bool
    /= :: Share -> Share -> Bool
    Eq,(forall x. Share -> Rep Share x)
    -> (forall x. Rep Share x -> Share) -> Generic Share
    forall x. Rep Share x -> Share
    forall x. Share -> Rep Share x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    $cfrom :: forall x. Share -> Rep Share x
    from :: forall x. Share -> Rep Share x
    $cto :: forall x. Rep Share x -> Share
    to :: forall x. Rep Share x -> Share
    Generic)

    instance Show Share where
      show :: Share -> String
    show Share
    s = (Int, ByteString) -> String
    forall a. Show a => a -> String
    show (ByteShare -> Int
    shareId (ByteShare -> Int) -> ByteShare -> Int
    forall a b. (a -> b) -> a -> b
    $ [ByteShare] -> ByteShare
    forall a. HasCallStack => [a] -> a
    head ([ByteShare] -> ByteShare) -> [ByteShare] -> ByteShare
    forall a b. (a -> b) -> a -> b
    $ Share -> [ByteShare]
    theShare Share
    s,String -> ByteString
    BLC.pack (String -> ByteString) -> String -> ByteString
    forall a b. (a -> b) -> a -> b
    $ (ByteShare -> Char) -> [ByteShare] -> String
    forall a b. (a -> b) -> [a] -> [b]
    map (Int -> Char
    chr (Int -> Char) -> (ByteShare -> Int) -> ByteShare -> Char
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ByteShare -> Int
    shareValue) ([ByteShare] -> String) -> [ByteShare] -> String
    forall a b. (a -> b) -> a -> b
    $ Share -> [ByteShare]
    theShare Share
    s)

    instance Binary ByteShare
    instance Binary Share

    -- | Encodes a 'ByteString' as a list of n shares, m of which are required for
    -- reconstruction.
    -- Lives in the 'IO' to access a random source.
    encode :: Int         -- ^ m
           -> Int         -- ^ n
           -> ByteString  -- ^ the secret that we want to share
           -> IO [Share] -- a list of n-shares (per byte)
    encode :: Int -> Int -> ByteString -> IO [Share]
    encode Int
    m Int
    n ByteString
    bstr
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    prime Bool -> Bool -> Bool
    || Int
    m Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    n = AssertionFailed -> IO [Share]
    forall a e. Exception e => e -> a
    throw (AssertionFailed -> IO [Share]) -> AssertionFailed -> IO [Share]
    forall a b. (a -> b) -> a -> b
    $ String -> AssertionFailed
    AssertionFailed (String -> AssertionFailed) -> String -> AssertionFailed
    forall a b. (a -> b) -> a -> b
    $
          String
    "encode: require n < " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ Int -> String
    forall a. Show a => a -> String
    show Int
    prime String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ String
    " and m<=n."
      | ByteString -> Bool
    BL.null ByteString
    bstr = [Share] -> IO [Share]
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
      | Bool
    otherwise = do
      let len :: Int
    len = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    max Int
    1 ((Int64 -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int64 -> Int) -> Int64 -> Int
    forall a b. (a -> b) -> a -> b
    $ ByteString -> Int64
    BL.length ByteString
    bstr) Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * (Int
    mInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1))
      [[FField]]
    coeffs <- (Int -> [FField] -> [[FField]]
    forall a. Int -> [a] -> [[a]]
    groupInto (Int
    mInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1) ([FField] -> [[FField]])
    -> ([Int] -> [FField]) -> [Int] -> [[FField]]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> FField) -> [Int] -> [FField]
    forall a b. (a -> b) -> [a] -> [b]
    map Int -> FField
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral ([Int] -> [FField]) -> ([Int] -> [Int]) -> [Int] -> [FField]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> [Int] -> [Int]
    forall a. Int -> [a] -> [a]
    take Int
    len )
                                ([Int] -> [[FField]]) -> IO [Int] -> IO [[FField]]
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    `liftM` (Int -> Int -> IO [Int]
    getDiceRolls Int
    prime Int
    len)
      let byteVecs :: [Vector ByteShare]
    byteVecs = ([FField] -> FField -> Vector ByteShare)
    -> [[FField]] -> [FField] -> [Vector ByteShare]
    forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
    zipWith (Int -> Int -> [FField] -> FField -> Vector ByteShare
    encodeByte Int
    m Int
    n) [[FField]]
    coeffs ([FField] -> [Vector ByteShare]) -> [FField] -> [Vector ByteShare]
    forall a b. (a -> b) -> a -> b
    $
                        (Word8 -> FField) -> [Word8] -> [FField]
    forall a b. (a -> b) -> [a] -> [b]
    map Word8 -> FField
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral ([Word8] -> [FField]) -> [Word8] -> [FField]
    forall a b. (a -> b) -> a -> b
    $ ByteString -> [Word8]
    BL.unpack ByteString
    bstr
      [Share] -> IO [Share]
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [ [ByteShare] -> Share
    Share ([ByteShare] -> Share) -> [ByteShare] -> Share
    forall a b. (a -> b) -> a -> b
    $ (Vector ByteShare -> ByteShare)
    -> [Vector ByteShare] -> [ByteShare]
    forall a b. (a -> b) -> [a] -> [b]
    map (Vector ByteShare -> Int -> ByteShare
    forall a. Vector a -> Int -> a
    V.! (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1)) [Vector ByteShare]
    byteVecs | Int
    i <- [Int
    1..Int
    n] ]

    -- | Reconstructs a (secret) bytestring from a list of (at least @m@) shares.
    -- Throws 'AssertionFailed' if the number of shares is too small.
    decode :: [Share]    -- ^ list of at least @m@ shares
           -> ByteString -- ^ reconstructed secret
    decode :: [Share] -> ByteString
    decode []     = [Word8] -> ByteString
    BL.pack []
    decode shares :: [Share]
    shares@((Share [ByteShare]
    s):[Share]
    _)
      | [Share] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [Share]
    shares Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < ByteShare -> Int
    reconstructionThreshold ([ByteShare] -> ByteShare
    forall a. HasCallStack => [a] -> a
    head [ByteShare]
    s) = AssertionFailed -> ByteString
    forall a e. Exception e => e -> a
    throw (AssertionFailed -> ByteString) -> AssertionFailed -> ByteString
    forall a b. (a -> b) -> a -> b
    $ String -> AssertionFailed
    AssertionFailed
          String
    "decode: not enough shares for reconstruction."
      | Bool
    otherwise =
        let origLength :: Int
    origLength = [ByteShare] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [ByteShare]
    s in
        let byteVecs :: [Vector ByteShare]
    byteVecs = (Share -> Vector ByteShare) -> [Share] -> [Vector ByteShare]
    forall a b. (a -> b) -> [a] -> [b]
    map ([ByteShare] -> Vector ByteShare
    forall a. [a] -> Vector a
    V.fromList ([ByteShare] -> Vector ByteShare)
    -> (Share -> [ByteShare]) -> Share -> Vector ByteShare
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Share -> [ByteShare]
    theShare) [Share]
    shares in
        let byteShares :: [[ByteShare]]
    byteShares = [ (Vector ByteShare -> ByteShare)
    -> [Vector ByteShare] -> [ByteShare]
    forall a b. (a -> b) -> [a] -> [b]
    map ((Vector ByteShare -> Int -> ByteShare
    forall a. Vector a -> Int -> a
    V.! (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1))) [Vector ByteShare]
    byteVecs | Int
    i <- [Int
    1..Int
    origLength] ] in
        [Word8] -> ByteString
    BL.pack ([Word8] -> ByteString)
    -> ([[ByteShare]] -> [Word8]) -> [[ByteShare]] -> ByteString
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (FField -> Word8) -> [FField] -> [Word8]
    forall a b. (a -> b) -> [a] -> [b]
    map (Integer -> Word8
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Word8) -> (FField -> Integer) -> FField -> Word8
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . PrimeField 1021 -> Integer
    forall (p :: Nat). PrimeField p -> Integer
    PF.toInteger (PrimeField 1021 -> Integer)
    -> (FField -> PrimeField 1021) -> FField -> Integer
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FField -> PrimeField 1021
    number)
                ([FField] -> [Word8])
    -> ([[ByteShare]] -> [FField]) -> [[ByteShare]] -> [Word8]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ([ByteShare] -> FField) -> [[ByteShare]] -> [FField]
    forall a b. (a -> b) -> [a] -> [b]
    map [ByteShare] -> FField
    decodeByte ([[ByteShare]] -> ByteString) -> [[ByteShare]] -> ByteString
    forall a b. (a -> b) -> a -> b
    $ [[ByteShare]]
    byteShares

    encodeByte :: Int -> Int -> Polyn -> FField -> Vector ByteShare
    encodeByte :: Int -> Int -> [FField] -> FField -> Vector ByteShare
    encodeByte Int
    m Int
    n [FField]
    coeffs FField
    secret =
      [ByteShare] -> Vector ByteShare
    forall a. [a] -> Vector a
    V.fromList[ Int -> Int -> Int -> ByteShare
    ByteShare Int
    i Int
    m (Int -> ByteShare) -> Int -> ByteShare
    forall a b. (a -> b) -> a -> b
    $ Integer -> Int
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Int) -> (FField -> Integer) -> FField -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . PrimeField 1021 -> Integer
    forall (p :: Nat). PrimeField p -> Integer
    PF.toInteger (PrimeField 1021 -> Integer)
    -> (FField -> PrimeField 1021) -> FField -> Integer
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . FField -> PrimeField 1021
    number (FField -> Int) -> FField -> Int
    forall a b. (a -> b) -> a -> b
    $
                    [FField] -> FField -> FField
    evalPolynomial (FField
    secretFField -> [FField] -> [FField]
    forall a. a -> [a] -> [a]
    :[FField]
    coeffs) (Int -> FField
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    i::FField)
                | Int
    i <- [Int
    1..Int
    n]
                ]

    decodeByte :: [ByteShare] -> FField
    decodeByte :: [ByteShare] -> FField
    decodeByte [ByteShare]
    ss =
      let m :: Int
    m = ByteShare -> Int
    reconstructionThreshold (ByteShare -> Int) -> ByteShare -> Int
    forall a b. (a -> b) -> a -> b
    $ [ByteShare] -> ByteShare
    forall a. HasCallStack => [a] -> a
    head [ByteShare]
    ss in
      if [ByteShare] -> Int
    forall a. [a] -> Int
    forall (t :: * -> *) a. Foldable t => t a -> Int
    length [ByteShare]
    ss Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    m
        then AssertionFailed -> FField
    forall a e. Exception e => e -> a
    throw (AssertionFailed -> FField) -> AssertionFailed -> FField
    forall a b. (a -> b) -> a -> b
    $ String -> AssertionFailed
    AssertionFailed String
    "decodeByte: insufficient number of shares for reconstruction!"
        else
          let shares :: [ByteShare]
    shares = Int -> [ByteShare] -> [ByteShare]
    forall a. Int -> [a] -> [a]
    take Int
    m [ByteShare]
    ss
              pts :: [(FField, FField)]
    pts = (ByteShare -> (FField, FField))
    -> [ByteShare] -> [(FField, FField)]
    forall a b. (a -> b) -> [a] -> [b]
    map (\ByteShare
    s -> (Int -> FField
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int -> FField) -> Int -> FField
    forall a b. (a -> b) -> a -> b
    $ ByteShare -> Int
    shareId ByteShare
    s,Int -> FField
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int -> FField) -> Int -> FField
    forall a b. (a -> b) -> a -> b
    $ ByteShare -> Int
    shareValue ByteShare
    s))
                        [ByteShare]
    shares
          in
          [(FField, FField)] -> FField -> FField
    forall a. Fractional a => [(a, a)] -> a -> a
    polyInterp [(FField, FField)]
    pts FField
    0

    -- | Groups a list into blocks of certain size. Running time: /O(n)/
    groupInto :: Int -> [a] -> [[a]]
    groupInto :: forall a. Int -> [a] -> [[a]]
    groupInto Int
    num [a]
    as
      | Int
    num Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0  = AssertionFailed -> [[a]]
    forall a e. Exception e => e -> a
    throw (AssertionFailed -> [[a]]) -> AssertionFailed -> [[a]]
    forall a b. (a -> b) -> a -> b
    $ String -> AssertionFailed
    AssertionFailed String
    "groupInto: Need positive number as argument."
      | Bool
    otherwise =
        let ([a]
    fs,[a]
    ss) = Int -> [a] -> ([a], [a])
    forall a. Int -> [a] -> ([a], [a])
    L.splitAt Int
    num [a]
    as in
        if [a] -> Bool
    forall a. [a] -> Bool
    forall (t :: * -> *) a. Foldable t => t a -> Bool
    L.null [a]
    ss
          then [[a]
    fs]
          else [a]
    fs [a] -> [[a]] -> [[a]]
    forall a. a -> [a] -> [a]
    : Int -> [a] -> [[a]]
    forall a. Int -> [a] -> [[a]]
    groupInto Int
    num [a]
    ss

    -- | A finite prime field. All computations are performed in this field.
    newtype FField = FField { FField -> PrimeField 1021
    number :: $(primeField $ fromIntegral 1021) }
      deriving(Int -> FField -> ShowS
    [FField] -> ShowS
    FField -> String
    (Int -> FField -> ShowS)
    -> (FField -> String) -> ([FField] -> ShowS) -> Show FField
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> FField -> ShowS
    showsPrec :: Int -> FField -> ShowS
    $cshow :: FField -> String
    show :: FField -> String
    $cshowList :: [FField] -> ShowS
    showList :: [FField] -> ShowS
    Show,ReadPrec [FField]
    ReadPrec FField
    Int -> ReadS FField
    ReadS [FField]
    (Int -> ReadS FField)
    -> ReadS [FField]
    -> ReadPrec FField
    -> ReadPrec [FField]
    -> Read FField
    forall a.
    (Int -> ReadS a)
    -> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
    $creadsPrec :: Int -> ReadS FField
    readsPrec :: Int -> ReadS FField
    $creadList :: ReadS [FField]
    readList :: ReadS [FField]
    $creadPrec :: ReadPrec FField
    readPrec :: ReadPrec FField
    $creadListPrec :: ReadPrec [FField]
    readListPrec :: ReadPrec [FField]
    Read,Eq FField
    Eq FField
    -> (FField -> FField -> Ordering)
    -> (FField -> FField -> Bool)
    -> (FField -> FField -> Bool)
    -> (FField -> FField -> Bool)
    -> (FField -> FField -> Bool)
    -> (FField -> FField -> FField)
    -> (FField -> FField -> FField)
    -> Ord FField
    FField -> FField -> Bool
    FField -> FField -> Ordering
    FField -> FField -> FField
    forall a.
    Eq a
    -> (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: FField -> FField -> Ordering
    compare :: FField -> FField -> Ordering
    $c< :: FField -> FField -> Bool
    < :: FField -> FField -> Bool
    $c<= :: FField -> FField -> Bool
    <= :: FField -> FField -> Bool
    $c> :: FField -> FField -> Bool
    > :: FField -> FField -> Bool
    $c>= :: FField -> FField -> Bool
    >= :: FField -> FField -> Bool
    $cmax :: FField -> FField -> FField
    max :: FField -> FField -> FField
    $cmin :: FField -> FField -> FField
    min :: FField -> FField -> FField
    Ord,FField -> FField -> Bool
    (FField -> FField -> Bool)
    -> (FField -> FField -> Bool) -> Eq FField
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: FField -> FField -> Bool
    == :: FField -> FField -> Bool
    $c/= :: FField -> FField -> Bool
    /= :: FField -> FField -> Bool
    Eq,Integer -> FField
    FField -> FField
    FField -> FField -> FField
    (FField -> FField -> FField)
    -> (FField -> FField -> FField)
    -> (FField -> FField -> FField)
    -> (FField -> FField)
    -> (FField -> FField)
    -> (FField -> FField)
    -> (Integer -> FField)
    -> Num FField
    forall a.
    (a -> a -> a)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> (a -> a)
    -> (a -> a)
    -> (a -> a)
    -> (Integer -> a)
    -> Num a
    $c+ :: FField -> FField -> FField
    + :: FField -> FField -> FField
    $c- :: FField -> FField -> FField
    - :: FField -> FField -> FField
    $c* :: FField -> FField -> FField
    * :: FField -> FField -> FField
    $cnegate :: FField -> FField
    negate :: FField -> FField
    $cabs :: FField -> FField
    abs :: FField -> FField
    $csignum :: FField -> FField
    signum :: FField -> FField
    $cfromInteger :: Integer -> FField
    fromInteger :: Integer -> FField
    Num,Num FField
    Num FField
    -> (FField -> FField -> FField)
    -> (FField -> FField)
    -> (Rational -> FField)
    -> Fractional FField
    Rational -> FField
    FField -> FField
    FField -> FField -> FField
    forall a.
    Num a
    -> (a -> a -> a) -> (a -> a) -> (Rational -> a) -> Fractional a
    $c/ :: FField -> FField -> FField
    / :: FField -> FField -> FField
    $crecip :: FField -> FField
    recip :: FField -> FField
    $cfromRational :: Rational -> FField
    fromRational :: Rational -> FField
    Fractional,(forall x. FField -> Rep FField x)
    -> (forall x. Rep FField x -> FField) -> Generic FField
    forall x. Rep FField x -> FField
    forall x. FField -> Rep FField x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    $cfrom :: forall x. FField -> Rep FField x
    from :: forall x. FField -> Rep FField x
    $cto :: forall x. Rep FField x -> FField
    to :: forall x. Rep FField x -> FField
    Generic,Typeable,Fractional FField
    [FField]
    Fractional FField
    -> (FField -> Integer)
    -> (FField -> Integer)
    -> (FField -> FField)
    -> [FField]
    -> FiniteField FField
    FField -> Integer
    FField -> FField
    forall k.
    Fractional k
    -> (k -> Integer)
    -> (k -> Integer)
    -> (k -> k)
    -> [k]
    -> FiniteField k
    $corder :: FField -> Integer
    order :: FField -> Integer
    $cchar :: FField -> Integer
    char :: FField -> Integer
    $cpthRoot :: FField -> FField
    pthRoot :: FField -> FField
    $callValues :: [FField]
    allValues :: [FField]
    FiniteField)

    -- | The size of the finite field
    prime :: Int
    prime :: Int
    prime = Integer -> Int
    forall a. Num a => Integer -> a
    fromInteger (Integer -> Int) -> Integer -> Int
    forall a b. (a -> b) -> a -> b
    $ FField -> Integer
    forall k. FiniteField k => k -> Integer
    order (FField
    0 :: FField)

    -- | A polynomial over the finite field given as a list of coefficients.
    type Polyn = [FField]

    -- | Evaluates the polynomial at a given point.
    evalPolynomial :: Polyn -> FField -> FField
    evalPolynomial :: [FField] -> FField -> FField
    evalPolynomial [FField]
    coeffs FField
    x =
      (FField -> FField -> FField) -> FField -> [FField] -> FField
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (\FField
    c FField
    res -> FField
    c FField -> FField -> FField
    forall a. Num a => a -> a -> a
    + (FField
    x FField -> FField -> FField
    forall a. Num a => a -> a -> a
    * FField
    res)) FField
    0 [FField]
    coeffs
    --  let clist = zipWith (\pow c -> (\x -> c * (x^pow))) [0..] coeffs
    --  in L.foldl' (+) 0 [ c x | c <- clist ]