中国剩余定理简析

Chinese Remainder Theorem

同余式

先简单介绍一下一次同余式

为常见的一次同余式式子,以下式子均满足 $(a, m)=1$

当常数项$b=1$时,即

此时同余式的解为$x=a^{-1}\mathrm{mod}m$

当$b$时任意整数时,即

此时同余式有解的充分必要条件是$(a,m)|b$,此时同余式的解为

可以发现,其有多个可能存在的解

1
2
3
4
5
6
7
# 线性同余方程求解
def linearCongruenceSolver(a, b, m):
g = gcd(a, m)
if b % g != 0:
return None
n = invert(a / g, m / g)
return [int((b * n + m * t) / g % m) for t in range(g)]

中国剩余定理

中国剩余定理,也称为孙子剩余定理,其最早见于《孙子算经》的“物不知数”题,原文如下

有物不知何数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?

翻译成数学式子也就是

要求$x$,明朝数学家总结出了《孙子歌》

三人同行七十稀,五树梅花二十一。七子团圆正半月,减百零五便得知。

翻译成数学式子也就是

简单解释一下这个式子,$70=2\times5\times7$,$5\times7$是不会对$5$和$7$产生余数的,至于多乘的$2$,其实是$35^{-1}\mathrm{mod}\ 3$,由于$1\equiv70 \mathrm{mod}\ 3$,所以$70$最后还要乘2;同理$3\times(21^{-1}\mathrm{mod}\ 5\times3\times7)$;同理$2\times(15^{-1}\mathrm{mod}\ 7)\times3\times5$,最后减掉$3\times5\times7$的倍数

现将

  • 2,3,2分别看作$b_1,b_2,b_3$
  • 3,5,7分别看作$m_1,m_2,m_3$
  • $5\times7,3\times7,3\times5$分别看作$M_1,M_2,M_3$
  • $2,1,1$分别看作$M_1^{-1},M_2^{-1},M_3^{-1}$
  • $105$看作$m_1\cdot m_2\cdot m_3$

则最后的式子即为

其中$M_i^{-1}\cdot M_i\equiv1(\mathrm{mod}\ m_i)$


这就引出了中国剩余定理,设$m_1,\cdots,m_k$是$k$个两两互素的正整数,则对任意整数$b_1,\cdots,b_k$,同余方程组

一定有解,且解是唯一的,其为

其中

1
2
3
4
5
6
7
8
9
10
11
12
# 中国剩余定理
# data = [(b1,m1),···,(bk,mk)]
def CRT(data):
x = 0
m = 1
for i in data:
m = m * i[1]
for bi, mi in data:
Mi = m / mi
mr = invert(Mi, mi)
x = x + bi * (mr * Mi)
return x % m

特殊的,当方程组只有两个式子时,即

其中$m_1$与$m_2$互质,其解为

其中$s\cdot q+t\cdot p=1$


广义上的中国剩余定理是不止一个解的,要求出全部解可以用下面的方法做

中国剩余定理的迭代证明,利用求解一次同余式的方法求解

先计算第一个式子

接着把这个等式代入第二个式子

计算得

这里可以利用求解同余式的公式求出$k_1$所有取值,接着回代$x=b_1+k_1\cdot m_1$就得到了$x(\mathrm{mod}\ m_1\cdot m_2)$的所有取值了

一直计算到最后一个式子,就得到了$x(\mathrm{mod}、 m_1\cdots m_2)$的所有解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 中国剩余定理
# data = [(b1,m1),···,(bk,mk)]
# 求出全部解
def CRT_ALL(data):
ans = [
data[0][0],
]
m = data[0][1]
for bi, mi in data[1:]:
new_ans = list()
# print ans
for a in ans:
ks = linearCongruenceSolver(m, bi - a, mi)
if not ks:
continue
for k in ks:
new_ans.append(a + k * m)
ans = new_ans
m = m * mi
return ans, m

拓展中国剩余定理

中国剩余定理只适用于模数互素的情况,当模数不互素时,就引出了拓展中国剩余定理

其中$m_1,\cdots,m_k$不一定两两互素,这样传统的公式求解就没有办法了,但是还是可以利用迭代形式,逐步求解,以两个式子为例

由第一个式子化成$x=b_1+k_1\cdot m_1$,代入到第二个式子中,得到

令$d=\mathrm{gcd}(m_1,m_2)$,左右同除$d$,得到

线性同余求解得到$k_1$,回代得到$x(\mathrm{mod}\ m_1\cdot m_2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
# 拓展中国剩余定理
# data = [(b1,m1),···,(bk,mk)]
def extCRT(data):
m = data[0][1]
x = data[0][0]
for bi, mi in data[1:]:
d = gcd(m, mi)
b = bi - x
k = b / d * invert(m / d, mi / d)
x += k * m
m = m * mi / d
x %= m
return x % m, m

可以发现,此处求$k$与上面求$k$用的是不同的方法,上面用线性同余解出所有$k$的取值,这里直接求逆得到,只有一个值

参考

  1. 《信息安全数学基础》第二版
  2. Soreat_u ‘s Blog
  3. Chinese remainder theorem - Wikipedia

  cryptorsa

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×