    -- |
    -- Module      : Crypto.Math.F2m
    -- License     : BSD-style
    -- Maintainer  : Danny Navarro <j@dannynavarro.net>
    -- Stability   : experimental
    -- Portability : Good
    --
    -- This module provides basic arithmetic operations over F₂m. Performance is
    -- not optimal and it doesn't provide protection against timing
    -- attacks. The 'm' parameter is implicitly derived from the irreducible
    -- polynomial where applicable.

    module Crypto.Number.F2m
        ( BinaryPolynomial
        , addF2m
        , mulF2m
        , squareF2m'
        , squareF2m
        , powF2m
        , modF2m
        , sqrtF2m
        , invF2m
        , divF2m
        ) where

    import Data.Bits (xor, shift, testBit, setBit)
    import Data.List
    import Crypto.Number.Basic

    -- | Binary Polynomial represented by an integer
    type BinaryPolynomial = Integer

    -- | Addition over F₂m. This is just a synonym of 'xor'.
    addF2m :: Integer
           -> Integer
           -> Integer
    addF2m :: Integer -> Integer -> Integer
    addF2m = Integer -> Integer -> Integer
    forall a. Bits a => a -> a -> a
    xor
    {-# INLINE addF2m #-}

    -- | Reduction by modulo over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    modF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Integer
    modF2m :: Integer -> Integer -> Integer
    modF2m Integer
    fx Integer
    i
        | Integer
    fx Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0 Bool -> Bool -> Bool
    || Integer
    i Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0 = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "modF2m: negative number represent no binary polynomial"
        | Integer
    fx Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0         = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "modF2m: cannot divide by zero polynomial"
        | Integer
    fx Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1         = Integer
    0
        | Bool
    otherwise       = Integer -> Integer
    go Integer
    i
          where
            lfx :: Int
    lfx = Integer -> Int
    log2 Integer
    fx
            go :: Integer -> Integer
    go Integer
    n | Int
    s Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    0    = Integer
    n Integer -> Integer -> Integer
    `addF2m` Integer
    fx
                 | Int
    s Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    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 #-}

    -- | Multiplication over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    mulF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Integer
           -> Integer
    mulF2m :: Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    n1 Integer
    n2
        |    Integer
    fx Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0
          Bool -> Bool -> Bool
    || Integer
    n1 Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0
          Bool -> Bool -> Bool
    || Integer
    n2 Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0 = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "mulF2m: negative number represent no binary polynomial"
        | Integer
    fx Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0   = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "mulF2m: 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` Integer
    2 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1 then Integer
    n1 else Integer
    0) (Integer -> Int
    log2 Integer
    n2)
          where
            go :: Integer -> Int -> Integer
    go Integer
    n Int
    s | Int
    s Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    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
    - Int
    1)
                                    else Integer -> Int -> Integer
    go Integer
    n (Int
    s Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1)
    {-# INLINABLE mulF2m #-}

    -- | Squaring over F₂m.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    squareF2m :: BinaryPolynomial -- ^ Modulus
              -> Integer
              -> Integer
    squareF2m :: Integer -> Integer -> Integer
    squareF2m 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 #-}

    -- | Squaring over F₂m without reduction by modulo.
    --
    -- The implementation utilizes the fact that for binary polynomial S(x) we have
    -- S(x)^2 = S(x^2). In other words, insert a zero bit between every bits of argument: 1101 -> 1010001.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent.
    squareF2m' :: Integer
               -> Integer
    squareF2m' :: Integer -> Integer
    squareF2m' Integer
    n
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0     = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "mulF2m: negative number represent no binary polynomial"
        | Bool
    otherwise = (Integer -> Int -> Integer) -> Integer -> [Int] -> Integer
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    foldl' (\Integer
    acc 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 (Int
    2 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    s) else Integer
    acc) Integer
    0 [Int
    0 .. Integer -> Int
    log2 Integer
    n]
    {-# INLINE squareF2m' #-}

    -- | Exponentiation in F₂m by computing @a^b mod fx@.
    --
    -- This implements an exponentiation by squaring based solution. It inherits the
    -- same restrictions as 'squareF2m'. Negative exponents are disallowed.
    powF2m :: BinaryPolynomial -- ^Modulus
           -> Integer          -- ^a
           -> Integer          -- ^b
           -> Integer
    powF2m :: Integer -> Integer -> Integer -> Integer
    powF2m Integer
    fx Integer
    a Integer
    b
      | Integer
    b Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    0     = [Char] -> Integer
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "powF2m: negative exponents disallowed"
      | Integer
    b Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0    = if Integer
    fx Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > Integer
    1 then Integer
    1 else Integer
    0
      | Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    b    = Integer -> Integer -> Integer
    squareF2m Integer
    fx Integer
    x
      | Bool
    otherwise = Integer -> Integer -> Integer -> Integer
    mulF2m Integer
    fx Integer
    a (Integer -> Integer
    squareF2m' Integer
    x)
      where x :: Integer
    x = Integer -> Integer -> Integer -> Integer
    powF2m Integer
    fx Integer
    a (Integer
    b Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2)

    -- | Square rooot in F₂m.
    --
    -- We exploit the fact that @a^(2^m) = a@, or in particular, @a^(2^m - 1) = 1@
    -- from a classical result by Lagrange. Thus the square root is simply @a^(2^(m
    -- - 1))@.
    sqrtF2m :: BinaryPolynomial -- ^Modulus
            -> Integer          -- ^a
            -> Integer
    sqrtF2m :: Integer -> Integer -> Integer
    sqrtF2m Integer
    fx Integer
    a = Int -> Integer -> Integer
    forall {t}. (Eq t, Num t) => t -> Integer -> Integer
    go (Integer -> Int
    log2 Integer
    fx Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Integer
    a
      where go :: t -> Integer -> Integer
    go t
    0 Integer
    x = Integer
    x
            go t
    n Integer
    x = t -> Integer -> Integer
    go (t
    n t -> t -> t
    forall a. Num a => a -> a -> a
    - t
    1) (Integer -> Integer -> Integer
    squareF2m Integer
    fx Integer
    x)

    -- | Extended GCD algorithm for polynomials. For @a@ and @b@ returns @(g, u, v)@ such that @a * u + b * v == g@.
    --
    -- Reference: https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#B.C3.A9zout.27s_identity_and_extended_GCD_algorithm
    gcdF2m :: Integer
           -> Integer
           -> (Integer, Integer, Integer)
    gcdF2m :: Integer -> Integer -> (Integer, Integer, Integer)
    gcdF2m Integer
    a Integer
    b = (Integer, Integer, Integer, Integer, Integer, Integer)
    -> (Integer, Integer, Integer)
    go (Integer
    a, Integer
    b, Integer
    1, Integer
    0, Integer
    0, Integer
    1)
      where
        go :: (Integer, Integer, Integer, Integer, Integer, Integer)
    -> (Integer, Integer, Integer)
    go (Integer
    g, Integer
    0, Integer
    u, Integer
    _, Integer
    v, Integer
    _)
            = (Integer
    g, Integer
    u, Integer
    v)
        go (Integer
    r0, Integer
    r1, Integer
    s0, Integer
    s1, Integer
    t0, 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 Int
    0 (Integer -> Int
    log2 Integer
    r0 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Integer -> Int
    log2 Integer
    r1)

    -- | Modular inversion over F₂m.
    -- If @n@ doesn't have an inverse, 'Nothing' is returned.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    invF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer
           -> Maybe Integer
    invF2m :: Integer -> Integer -> Maybe Integer
    invF2m Integer
    fx Integer
    n = if Integer
    g Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    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
        (Integer
    g, Integer
    u, Integer
    _) = Integer -> Integer -> (Integer, Integer, Integer)
    gcdF2m Integer
    n Integer
    fx
    {-# INLINABLE invF2m #-}

    -- | Division over F₂m. If the dividend doesn't have an inverse it returns
    -- 'Nothing'.
    --
    -- This function is undefined for negative arguments, because their bit
    -- representation is platform-dependent. Zero modulus is also prohibited.
    divF2m :: BinaryPolynomial -- ^ Modulus
           -> Integer          -- ^ Dividend
           -> Integer          -- ^ Divisor
           -> Maybe Integer    -- ^ Quotient
    divF2m :: Integer -> Integer -> Integer -> Maybe Integer
    divF2m Integer
    fx Integer
    n1 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 #-}