{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE CPP #-}
#ifndef MIN_VERSION_integer_gmp
#define MIN_VERSION_integer_gmp(a,b,c) 0
#endif
module Crypto.Number.ModArithmetic
(
expSafe
, expFast
, exponentiation_rtl_binary
, exponentiation
, exponantiation_rtl_binary
, exponantiation
, inverse
, inverseCoprimes
) where
import Control.Exception (throw, Exception)
import Data.Typeable
#if MIN_VERSION_integer_gmp(0,5,1)
import GHC.Integer.GMP.Internals
#else
import Crypto.Number.Basic (gcde_binary)
import Data.Bits
#endif
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,Typeable)
instance Exception CoprimesAssertionError
expSafe :: Integer
-> Integer
-> Integer
-> Integer
#if MIN_VERSION_integer_gmp(0,5,1)
expSafe :: Integer -> Integer -> Integer -> Integer
expSafe b :: Integer
b e :: Integer
e m :: Integer
m
#if !(MIN_VERSION_integer_gmp(1,0,0))
| odd m = powModSecInteger b e m
#endif
| Bool
otherwise = Integer -> Integer -> Integer -> Integer
powModInteger Integer
b Integer
e Integer
m
#else
expSafe = exponentiation
#endif
expFast :: Integer
-> Integer
-> Integer
-> Integer
expFast :: Integer -> Integer -> Integer -> Integer
expFast =
#if MIN_VERSION_integer_gmp(0,5,1)
Integer -> Integer -> Integer -> Integer
powModInteger
#else
exponentiation
#endif
exponentiation_rtl_binary :: Integer -> Integer -> Integer -> Integer
#if MIN_VERSION_integer_gmp(0,5,1)
exponentiation_rtl_binary :: Integer -> Integer -> Integer -> Integer
exponentiation_rtl_binary = Integer -> Integer -> Integer -> Integer
expSafe
#else
exponentiation_rtl_binary 0 0 m = 1 `mod` m
exponentiation_rtl_binary b e m = loop e b 1
where sq x = (x * x) `mod` m
loop !0 _ !a = a `mod` m
loop !i !s !a = loop (i `shiftR` 1) (sq s) (if odd i then a * s else a)
#endif
exponentiation :: Integer -> Integer -> Integer -> Integer
#if MIN_VERSION_integer_gmp(0,5,1)
exponentiation :: Integer -> Integer -> Integer -> Integer
exponentiation = Integer -> Integer -> Integer -> Integer
expSafe
#else
exponentiation b e m
| b == 1 = b
| e == 0 = 1
| e == 1 = b `mod` m
| even e = let p = (exponentiation b (e `div` 2) m) `mod` m
in (p^(2::Integer)) `mod` m
| otherwise = (b * exponentiation b (e-1) m) `mod` m
#endif
exponantiation_rtl_binary :: Integer -> Integer -> Integer -> Integer
exponantiation_rtl_binary :: Integer -> Integer -> Integer -> Integer
exponantiation_rtl_binary = Integer -> Integer -> Integer -> Integer
exponentiation_rtl_binary
exponantiation :: Integer -> Integer -> Integer -> Integer
exponantiation :: Integer -> Integer -> Integer -> Integer
exponantiation = Integer -> Integer -> Integer -> Integer
exponentiation
inverse :: Integer -> Integer -> Maybe Integer
#if MIN_VERSION_integer_gmp(0,5,1)
inverse :: Integer -> Integer -> Maybe Integer
inverse g :: Integer
g m :: Integer
m
| Integer
r Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Maybe Integer
forall a. Maybe a
Nothing
| Bool
otherwise = Integer -> Maybe Integer
forall a. a -> Maybe a
Just Integer
r
where r :: Integer
r = Integer -> Integer -> Integer
recipModInteger Integer
g Integer
m
#else
inverse g m
| d > 1 = Nothing
| otherwise = Just (x `mod` m)
where (x,_,d) = gcde_binary g m
#endif
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