module Crypto.Number.ModArithmetic
( exponantiation_rtl_binary
, exponantiation
, inverse
, inverseCoprimes
) where
import Control.Exception (throw, Exception)
import Crypto.Number.Basic (gcde_binary)
import Data.Bits
import Data.Typeable
data CoprimesAssertionError = CoprimesAssertionError
deriving (Show,Typeable)
instance Exception CoprimesAssertionError
exponantiation_rtl_binary :: Integer -> Integer -> Integer -> Integer
exponantiation_rtl_binary 0 0 m = 1 `mod` m
exponantiation_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)
exponantiation :: Integer -> Integer -> Integer -> Integer
exponantiation b e m
| b == 1 = b
| e == 0 = 1
| e == 1 = b `mod` m
| even e = let p = (exponantiation b (e `div` 2) m) `mod` m
in (p^(2::Integer)) `mod` m
| otherwise = (b * exponantiation b (e1) m) `mod` m
inverse :: Integer -> Integer -> Maybe Integer
inverse g m = if d > 1 then Nothing else Just (x `mod` m)
where (x,_,d) = gcde_binary g m
inverseCoprimes :: Integer -> Integer -> Integer
inverseCoprimes g m =
case inverse g m of
Nothing -> throw CoprimesAssertionError
Just i -> i