区块链中的数学 - 中国剩余定理

  • blocksight
  • 更新于 2020-06-23 17:29
  • 阅读 3148

本节主要介绍了中国剩余定理,也是数论中重要的定理之一。其中过程用到了模运算的乘法规则逆元的求法,可见这一系列知识点是环环相扣的,层层递进的。

写在前面

上一节介绍了欧拉定理和欧拉函数并加以证明。其中欧拉函数是积性函数的证明用到了中国剩余定理【欧拉函数性质4】,没印象的可以再看看, 当时没有展开,本节详细说明下。

中国剩余定理

中国剩余定理(Chinese remainder theorem(CRT)),是中国古代求解一次同余式组的方法,是数论中一个重要定理。

最早于中国南北朝时期(公元5世纪)的数学著作《孙子算经》提出,故又称孙子定理。 记载原文如下:

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

意思是,一个整数除以3余2,除以5余3,除以7余2,求这个整数.

类似的还有韩信点兵的故事。

公式推导

上述问题可以转化为求一元同余方程组的问题:

$ \begin{cases} x=a_1\ mod\ m_1 \ x=a_2\ mod\ m_2 \ ... \ x=a_n\ mod\ m_n \end{cases} $

求出x的值。

假设整数$m_1,m_2, ... ,m_n$两两互质,则对任意的整数:$a_1,a_2, ... a_n,$,该方程组有解,并且通解可以用如下方式得到:

$M=m_1 \times m_2 \times ... \times mn =\prod{i=1}^n m_i $

是整数$m_1,m_2, ... ,m_n$的乘积,并设$M_i=M/m_i$, 是除了$m_i$以外的n- 1个整数的乘,i在[1,n]之间。

设$t_i$为$M_i$模的逆元,则$t_iM_i \equiv 1 mod (m_i)$ , 方程组的通解形式为

$x=a_1t_1M_1+a_2t_2M_2+...+a_nt_nMn+kM=kM+ \sum{i=1}^n a_it_iM_i,k \in \mathbb{Z}$

K是整数,在模M的意义下,方程组只有一个解:

$x=(\sum_{i=1}^n a_it_iM_i)modM$

为什么这样求出来的解就是正确的呢?下面我们来证明。

解法证明

证明 :

(1)从假设可知,对任何$i \in {1,2,...,n}$ ,因为$m_1,m_2...m_n$两两互质, 所以$m_i,M_i$互质。所以必然存在逆元$t_i,t_iM_i \equiv 1(mod\ m_i)$ 可得下式成立,

$a_it_iM_i \equiv a_i mod (m_i)$

对于任意$\forall_j \in {1,2,...,n}(j\neq i)$

$a_it_iM_i \equiv 0 (mod\ m_j)$

所以:$\forall_i \in {1,2,...,n}$

$x=a_it_iMi+\sum{j\neq i}a_jt_jM_j \equiv ai+\sum{j\neq i}0(mod\ m_j)\equiv a_i(modm_i)$

这说明x就是方程组的解。

(2)如果$ x_1,x_2$都是方程组的解,那么:

$x_1-x_2 \equiv 0(mod\ m_i)$

而 $m_1,m_2,...,mn$两两互质,说明 $M =\prod{i=1}^n m_i $整除$x_1-x_2$, 所以方程组的任何两个解之间必然相差M的整数倍,

所以方程组所有的解的集合是:

$\lbrace Km+\sum_{i=1}^na_it_iM_i \rbrace $

实例演练

以上求解思路从下面两个结论出发:

  1. 两个数相加,如果一个加数能被a整除,另一个整数不能被a整除,那么它们的和就不能被整数a整除,和的余数取决于不能不能被a整除的加数

  2. 两数和不能整除a,若除数扩大(或缩小)n倍,而被除数不变,则其商和余数也同时扩大(或缩小)相同的倍数(余数必小于除数)

这两个结论显而易见,下面来实例解析下中国剩余定理求解过程。

通过开头提出的例子计算来帮助理解。

例中可得,$ a_1= 2, a_2= 3, a_3= 2, m_1= 3, m_2= 5, m_3= 7$

方程组为:

$ \begin{cases} x=2\ mod\ 3 \ x=3\ mod\ 5 \ x=2\ mod\ 7 \end{cases} $

<1> 计算最小公倍数 M = 3 57= 105

<2> 计算$M_1$=105/3 = 35, $M_2$= 105/5 = 21, $M_3$= 105/7 = 15

分别求出

$t_1$= 2, $t_2$=1, $t_3$=1 [注:求解逆元的方法参见]

解为:

$x = a_1t_1M_1+a_2t_2M_2 + a_3t_3M_3(mod\ M_i) = 140 + 63 + 30 (mod\ 105) = 23$

观察解 $x = a_1t_1M_1+a_2t_2M_2 + a_3t_3M_3(mod\ M_i )$ 结构,

其中$M_2,M_3$均能整除$m_1$, 后二者之和模 $m_1$为零,

根据结论1,x值取决于第一项$a_1t_1M_1$

由于$t_1M_1 \equiv 1mod(m_1)$ ,

根据结论2,将除数扩大$a_1$倍,余数也扩大$a_1$倍,即 $a_1t_1M_1 \equiv a_1mod(m_1)$(其实也是模运算的乘法规则,参见此历史文章)。

以上分析从模($m_1$)的角度满足方程组第一个等式。同理, 从$m_2$角度类似分析,x满足方程组第二个等式,依次类推满足所有等式。

小结

本节主要介绍了中国剩余定理,也是数论中重要的定理之一。其中过程用到了模运算的乘法规则逆元的求法,可见这一系列知识点是环环相扣的,层层递进的。

这两节文章又是为了更好理解RSA加解密原理章节而展开,前后联系,相互呼应以形成知识学习的闭环。

本来打算本节包含欧拉函数性质4的证明。但是篇幅不短了, 下次再说吧。

好了,有了中国剩余定理的基础,下一节讲欧拉函数性质4的推导

欢迎关注公众号:blocksight

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。