{-# 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 ]