    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE DeriveDataTypeable #-}
    -- |
    -- Module      : Crypto.Number.ModArithmetic
    -- License     : BSD-style
    -- Maintainer  : Vincent Hanquez <vincent@snarc.org>
    -- Stability   : experimental
    -- Portability : Good

    module Crypto.Number.ModArithmetic
        (
        -- * Exponentiation
          expSafe
        , expFast
        -- * Inverse computing
        , inverse
        , inverseCoprimes
        , jacobi
        ) where

    import Control.Exception (throw, Exception)
    import Crypto.Number.Basic
    import Crypto.Number.Compat

    -- | Raised when two numbers are supposed to be coprimes but are not.
    data CoprimesAssertionError = CoprimesAssertionError
        deriving (Int -> CoprimesAssertionError -> ShowS
    [CoprimesAssertionError] -> ShowS
    CoprimesAssertionError -> String
    (Int -> CoprimesAssertionError -> ShowS)
    -> (CoprimesAssertionError -> String)
    -> ([CoprimesAssertionError] -> ShowS)
    -> Show CoprimesAssertionError
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    showList :: [CoprimesAssertionError] -> ShowS
    $cshowList :: [CoprimesAssertionError] -> ShowS
    show :: CoprimesAssertionError -> String
    $cshow :: CoprimesAssertionError -> String
    showsPrec :: Int -> CoprimesAssertionError -> ShowS
    $cshowsPrec :: Int -> CoprimesAssertionError -> ShowS
    Show)

    instance Exception CoprimesAssertionError

    -- | Compute the modular exponentiation of base^exponent using
    -- algorithms design to avoid side channels and timing measurement
    --
    -- Modulo need to be odd otherwise the normal fast modular exponentiation
    -- is used.
    --
    -- When used with integer-simple, this function is not different
    -- from expFast, and thus provide the same unstudied and dubious
    -- timing and side channels claims.
    --
    -- Before GHC 8.4.2, powModSecInteger is missing from integer-gmp,
    -- so expSafe has the same security as expFast.
    expSafe :: Integer -- ^ base
            -> Integer -- ^ exponent
            -> Integer -- ^ modulo
            -> Integer -- ^ result
    expSafe :: Integer -> Integer -> Integer -> Integer
    expSafe b :: Integer
    b e :: Integer
    e m :: Integer
    m
        | Integer -> Bool
    forall a. Integral a => a -> Bool
    odd Integer
    m     = Integer -> Integer -> Integer -> GmpSupported Integer
    gmpPowModSecInteger Integer
    b Integer
    e Integer
    m GmpSupported Integer -> Integer -> Integer
    forall a. GmpSupported a -> a -> a
    `onGmpUnsupported`
                      (Integer -> Integer -> Integer -> GmpSupported Integer
    gmpPowModInteger Integer
    b Integer
    e Integer
    m   GmpSupported Integer -> Integer -> Integer
    forall a. GmpSupported a -> a -> a
    `onGmpUnsupported`
                      Integer -> Integer -> Integer -> Integer
    exponentiation Integer
    b Integer
    e Integer
    m)
        | Bool
    otherwise = Integer -> Integer -> Integer -> GmpSupported Integer
    gmpPowModInteger Integer
    b Integer
    e Integer
    m    GmpSupported Integer -> Integer -> Integer
    forall a. GmpSupported a -> a -> a
    `onGmpUnsupported`
                      Integer -> Integer -> Integer -> Integer
    exponentiation Integer
    b Integer
    e Integer
    m

    -- | Compute the modular exponentiation of base^exponent using
    -- the fastest algorithm without any consideration for
    -- hiding parameters.
    --
    -- Use this function when all the parameters are public,
    -- otherwise 'expSafe' should be prefered.
    expFast :: Integer -- ^ base
            -> Integer -- ^ exponent
            -> Integer -- ^ modulo
            -> Integer -- ^ result
    expFast :: Integer -> Integer -> Integer -> Integer
    expFast b :: Integer
    b e :: Integer
    e m :: Integer
    m = Integer -> Integer -> Integer -> GmpSupported Integer
    gmpPowModInteger Integer
    b Integer
    e Integer
    m GmpSupported Integer -> Integer -> Integer
    forall a. GmpSupported a -> a -> a
    `onGmpUnsupported` Integer -> Integer -> Integer -> Integer
    exponentiation Integer
    b Integer
    e Integer
    m

    -- | @exponentiation@ computes modular exponentiation as /b^e mod m/
    -- using repetitive squaring.
    exponentiation :: Integer -> Integer -> Integer -> Integer
    exponentiation :: Integer -> Integer -> Integer -> Integer
    exponentiation b :: Integer
    b e :: Integer
    e m :: Integer
    m
        | Integer
    b Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1    = Integer
    b
        | Integer
    e Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0    = 1
        | Integer
    e Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1    = Integer
    b Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m
        | Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    e    = let p :: Integer
    p = (Integer -> Integer -> Integer -> Integer
    exponentiation Integer
    b (Integer
    e Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` 2) Integer
    m) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m
                       in (Integer
    pInteger -> Integer -> Integer
    forall a b. (Num a, Integral b) => a -> b -> a
    ^(2::Integer)) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m
        | Bool
    otherwise = (Integer
    b Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer -> Integer -> Integer -> Integer
    exponentiation Integer
    b (Integer
    eInteger -> Integer -> Integer
    forall a. Num a => a -> a -> a
    -1) Integer
    m) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m

    -- | @inverse@ computes the modular inverse as in /g^(-1) mod m/.
    inverse :: Integer -> Integer -> Maybe Integer
    inverse :: Integer -> Integer -> Maybe Integer
    inverse g :: Integer
    g m :: Integer
    m = Integer -> Integer -> GmpSupported (Maybe Integer)
    gmpInverse Integer
    g Integer
    m GmpSupported (Maybe Integer) -> Maybe Integer -> Maybe Integer
    forall a. GmpSupported a -> a -> a
    `onGmpUnsupported` Maybe Integer
    v
      where
        v :: Maybe Integer
    v
            | Integer
    d Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > 1     = Maybe Integer
    forall a. Maybe a
    Nothing
            | Bool
    otherwise = Integer -> Maybe Integer
    forall a. a -> Maybe a
    Just (Integer
    x Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    m)
        (x :: Integer
    x,_,d :: Integer
    d) = Integer -> Integer -> (Integer, Integer, Integer)
    gcde Integer
    g Integer
    m

    -- | Compute the modular inverse of two coprime numbers.
    -- This is equivalent to inverse except that the result
    -- is known to exists.
    --
    -- If the numbers are not defined as coprime, this function
    -- will raise a 'CoprimesAssertionError'.
    inverseCoprimes :: Integer -> Integer -> Integer
    inverseCoprimes :: Integer -> Integer -> Integer
    inverseCoprimes g :: Integer
    g m :: Integer
    m =
        case Integer -> Integer -> Maybe Integer
    inverse Integer
    g Integer
    m of
            Nothing -> CoprimesAssertionError -> Integer
    forall a e. Exception e => e -> a
    throw CoprimesAssertionError
    CoprimesAssertionError
            Just i :: Integer
    i  -> Integer
    i

    -- | Computes the Jacobi symbol (a/n).
    -- 0 ≤ a < n; n ≥ 3 and odd.
    --
    -- The Legendre and Jacobi symbols are indistinguishable exactly when the
    -- lower argument is an odd prime, in which case they have the same value.
    --
    -- See algorithm 2.149 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.
    jacobi :: Integer -> Integer -> Maybe Integer
    jacobi :: Integer -> Integer -> Maybe Integer
    jacobi a :: Integer
    a n :: Integer
    n
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < 3 Bool -> Bool -> Bool
    || Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    n  = Maybe Integer
    forall a. Maybe a
    Nothing
        | Integer
    a Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 0 Bool -> Bool -> Bool
    || Integer
    a Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 = Integer -> Maybe Integer
    forall a. a -> Maybe a
    Just Integer
    a
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Integer
    a           = Integer -> Integer -> Maybe Integer
    jacobi (Integer
    a Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    n) Integer
    n
        | Integer
    a Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < 0            =
          let b :: Integer
    b = if Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` 4 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 then 1 else -1
           in (Integer -> Integer) -> Maybe Integer -> Maybe Integer
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    *Integer
    b) (Integer -> Integer -> Maybe Integer
    jacobi (-Integer
    a) Integer
    n)
        | Bool
    otherwise        =
          let (e :: Int
    e, a1 :: Integer
    a1) = Integer -> (Int, Integer)
    asPowerOf2AndOdd Integer
    a
              nMod8 :: Integer
    nMod8   = Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` 8
              nMod4 :: Integer
    nMod4   = Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` 4
              a1Mod4 :: Integer
    a1Mod4  = Integer
    a1 Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` 4
              s' :: Integer
    s'      = if Int -> Bool
    forall a. Integral a => a -> Bool
    even Int
    e Bool -> Bool -> Bool
    || Integer
    nMod8 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 Bool -> Bool -> Bool
    || Integer
    nMod8 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 7 then 1 else -1
              s :: Integer
    s       = if Integer
    nMod4 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 3 Bool -> Bool -> Bool
    && Integer
    a1Mod4 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 3 then -Integer
    s' else Integer
    s'
              n1 :: Integer
    n1      = Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    a1
           in if Integer
    a1 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == 1 then Integer -> Maybe Integer
    forall a. a -> Maybe a
    Just Integer
    s
              else (Integer -> Integer) -> Maybe Integer -> Maybe Integer
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    *Integer
    s) (Integer -> Integer -> Maybe Integer
    jacobi Integer
    n1 Integer
    a1)