module Crypto.Number.F2m
( BinaryPolynomial
, addF2m
, mulF2m
, squareF2m'
, squareF2m
, modF2m
, invF2m
, divF2m
) where
import Data.Bits (xor, shift, testBit, setBit)
import Data.List
import Crypto.Number.Basic
type BinaryPolynomial = Integer
addF2m :: Integer
-> Integer
-> Integer
addF2m :: Integer -> Integer -> Integer
addF2m = Integer -> Integer -> Integer
forall a. Bits a => a -> a -> a
xor
{-# INLINE addF2m #-}
modF2m :: BinaryPolynomial
-> Integer
-> Integer
modF2m :: Integer -> Integer -> Integer
modF2m fx :: Integer
fx i :: Integer
i
| Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 Bool -> Bool -> Bool
|| Integer
i Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: negative number represent no binary polynomial"
| Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: cannot divide by zero polynomial"
| Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1 = 0
| Bool
otherwise = Integer -> Integer
go Integer
i
where
lfx :: Int
lfx = Integer -> Int
log2 Integer
fx
go :: Integer -> Integer
go n :: Integer
n | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Integer
n Integer -> Integer -> Integer
`addF2m` Integer
fx
| Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = Integer
n
| Bool
otherwise = Integer -> Integer
go (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer
n Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
fx Int
s
where s :: Int
s = Integer -> Int
log2 Integer
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
lfx
{-# INLINE modF2m #-}
mulF2m :: BinaryPolynomial
-> Integer
-> Integer
-> Integer
mulF2m :: Integer -> Integer -> Integer -> Integer
mulF2m fx :: Integer
fx n1 :: Integer
n1 n2 :: Integer
n2
| Integer
fx Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0
Bool -> Bool -> Bool
|| Integer
n1 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0
Bool -> Bool -> Bool
|| Integer
n2 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "mulF2m: negative number represent no binary binary polynomial"
| Integer
fx Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "modF2m: cannot multiply modulo zero polynomial"
| Bool
otherwise = Integer -> Integer -> Integer
modF2m Integer
fx (Integer -> Integer) -> Integer -> Integer
forall a b. (a -> b) -> a -> b
$ Integer -> Int -> Integer
go (if Integer
n2 Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` 2 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1 then Integer
n1 else 0) (Integer -> Int
log2 Integer
n2)
where
go :: Integer -> Int -> Integer
go n :: Integer
n s :: Int
s | Int
s Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Integer
n
| Bool
otherwise = if Integer -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Integer
n2 Int
s
then Integer -> Int -> Integer
go (Integer
n Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
n1 Int
s) (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)
else Integer -> Int -> Integer
go Integer
n (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
- 1)
{-# INLINABLE mulF2m #-}
squareF2m :: BinaryPolynomial
-> Integer
-> Integer
squareF2m :: Integer -> Integer -> Integer
squareF2m fx :: Integer
fx = Integer -> Integer -> Integer
modF2m Integer
fx (Integer -> Integer) -> (Integer -> Integer) -> Integer -> Integer
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Integer
squareF2m'
{-# INLINE squareF2m #-}
squareF2m' :: Integer
-> Integer
squareF2m' :: Integer -> Integer
squareF2m' n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 0 = [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error "mulF2m: negative number represent no binary binary polynomial"
| Bool
otherwise = (Integer -> Int -> Integer) -> Integer -> [Int] -> Integer
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\acc :: Integer
acc s :: Int
s -> if Integer -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Integer
n Int
s then Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
setBit Integer
acc (2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
s) else Integer
acc) 0 [0 .. Integer -> Int
log2 Integer
n]
{-# INLINE squareF2m' #-}
gcdF2m :: Integer
-> Integer
-> (Integer, Integer, Integer)
gcdF2m :: Integer -> Integer -> (Integer, Integer, Integer)
gcdF2m a :: Integer
a b :: Integer
b = (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (Integer
a, Integer
b, 1, 0, 0, 1)
where
go :: (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (g :: Integer
g, 0, u :: Integer
u, _, v :: Integer
v, _)
= (Integer
g, Integer
u, Integer
v)
go (r0 :: Integer
r0, r1 :: Integer
r1, s0 :: Integer
s0, s1 :: Integer
s1, t0 :: Integer
t0, t1 :: Integer
t1)
= (Integer, Integer, Integer, Integer, Integer, Integer)
-> (Integer, Integer, Integer)
go (Integer
r1, Integer
r0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
r1 Int
j, Integer
s1, Integer
s0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
s1 Int
j, Integer
t1, Integer
t0 Integer -> Integer -> Integer
`addF2m` Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
shift Integer
t1 Int
j)
where j :: Int
j = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max 0 (Integer -> Int
log2 Integer
r0 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Integer -> Int
log2 Integer
r1)
invF2m :: BinaryPolynomial
-> Integer
-> Maybe Integer
invF2m :: Integer -> Integer -> Maybe Integer
invF2m fx :: Integer
fx n :: Integer
n = if Integer
g Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 1 then Integer -> Maybe Integer
forall a. a -> Maybe a
Just (Integer -> Integer -> Integer
modF2m Integer
fx Integer
u) else Maybe Integer
forall a. Maybe a
Nothing
where
(g :: Integer
g, u :: Integer
u, _) = Integer -> Integer -> (Integer, Integer, Integer)
gcdF2m Integer
n Integer
fx
{-# INLINABLE invF2m #-}
divF2m :: BinaryPolynomial
-> Integer
-> Integer
-> Maybe Integer
divF2m :: Integer -> Integer -> Integer -> Maybe Integer
divF2m fx :: Integer
fx n1 :: Integer
n1 n2 :: Integer
n2 = Integer -> Integer -> Integer -> Integer
mulF2m Integer
fx Integer
n1 (Integer -> Integer) -> Maybe Integer -> Maybe Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Integer -> Integer -> Maybe Integer
invF2m Integer
fx Integer
n2
{-# INLINE divF2m #-}