(4条消息) 什么是模逆元
https://aaron67.cc/2020/05/30/modular-multiplicative-inverse/
整数 a 除以整数 b,若得到的余数是 r,则记作
a m o d b = r a \bmod{b} = r amodb=r
例如
5 m o d 3 = 2 5 \bmod{3} = 2 5mod3=2
− 5 m o d 3 = 1 -5 \bmod{3} = 1 −5mod3=1
模运算的部分性质如下:
( a + b ) m o d c = ( ( a m o d c ) + ( b m o d c ) ) m o d c (a + b) \bmod{c} = ((a \bmod{c}) + (b \bmod{c})) \bmod{c} (a+b)modc=((amodc)+(bmodc))modc
( a ⋅ b ) m o d c = ( ( a m o d c ) ⋅ ( b m o d c ) ) m o d c (a \cdot b) \bmod{c} = ((a \bmod{c}) \cdot (b \bmod{c})) \bmod{c} (a⋅b)modc=((amodc)⋅(bmodc))modc
a b m o d c = ( a m o d c ) b m o d c a^{b} \bmod{c} = (a \bmod{c})^{b} \bmod{c} abmodc=(amodc)bmodc
如果你对模运算还不太熟悉,推荐先阅读 Khan Academy 的入门课程。
同余
两个整数 a、b,若它们除以正整数 n 所得的余数相等,即 a m o d n = b m o d n a \bmod{n} = b \bmod{n} amodn=bmodn,则称 a 和 b 对于模 n 同余,记作
a ≡ b ( m o d n ) a\equiv b \pmod{n} a≡b(modn)
读作 a 同余于 b 模 n,或 a 和 b 关于模 n 同余。例如
2 ≡ 8 ( m o d 6 ) 2\equiv 8 \pmod{6} 2≡8(mod6)
当 k 为整数( k ∈ Z k \in \mathbb{Z} k∈Z)时,同余关系有如下性质。
a ≡ b ( m o d n ) ⇒ a k ≡ b k ( m o d n ) a\equiv b \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ ak\equiv bk \pmod{n} a≡b(modn) ⇒ ak≡bk(modn)
当 k、n 互质时,有
a k ≡ b k ( m o d n ) ⇒ a ≡ b ( m o d n ) ak\equiv bk \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ a\equiv b \pmod{n} ak≡bk(modn) ⇒ a≡b(modn)
模逆元
参考倒数( x y = 1 xy = 1 xy=1)的定义,对整数 a 和 b,若
a b ≡ 1 ( m o d n ) ab \equiv 1 \pmod{n} ab≡1(modn)
则称 a 和 b 关于模 n 互为模倒数,也叫模反元素或模逆元(modular multiplicative inverse),还可以记作
b ≡ 1 a ( m o d n ) 或 b ≡ a − 1 ( m o d n ) b \equiv \frac{1}{a} \pmod{n}\ \ \ \ 或\ \ \ \ b \equiv a^{-1} \pmod{n} b≡a1(modn) 或 b≡a−1(modn)
类似于实数除法,在模 n 下的除法可以用和对应模逆元的乘法来表达。”分数取模”,等价于求分母的模逆元。
当 a、b 关于模 n 互为模逆元时, b m o d n = 1 a m o d n b \bmod{n} = \frac{1}{a} \bmod{n} bmodn=a1modn
c a m o d n = ( c ⋅ 1 a ) m o d n = ( ( c m o d n ) ⋅ ( 1 a m o d n ) ) m o d n = ( ( c m o d n ) ⋅ ( b m o d n ) ) m o d n = ( c ⋅ b ) m o d n \frac{c}{a} \bmod{n} = (c \cdot \frac{1}{a}) \bmod{n} = ((c \bmod{n}) \cdot (\frac{1}{a} \bmod{n})) \bmod{n} = ((c \bmod{n}) \cdot (b \bmod{n})) \bmod{n} = (c \cdot b) \bmod{n} acmodn=(c⋅a1)modn=((cmodn)⋅(a1modn))modn=((cmodn)⋅(bmodn))modn=(c⋅b)modn
例如
20 3 m o d 7 = ( ( 20 m o d 7 ) ⋅ ( 1 3 m o d 7 ) ) m o d 7 = ( 6 × 5 ) m o d 7 = 2 \frac{20}{3} \bmod{7} = ((20 \bmod{7}) \cdot (\frac{1}{3} \bmod{7})) \bmod{7} = (6 \times 5) \bmod{7} = 2 320mod7=((20mod7)⋅(31mod7))mod7=(6×5)mod7=2
根据定义,求 a 关于模 n 的模逆元,若 b 是解, k ∈ Z k \in \mathbb{Z} k∈Z,则 b + k n b + kn b+kn 也都是解,且最小的非负整数解小于 n,例如
2 × 3 ≡ 1 ( m o d 5 ) 2 \times 3 \equiv 1 \pmod{5} 2×3≡1(mod5)
2 × 8 ≡ 1 ( m o d 5 ) 2 \times 8 \equiv 1 \pmod{5} 2×8≡1(mod5)
即 3 和 8 都是 2 关于模 5 的模逆元,其中 3 是最小的非负整数解。所以求模逆元可以通过遍历 0 ~ n 来确定。
# find modular multiplicative inverse of 'a' under modulo 'n'
def modular_multiplicative_inverse(a: int, n: int) -> int:
for i in range(n):
if (a * i) % n == 1:
return i
raise ValueError('{} has no multiplicative inverse under modulo {}'.format(a, n))
但这种方法在 n 取值很大时效率不高。你可以参考文章 Modular multiplicative inverse,使用扩展欧几里得算法或费马小定理改进。
def extended_euclid_gcd(a: int, b: int) -> list:
"""
Returns [gcd(a, b), x, y] where ax + by = gcd(a, b)
"""
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
return [old_r, old_s, old_t]
def modular_multiplicative_inverse(a: int, n: int) -> int:
"""
Assumes that a and n are co-prime, returns modular multiplicative inverse of a under n
"""
# Find gcd using Extended Euclid's Algorithm
gcd, x, y = extended_euclid_gcd(a, n)
# In case x is negative, we handle it by adding extra n
# Because we know that modular multiplicative inverse of a in range n lies in the range [0, n-1]
if x < 0:
x += n
return x
已知整数 a、n,使用扩展欧几里得算法可以求出整数 x、y、g 满足下式。
a x + n y = g ax + ny = g ax+ny=g
其中,g 是 a 和 n 的最大公约数。上式两边同模 n,有
( a x + n y ) m o d n = ( a x m o d n ) + ( n y m o d n ) = a x m o d n = g m o d n (ax + ny) \bmod{n} = (ax \bmod{n}) + (ny \bmod{n}) = ax \bmod{n} = g \bmod{n} (ax+ny)modn=(axmodn)+(nymodn)=axmodn=gmodn
即
a x ≡ g ( m o d n ) ax \equiv g \pmod{n} ax≡g(modn)
当 a、n 互质时, g = 1 g = 1 g=1,此时 x 就是解。当 g ≠ 1 g \neq 1 g=1 时, a 关于模 n 的模逆元不存在。
两数互质的充分必要条件是两数的最大公约数为 1。也就是说,a 关于模 n 的模逆元存在的充分必要条件是 a 和 n 互质。