{-# LANGUAGE BangPatterns #-}

module CryptoMath where

fastpow :: Integer -> Integer -> Integer -> Integer
fastpow base exp modulo =
  let fastpow' b 0 m !r = r
      fastpow' b e m r = fastpow' (mod (b * b) m) (div e 2) m (if even e then r else mod (r * b) m)
   in fastpow' (mod base modulo) exp modulo 1

-- |
-- >>> gcd' 55 30
-- 5
gcd' :: Integer -> Integer -> Integer
gcd' a b =
  if mod a b == 0
    then b
    else gcd' b (mod a b)

-- |
-- >>> modInv 5 66
-- Just 53

-- |
-- >>> modInv 6 66
-- Nothing
modInv :: Integer -> Integer -> Maybe Integer
modInv a m
  | 1 == g = Just (mkPos i)
  | otherwise = Nothing
  where
    (i, _, g) = gcdExt a m
    mkPos x
      | x < 0 = x + m
      | otherwise = x

-- Extended Euclidean algorithm.
-- Given non-negative a and b, return x, y and g
-- such that ax + by = g, where g = gcd(a,b).
-- Note that x or y may be negative.
gcdExt :: Integer -> Integer -> (Integer, Integer, Integer)
gcdExt a 0 = (1, 0, a)
gcdExt a b =
  let (q, r) = quotRem a b
      (s, t, g) = gcdExt b r
   in (t, s - q * t, g)