haskell - Haskell中的模逆

到目前为止，我已经解决了euclid，lCM，extGCD和coprime。我该如何解决模块化的Inverse(minv)问题？我认为“假设n为互质”使我感到困惑。

euclid :: Integer -> Integer -> Integer
euclid 0 0 = error "GCD(0,0) is undefined"
euclid a 0 = a
euclid a b =  euclid b (a `emod` b)

-- Returns the least common multiple of a and b, using the definition of lcm
-- given in class (in terms of the gcd). DO NOT use the built-in `lcm` function.
lCM :: Integer -> Integer -> Integer
lCM 0 0 = error "LCM(0,0) is undefined"
lCM a b = a*b `ediv` (euclid a b)

-- extGCD a b
-- Returns the GCD of a and b, along with x and y such that
--   GCD(a,b) = ax + by
-- calculated via the recursive extended Euclidean algorithm presented in
-- class.
extGCD :: Integer -> Integer -> (Integer,Integer,Integer)
extGCD 0 0 = error "extGCD(0,0) is undefined"
extGCD a 0 = (1,0,a)     -- Base case
extGCD a b = let (q,r) = a `eDivMod` b           -- q and r of a/b
               (c,x,y) = extGCD b r          -- Recursive call
         in  (x,c-q*x, y) -- Recursive results

-- coprime a b
-- Returns True if a and b are coprime (have no common factors)
coprime :: Integer -> Integer -> Bool
coprime 0 0 = error "coprime(0,0) is undefined"
coprime a b = (euclid a b) == 1

-- minv a n
-- Returns the modular inverse of a mod n. Assumes that a and n are coprime.
minv :: Integer -> Integer -> Integer
minv a n =

最佳答案

您可以使用extGCD函数来实现。

如果a和m是互质的，则使用extGCD函数来解决:

a*x + m*y = gcd a m = 1

这意味着a * x = 1 mod m，即a和x是乘法逆m。

关于haskell - Haskell中的模逆，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33326716/