模数两两互素时
1
2
3
4
5
6
7
8
9
10
11
|
from Crypto.Util.number import inverse
from functools import reduce
def crt(a, m):
'''Return a solution to a Chinese Remainder Theorem problem.
'''
M = reduce(lambda x, y: x*y, m)
Mi = [M//i for i in m]
t = [inverse(Mi[i], m[i]) for i in range(len(m))]
x = sum([a[i]*t[i]*Mi[i] for i in range(len(m))])
return x % M
|
不满足模数两两互素时
这种情况有最小解 x 满足条件，很多博客也讲的很详细，但是没找到 Python 写的…
与 m 互素时一样，m 不互素时显然也会有无限个解 X = k * M + x ，但是 m 之间不互素时，在模 M 的意义下也可能会有多个解。
x 为最小解，m1 , m2 , … , mn 的最小公倍数为 L ，X < M ，易知 X = x + k * L ，枚举 k 就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
from Crypto.Util.number import GCD, inverse
from functools import reduce
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def crt_minial(a, m):
'''Return the minial solution to a Chinese Remainder Theorem problem.
'''
assert len(a) == len(m), f"length of {a} is not equal to {b}"
m1, a1, lcm = m[0], a[0], m[0]
for i in range(1, len(m)):
c = a[i]-a1
g, k, _ = egcd(m1, m[i])
lcm = lcm*m[i]//GCD(lcm, m[i])
assert c % g == 0, 'No Answer!'
t = m[i]//g
a1 += m1*(((c//g*k) % t + t) % t)
m1 = m[i]//g*m1
return a1
|