{-# OPTIONS_GHC -O2 -feager-blackholing #-}
{-# LANGUAGE Safe, BangPatterns, NoImplicitPrelude #-}
module Crypto.Fi ( FPrime
, eq
, add
, addr
, sub
, subr
, neg
, shift
, mul
, mulr
, redc
, square
, pow
, inv
, fromInteger
, toInteger
, condBit
)
where
import safe Prelude ((==),Integer,Int,Bool(),($),(+),(-),(*),(^),mod,otherwise,(<))
import safe qualified Prelude as P (fromInteger,toInteger)
import safe qualified Data.Bits as B (Bits(..),shift,(.&.))
import safe Crypto.Common (log2len)
type FPrime = Integer
eq :: FPrime -> FPrime -> Bool
eq :: FPrime -> FPrime -> Bool
eq !FPrime
a !FPrime
b = FPrime
a forall a. Eq a => a -> a -> Bool
== FPrime
b
{-# INLINABLE eq #-}
add :: FPrime -> FPrime -> FPrime
add :: FPrime -> FPrime -> FPrime
add !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
+ FPrime
b
{-# INLINABLE add #-}
addr :: FPrime -> FPrime -> FPrime -> FPrime
addr :: FPrime -> FPrime -> FPrime -> FPrime
addr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime
a forall a. Num a => a -> a -> a
+ FPrime
b
{-# INLINABLE addr #-}
sub :: FPrime -> FPrime -> FPrime
sub :: FPrime -> FPrime -> FPrime
sub !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
- FPrime
b
{-# INLINABLE sub #-}
subr :: FPrime -> FPrime -> FPrime -> FPrime
subr :: FPrime -> FPrime -> FPrime -> FPrime
subr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p (FPrime
a forall a. Num a => a -> a -> a
- FPrime
b)
{-# INLINABLE subr #-}
neg :: FPrime -> FPrime -> FPrime
neg :: FPrime -> FPrime -> FPrime
neg !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p (-FPrime
a)
{-# INLINABLE neg #-}
shift :: FPrime -> Int -> FPrime
shift :: FPrime -> Int -> FPrime
shift !FPrime
a !Int
b = forall a. Bits a => a -> Int -> a
B.shift FPrime
a Int
b
redc :: FPrime -> FPrime -> FPrime
redc :: FPrime -> FPrime -> FPrime
redc !FPrime
p !FPrime
a = FPrime
a forall a. Integral a => a -> a -> a
`mod` FPrime
p
{-# INLINABLE redc #-}
mul :: FPrime -> FPrime -> FPrime
mul :: FPrime -> FPrime -> FPrime
mul !FPrime
a !FPrime
b = FPrime
a forall a. Num a => a -> a -> a
* FPrime
b
{-# INLINABLE mul #-}
mulr :: FPrime -> FPrime -> FPrime -> FPrime
mulr :: FPrime -> FPrime -> FPrime -> FPrime
mulr !FPrime
p !FPrime
a !FPrime
b = FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime
a forall a. Num a => a -> a -> a
* FPrime
b
{-# INLINABLE mulr #-}
square :: FPrime -> FPrime -> FPrime
square :: FPrime -> FPrime -> FPrime
square !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p (FPrime
a forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
2::Int))
{-# INLINABLE square #-}
pow :: FPrime -> FPrime -> Integer -> FPrime
pow :: FPrime -> FPrime -> FPrime -> FPrime
pow !FPrime
p !FPrime
a' !FPrime
k = let a :: FPrime
a = FPrime -> FPrime -> FPrime
redc FPrime
p FPrime
a'
binlog :: Int
binlog = FPrime -> Int
log2len FPrime
a
alleeins :: FPrime
alleeins = Int -> FPrime -> FPrime
fromInteger Int
binlog (FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^Int
binlog forall a. Num a => a -> a -> a
- FPrime
1)
eins :: FPrime
eins = Int -> FPrime -> FPrime
fromInteger Int
binlog FPrime
1
ex :: FPrime -> Int -> FPrime
ex FPrime
erg Int
i
| Int
i forall a. Ord a => a -> a -> Bool
< Int
0 = FPrime
erg
| Bool
otherwise =
let s :: FPrime
s = FPrime -> Int -> FPrime
condBit FPrime
k Int
i
pat :: FPrime
pat = FPrime -> FPrime -> FPrime
mul FPrime
alleeins FPrime
s
invpat :: FPrime
invpat = FPrime -> FPrime -> FPrime
mul FPrime
alleeins (FPrime -> FPrime -> FPrime
sub FPrime
eins FPrime
s)
in FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime -> Int -> FPrime
ex (FPrime -> FPrime -> FPrime -> FPrime
mulr FPrime
p (FPrime -> FPrime -> FPrime
square FPrime
p FPrime
erg) (FPrime -> FPrime -> FPrime -> FPrime
addr FPrime
p (FPrime
a forall a. Bits a => a -> a -> a
B..&. FPrime
pat) (FPrime
eins forall a. Bits a => a -> a -> a
B..&. FPrime
invpat))) (Int
i forall a. Num a => a -> a -> a
- Int
1)
in FPrime -> FPrime -> FPrime
redc FPrime
p forall a b. (a -> b) -> a -> b
$ FPrime -> Int -> FPrime
ex FPrime
1 (FPrime -> Int
log2len FPrime
k forall a. Num a => a -> a -> a
- Int
1)
inv :: FPrime -> FPrime -> FPrime
inv :: FPrime -> FPrime -> FPrime
inv !FPrime
p !FPrime
a = FPrime -> FPrime -> FPrime -> FPrime
pow FPrime
p FPrime
a (FPrime -> FPrime
toInteger FPrime
p forall a. Num a => a -> a -> a
- FPrime
2)
fromInteger :: Int -> FPrime -> Integer
fromInteger :: Int -> FPrime -> FPrime
fromInteger !Int
l !FPrime
a = forall a. Num a => FPrime -> a
P.fromInteger (FPrime
a forall a. Integral a => a -> a -> a
`mod` (FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^Int
l))
{-# INLINABLE fromInteger #-}
toInteger :: FPrime -> Integer
toInteger :: FPrime -> FPrime
toInteger !FPrime
a = forall a. Integral a => a -> FPrime
P.toInteger FPrime
a
{-# INLINABLE toInteger #-}
condBit :: FPrime -> Int -> FPrime
condBit :: FPrime -> Int -> FPrime
condBit !FPrime
a !Int
i = FPrime -> Int -> FPrime
shift (FPrime
a forall a. Bits a => a -> a -> a
B..&. Int -> FPrime -> FPrime
fromInteger (Int
iforall a. Num a => a -> a -> a
+Int
1) ((FPrime
2forall a b. (Num a, Integral b) => a -> b -> a
^(Int
iforall a. Num a => a -> a -> a
+Int
1)forall a. Num a => a -> a -> a
-FPrime
1)::Integer)) (-Int
i)
{-# INLINABLE condBit #-}