作者：aaron67
时间：2020年10月11日 00:50:38
来源：https://blog.csdn.net/aaron67/article/details/109006977
整数 a 除以整数 b，若得到的余数是 r，则记作
a mod b = r
例如
5 mod 3 = 2
− 5 mod 3 = 1
模运算的部分性质如下：
( a + b ) mod c = ( ( a mod c ) + ( b mod c ) ) mod c
( a ⋅ b ) mod c = ( ( a mod c ) ⋅ ( b mod c ) ) mod c
a^b mod c = ( a mod c )^b mod c
如果你对模运算还不太熟悉，推荐先阅读 Khan Academy 的入门课程。
同余
两个整数 a、b，若它们除以正整数 n 所得的余数相等，即 a mod n = b mod n，则称 a 和 b 对于模 n 同余，记作
a ≡ b ( mod n )
读作 a 同余于 b 模 n，或 a 和 b 关于模 n 同余。例如
2 ≡ 8 ( mod 6 )
当 k 为整数（k ∈ Z）时，同余关系有如下性质。
a ≡ b ( mod n ) ⇒ ak ≡ bk ( mod n )
当 k、n 互质时，有
ak ≡ bk ( mod n ) ⇒ a ≡ b ( mod n )
模逆元
参考倒数（xy = 1）的定义，对整数 a 和 b，若
ab ≡ 1 ( mod n )
则称 a 和 b 关于模 n 互为模倒数，也叫模反元素或模逆元（modular multiplicative inverse），还可以记作
b ≡ 1/a ( mod n ) 或 b ≡ a^(−1) ( mod n )
类似于实数除法，在模 n 下的除法可以用和对应模逆元的乘法来表达。”分数取模”，等价于求分母的模逆元。
当 a、b 关于模 n 互为模逆元时，b mod n = 1/a mod n
c/a mod n = ( c ⋅ 1/a ) mod n = ( ( c mod n ) ⋅ ( 1/a mod n ) ) mod n = ( ( c mod n ) ⋅ ( b mod n ) ) mod n = ( c ⋅ b ) mod n
例如
20/3 mod 7 = ( ( 20 mod 7 ) ⋅ ( 1/3 mod 7 ) ) mod 7 = ( 6 × 5 ) mod 7 = 2
根据定义，求 a 关于模 n 的模逆元，若 b 是解，k ∈ Z，则 b + k n也都是解，且最小的非负整数解小于 n，例如
2 × 3 ≡ 1 ( mod 5 )
2 × 8 ≡ 1 ( mod 5 )
即 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 满足下式。
ax + ny = g
其中，g 是 a 和 n 的最大公约数。上式两边同模 n，有
( ax + ny ) mod n = ( ax mod n ) + ( ny mod n ) = ax mod n = g mod n
即
ax ≡ g ( mod n )
当 a、n 互质时，g = 1，此时 x 就是解。当 g ≠ 1 时， a 关于模 n 的模逆元不存在。
两数互质的充分必要条件是两数的最大公约数为 1。也就是说，a 关于模 n 的模逆元存在的充分必要条件是 a 和 n 互质。
完整代码
modular_inverse.py