{-# LANGUAGE DataKinds, DeriveDataTypeable, DeriveGeneric, GeneralizedNewtypeDeriving, TemplateHaskell #-}
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
polyInterp :: Fractional a => [(a, a)] -> a -> a
polyInterp :: [(a, a)] -> a -> a
polyInterp xys :: [(a, a)]
xys x :: a
x = [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 (left :: [(a, b)]
left, (xj :: a
xj, yj :: a
yj), right :: [(a, b)]
right) =
a
yj a -> a -> a
forall a. Num a => a -> a -> 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 (\(xm :: a
xm, _) -> (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))
slidingFocus :: [a] -> [([a], a, [a])]
slidingFocus :: [a] -> [([a], a, [a])]
slidingFocus [] = []
slidingFocus (x :: a
x : xs :: [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 left :: [t]
left focus :: t
focus right :: [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
[] -> []
focus' :: t
focus' : right' :: [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'
data ByteShare = ByteShare
{ ByteShare -> Int
shareId :: !Int
, ByteShare -> Int
reconstructionThreshold :: !Int
, ByteShare -> Int
shareValue :: !Int
}
deriving(Typeable,ByteShare -> ByteShare -> Bool
(ByteShare -> ByteShare -> Bool)
-> (ByteShare -> ByteShare -> Bool) -> Eq ByteShare
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: ByteShare -> ByteShare -> Bool
$c/= :: ByteShare -> ByteShare -> Bool
== :: ByteShare -> ByteShare -> Bool
$c== :: 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
$cto :: forall x. Rep ByteShare x -> ByteShare
$cfrom :: forall x. ByteShare -> Rep ByteShare x
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
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
/= :: Share -> Share -> Bool
$c/= :: Share -> Share -> Bool
== :: Share -> Share -> Bool
$c== :: 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
$cto :: forall x. Rep Share x -> Share
$cfrom :: forall x. Share -> Rep Share x
Generic)
instance Show Share where
show :: Share -> String
show s :: 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. [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
encode :: Int
-> Int
-> ByteString
-> IO [Share]
encode :: Int -> Int -> ByteString -> IO [Share]
encode m :: Int
m n :: Int
n bstr :: 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
$
"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]
++ " and m<=n."
| ByteString -> Bool
BL.null ByteString
bstr = [Share] -> IO [Share]
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 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
-1))
[[FField]]
coeffs <- (Int -> [FField] -> [[FField]]
forall a. Int -> [a] -> [[a]]
groupInto (Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
-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 (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
-1)) [Vector ByteShare]
byteVecs | Int
i <- [1..Int
n] ]
decode :: [Share]
-> ByteString
decode :: [Share] -> ByteString
decode [] = [Word8] -> ByteString
BL.pack []
decode shares :: [Share]
shares@((Share s :: [ByteShare]
s):_)
| [Share] -> 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. [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
"decode: not enough shares for reconstruction."
| Bool
otherwise =
let origLength :: Int
origLength = [ByteShare] -> 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
-1))) [Vector ByteShare]
byteVecs | Int
i <- [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 m :: Int
m n :: Int
n coeffs :: [FField]
coeffs secret :: 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 <- [1..Int
n]
]
decodeByte :: [ByteShare] -> FField
decodeByte :: [ByteShare] -> FField
decodeByte ss :: [ByteShare]
ss =
let m :: Int
m = ByteShare -> Int
reconstructionThreshold (ByteShare -> Int) -> ByteShare -> Int
forall a b. (a -> b) -> a -> b
$ [ByteShare] -> ByteShare
forall a. [a] -> a
head [ByteShare]
ss in
if [ByteShare] -> 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 "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 (\s :: 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 0
groupInto :: Int -> [a] -> [[a]]
groupInto :: Int -> [a] -> [[a]]
groupInto num :: Int
num as :: [a]
as
| Int
num Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 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 "groupInto: Need positive number as argument."
| Bool
otherwise =
let (fs :: [a]
fs,ss :: [a]
ss) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
num [a]
as in
if [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
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
showList :: [FField] -> ShowS
$cshowList :: [FField] -> ShowS
show :: FField -> String
$cshow :: FField -> String
showsPrec :: Int -> FField -> ShowS
$cshowsPrec :: Int -> 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
readListPrec :: ReadPrec [FField]
$creadListPrec :: ReadPrec [FField]
readPrec :: ReadPrec FField
$creadPrec :: ReadPrec FField
readList :: ReadS [FField]
$creadList :: ReadS [FField]
readsPrec :: Int -> ReadS FField
$creadsPrec :: Int -> ReadS 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
min :: FField -> FField -> FField
$cmin :: FField -> FField -> FField
max :: FField -> FField -> FField
$cmax :: FField -> FField -> FField
>= :: FField -> FField -> Bool
$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
compare :: FField -> FField -> Ordering
$ccompare :: FField -> FField -> Ordering
$cp1Ord :: Eq FField
Ord,FField -> FField -> Bool
(FField -> FField -> Bool)
-> (FField -> FField -> Bool) -> Eq FField
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FField -> FField -> Bool
$c/= :: FField -> FField -> Bool
== :: FField -> FField -> Bool
$c== :: 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
fromInteger :: Integer -> FField
$cfromInteger :: Integer -> FField
signum :: FField -> FField
$csignum :: FField -> FField
abs :: FField -> FField
$cabs :: FField -> FField
negate :: FField -> FField
$cnegate :: FField -> FField
* :: FField -> FField -> FField
$c* :: FField -> FField -> FField
- :: FField -> FField -> FField
$c- :: FField -> FField -> FField
+ :: FField -> FField -> FField
$c+ :: FField -> FField -> 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
fromRational :: Rational -> FField
$cfromRational :: Rational -> FField
recip :: FField -> FField
$crecip :: FField -> FField
/ :: FField -> FField -> FField
$c/ :: FField -> FField -> FField
$cp1Fractional :: Num 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
$cto :: forall x. Rep FField x -> FField
$cfrom :: forall x. FField -> Rep FField x
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
allValues :: [FField]
$callValues :: [FField]
pthRoot :: FField -> FField
$cpthRoot :: FField -> FField
char :: FField -> Integer
$cchar :: FField -> Integer
order :: FField -> Integer
$corder :: FField -> Integer
$cp1FiniteField :: Fractional FField
FiniteField)
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 (0 :: FField)
type Polyn = [FField]
evalPolynomial :: Polyn -> FField -> FField
evalPolynomial :: [FField] -> FField -> FField
evalPolynomial coeffs :: [FField]
coeffs x :: FField
x =
(FField -> FField -> FField) -> FField -> [FField] -> FField
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\c :: FField
c res :: 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)) 0 [FField]
coeffs