Haskell 中的模逆

Question

到目前为止我已经解决了 euclid、lCM、extGCD 和 coprime。我将如何求解模逆（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 = 

Answer 1

您可以使用您的

extGCD

功能来做到这一点。

如果 a 和 m 互质，则使用您的

extGCD

函数来求解：

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

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

Answer 2

首先

a

和

n

必须互质，否则逆元不存在。这是因为求

a

模

n

的倒数与求解同余相同：

ax = 1 mod n

。

线性同余

ax = b mod n

仅当

gcd(a, n) | b

时才有解。但在这种情况下

gcd(a, n) | 1

意味着

gcd(a, n) = 1

。

所以现在，要找到逆元，您可以使用 Bezout 恒等式，即存在

x

和

y

，使得：

gcd(a, n) = a*x + n*y

。您已经在

extGCD

函数中找到了此类值，因此您可以将

minv

实现为：

minv a n =  a*x + n*y
    (x, y, _) = extGCD a n

最好编写一个类型为

Integer -> Integer -> Maybe Integer

的函数，如果

Nothing

与

extGCD

不同，则返回

1

：

minv a n =
  | g == 1    = Just $ a*x + n*y
  | otherwise = Nothing
  where
    (x, y, g) = extGCD a n

---

顺便说一句：Z_n中的可逆元素子群正是与

a

互质的<

n

的集合。当

n

为素数时，该子群与没有

n

的 Z_n 重合，在这种情况下，Z

n

是一个域。

Answer 3

0

和

a

，都存在整数

b

和

x

，使得

y

（参见

Bézout 恒等式

）。具体来说，当 ax + by = gcd(a, b) 和

a

互质时，这简化为

b

。利用

扩展欧几里得算法

，我们迭代ax + by = ax = gcd(a, b) = 1 mod b形式的表达式，其中我们将

(b mod a)x + ay = gcd(a, b)

重新定义为

a

，将

a' = b mod a

重新定义为

b

。最终，我们到达最终状态，

b' = a

。为了在 Haskell 中实现这一点，我们定义了一个函数

(a, b, x, y) = (0, gcd(a, b), 0, 1)

，它将

extgcd

和

a

作为输入并返回一个元组

b

。为了理解每次迭代之间的关系，我们比较方程

(x, y)

和

ax + by = gcd(a, b)

。从这个比较中，我们得出

(b mod a)x + ay = gcd(a, b)

和

x = y' - floor(b/a) * x'

。这引导我们进行以下 Haskell 实现：y = x'