module Legacy.Haskoin.V0102.Network.Haskoin.Crypto.NumberTheory
  ( extendedModGCD
  , mulInverse
  ) where

-- Extended euclidean algorithm
-- Calculates the multiplicative inverse modulo p
extendedModGCD :: Integer -> Integer -> Integer -> (Integer, Integer)
extendedModGCD a b p
  | b == 0 = (1, 0)
  | otherwise = (t, (s - q * t) `mod` p)
  where
    (q, r) = quotRem a b
    (s, t) = extendedModGCD b r p

-- Find multiplicative inverse of a : a*s = 1 (mod p)
mulInverse :: Integer -> Integer -> Integer
mulInverse a p
  | a * s `mod` p == 1 = s
  | otherwise = error "No multiplicative inverse (mod p) for a"
  where
    (s, _) = extendedModGCD a p p