P42 - 模乘逆元

2026-09-07 00:00    #Haskell   #99题   #数论  

P42 - 模乘逆元

Determine the modular multiplicative inverse

官方模块：Problems.P42　核心函数：multiplicativeInverse

← P41 哥德巴赫数对列表 | P43 高斯整数整除 →

题目描述

求模 nn 下 aa 的乘法逆元 xx，满足 ax≡1(modn)ax \equiv 1 \pmod n。逆元存在当且仅当 gcd⁡(a,n)=1\gcd(a, n) = 1。

函数签名

1multiplicativeInverse :: Integral a => a -> a -> Maybe a

实现

方法一：扩展欧几里得算法

 1multiplicativeInverse :: Integral a => a -> a -> Maybe a
 2multiplicativeInverse a n
 3  | n <= 1    = Nothing
 4  | g == 1    = Just (x `mod` n)
 5  | otherwise = Nothing
 6  where
 7    (g, x, _) = extendedGCD (a `mod` n) n
 8
 9extendedGCD :: Integral a => a -> a -> (a, a, a)
10extendedGCD 0 b = (abs b, 0, signum b)
11extendedGCD a b =
12  let (g, x, y) = extendedGCD (b `mod` a) a
13  in (g, y - (b `div` a) * x, x)

扩展欧几里得算法同时求出 g,s,tg,s,t，满足 as+nt=gas+nt=g。当 g=1g=1 时，ss 就是逆元。

方法二：迭代版扩展欧几里得

 1multiplicativeInverse :: Integral a => a -> a -> Maybe a
 2multiplicativeInverse a n
 3  | n <= 1    = Nothing
 4  | g == 1    = Just (x `mod` n)
 5  | otherwise = Nothing
 6  where
 7    (g, x, _) = iter 0 1 n (a `mod` n)
 8    iter s0 s1 r0 r1
 9      | r1 == 0   = (r0, s0, (r0 - s0 * (a `mod` n)) `div` n)
10      | otherwise = let q = r0 `div` r1
11                    in iter s1 (s0 - q * s1) r1 (r0 - q * r1)

非递归版本，避免在大数上递归栈溢出。

方法三：朴素枚举（仅用于验证）

1multiplicativeInverse :: Integral a => a -> a -> Maybe a
2multiplicativeInverse a n
3  | n <= 1    = Nothing
4  | otherwise = listToMaybe [x | x <- [1..n-1], (a * x) `mod` n == 1]

从定义出发，枚举 1..n−11..n-1 检查乘积模 n 是否为 1。小 n 可用，大 n 极慢。

方法对比

方法复杂度特点
递归扩展 GCDO(log n)标准做法，推荐
迭代扩展 GCDO(log n)无栈溢出风险
朴素枚举O(n)教学验证用

测试

1>>> multiplicativeInverse 3 7
2Just 5      -- 因为 3 * 5 = 15 ≡ 1 (mod 7)
3>>> multiplicativeInverse 2 6
4Nothing     -- gcd(2,6) = 2 ≠ 1
5>>> multiplicativeInverse 1 2
6Just 1

参考