module CryptoMath where

-- |
-- >>> gcd' 55 30
-- 5
gcd' :: Int -> Int -> Int
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 :: Int -> Int -> Maybe Int
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 :: Int -> Int -> (Int, Int, Int)
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)