LUOYANG NORMAL UNIVERSITY
2012届 本科毕业论文
中国剩余定理的归纳及其应用
院（系）名称 专 业 名 称 学
生
姓
名
数学科学学院 数学与应用数学
任晓燕 080414001 王众杰 讲师
2012.5
学 号 指
导
教
师
完 成 时 间
中国剩余定理的归纳及其应用
任晓燕
数学科学学院 数学与应用数学 学号：080414001
指导老师：王众杰
摘要：中国剩余定理又称为孙子定理, 它的数学思想在近代数学中占有非常重要的地位. 本文归纳了中国剩余定理并给出证明, 并给出相关的经典例, 并在此基础上对其在同余式组, 多项式定理、赋值定理、密码学以及生活中的应用进行初步的讨论和分析.
关键词：中国剩余定理； 同余式组； 多项式； 密码学 引言
中国古代著名数学著作记载, " 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何? " 此问题为中国剩余定理的原型. 解法和答案用算式表示为70×2+21×3+15×2-105×2=23.即得到适合题意的最小整数是23. " 物不知其数" 开创了一次同余式研究的先河, 但真正从完整的计算程序和理论上解决这个问题的事南宋时期的数学家秦九韶, 秦九韶在他的《数书九章》中提出了一个数学方法" 大衍求一术" .
1876年, 德国人马蒂生首先指出这一解法与19世纪高斯《算术探究》中关于一次同余式组的解法完全一致. 从此, 中国古代数学这一创造受到世界学者瞩目, 并在西方数学史著中正式称为" 中国剩余定理" .
. 1
中国剩余定理及其证明
设n 2, m 1, m 2,... m n 两两互素的正整数,
令M =m 1m 2... m n =m 1M 1=m 2M 2=... m n M n , 则同余式组
⎧x =c 1(m od m 1)⎪
⎪x =c 2(m od m 2)
⎨
⎪........................ ⎪x =c (m od m )
n n ⎩
有正整数解x =M 1a 1c 1+M 2a 2c 2+... M n a n c n (mod M )且解唯一；其中a i 是满足
M i a i ≡1(mod m i ), (i =1, 2,... n )的一个整数.
下面我们先给出裴蜀恒等式和一个性质, 然后证明中国剩余定理.
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a 、b 和它们的最大公约数d ，关于未知数x 和y 的线性丢番图方程ax +by =d （称为裴蜀等式）：
裴蜀恒等式 如果两个数的最大公约数是d , 则必定存在两个整数x , y 使得等式ax +by =d 成立. .
性质 同余式组a ≡b (mod m j )j =1, 2,... n 同时成立的充要条件是a ≡b (m od ⎡⎣m 1, m 2,... m n ⎤⎦).
证明 先证存在性：因为m 1, m 2,... m 两两互素, M k =
M m k
,
故(M k , m k )=1, k =1, 2,... n , 由裴蜀恒等式可知一定存在整数αk , βk 使得
M k αk +βk m k =1, 即M k αk =-βk m k +1, 因此必定存在αk , 使
M k αk ≡1(mod m k ), k =1, 2,... n . 又因当λ≠k 时, 恒有m λM k ,
所以M k a k ≡1(mod m λ)(λ≠k ). 若令R =x =M 1a 1c 1+M 2a 2c 2+... M n a n c n , 则有
⎧R =M 1a 1c 1(m od m 1)⎪
⎪R =M 2a 2c 2(m od m 2)
⎨
⎪................................ ⎪R =M a c (m od m )
n n n n ⎩
又m k M , 故M ≡0(mod m k ), 从而x =R +M t ≡R ≡c k (mod m k ), k =1, 2,... n . 因此x ≡R (mod M ), 即R =x =M 1a 1c 1+M 2a 2c 2+... M n a n c n (m od M )为同余式组之解.
唯一性：该同余式组还有一组解y , 则有x ≡y (mod m k ), , k =1, 2,..., n 由于m 1, m 2,..., m n 两两互素, 因此M =[m 1, m 2,..., m n ]=m 1m 2... m , 利用所给性质可知
x ≡y (mod M ), 证毕.
2 中国剩余定理的推广
2.1 一元多项式环中的中国剩余定理
2.1.1 定理 设m 1(x ), m 2(x ),... 是两两既约的多项式, 那么对任意的多项式
r 1(x ), r 2(x ),... , ∃g (x )∈R [X ], 使得g (x )≡r j (x )(mod m j (x )), j =1, 2,... , 记此式为
(1)式, 且有：
g (x )≡M 1(x )M 1
-1
(x )r 1(x )+M 2(x )M 2-1(x )r 2(x )+... +M k (x )M k -1(x )r k (x )(mod m (x ))
这里g (x )在mod m (x )下是唯一的, 其中：m (x )=m 1(x )m 2(x )... , 且有下式：
m (x )=m j (x )M
j
(x ),
j =1, 2,... , 以及M
-1j (x )是M j (x )对模M j (x )的逆.
2.1.2 定理的应用
在上述定理中, 取M i (x )=x -a i , a i ≠a j , i ≠j 时, 令r i (x )=r , 则有：
r i (x )=r i =g (a ).
则可得到插值公式
M 1(x )M 1
-1
(x )r 1(x )+... +M k (x )M k
-1
⎛k ⎫
(x )r k (x )= ∏(x -a i )⎪q (x )
⎝i =1⎭
其中
M i (x )=
∏(x -a ), M (x )=∏(x -a ), 令为：h (x )(x -a k )+l 所以有：
j
k
j
j =1, j ≠i
j =1
k k -1
1l
M k (x )-
h (x )l
1l
(x -a k )=1
k -1
则M k (x )=. M k (a k )=∏(a k -a i )=h (a k )(a k -a k )+l =l .
-1
i =1
则=
l
11
k -1
M k
-a i )
-1
(x ), 同理求得M
-1j (x ),
j =1, 2,... , 代入上述插值公式, 即得
∏(a
i =1
k
到拉格朗日插值公式.
2.2 中国剩余定理在非标准数论中的推广 2.2.1 第一广义中国剩余定理
设(p 1, p 2... )是一列标准素数, (r 1, r 2... )是自然数集的任一无穷子列, 将它作为一组余数, 则Γ(x )={(∃q i p i )(x ≡q i p i +r i )|i =1, 2,... }与THN 和谐.
例 证明 可数THN 的模型的总数为2ω.
证明 由第一广义中国剩余定理知每个Γ(x )都是THN 和谐的, 因而可以扩充为一个极大的和谐式子集, 这样一个极大的和谐式子集是某个非标准数所满足的型. 每一序列(r 1, r 2,... )(0≤r i ≤p i )都可以对应着一个型. 不同的序列对应的型也不同. 因而, 数论中型的个数必然必这些无穷数列的个数多, 计算这样的无穷序列的个数可以得出型的个数的上界. 实际上, 易见这个数目为
∏
i
p i =2⨯3⨯⨯5⨯7, 由集合论可知.
(i )∏
i
p i ==2
∏i
i
(ii )ωω
i
ω
(iii )∏i =2ω
综上可知∏
i
p i =2. 另一方面, 作为可数理论, THN 之多有2ω个型. 因此
ω
THN 共有2ω个型. 由每个型出发, 利用它与THN 的和谐性可以有一个可数模型
实现它. 我们知道一个可数模型之多能实现可数多个型, 所以互不相同构的可数模型的总数仍为2ω. 2.2.2 第二广义中国剩余定理
设ψ是一个ω-饱和THN 模型. (p 1, p 2... )是一列标准或非标准素数(r 1, r 2... )是一列满足0≤r i
⎧x ≡r 1(m od m 1), ⎪⎪...
=1(i ≠j ), 那么对所有, 同余式⎨
⎪x ≡r n (m od m n ), ⎪... ⎩
设r 1..., r n ..., ∈N , 且(m i , m j )
有解.
例 证明 存在无限组孪生拟素数(p , p +2).
证明 首先构造一组孪生拟素数：
我们规定余数列为r 1=1, r 2=2, r i =1(i =3, 4,... ), 即(1, 2,1,1,... ), 由它得到式子集Γ(x )={(∃q i )(x ≡q i p i +r i )i =1, 2,... }与T 和谐, 在ℜ中又非标准数p 实现
Γ(x ),
显然它是一个拟素数, 而且余数列的特殊取值p +2也是拟素数, 即
=0, i =1, 2,..., 设它所对应
(p , p +2)使一组孪生拟素数. 另一方面, 如果余数列取r i
的非标准数为q .
那么令p 1=p +q , p 2=p +2⨯q , p 3=p +3⨯q ,..., 就得到了无限组孪生拟素数
(p , p +2), (p 1, p 1), (p 2, p 2+2)(p 3, p 3+2),...
3 中国剩余定理的另解 3.1 同余扩整法
设所求的整数为N , 引言中题意是：N 被3除余2被5除余3被7除余2求N 的最小值. 我们不妨从第三个条件切入. N 被7除余2就可以说和7对于模
是同余的那么2加上7的整数倍后所得的数与N 对于模7仍同余所以用2依次加7的1倍2倍3倍后经检验2+3=23既符合被3除余2又符合被5除余3
⎛7⎫
2+79+716+7 ⎪
916233. 故N 的最小值是23. 于是可写成：2(7) ⎪
5⎪⎝⎭
3.2 列方程组法
设被所得的整数商分别为依题意3x +2=5y +3=7z +2=N (1)
⎧⎪3x -5y =1
于是有⎨
⎪⎩5y -7z =-1
(2)(3)
t ⎧⎪x =2+5t ⎪⎩y =1+3
解方程(2)得通解 ⎨
(4)
(t ∈Z )
(5)
将(5)式代入(3)得7z -15t =6.
⎧⎪t =-1-7t 1此不定方程的通解为⎨
⎪⎩z =3+15t 1
(6)
(t 1∈z )
(7)
将(6)代入(4), (5)同时考虑式(7)得原方程组的全部整数解为
⎧x =7+35t 1⎪
⎨y =4+21t 1⎪
⎩z =3+15t 1
(8)(9).
(t 1∈Z )(10)
上式三式(8), (9), (10)中任意一个代入(1)得" 物不知其数" 问题的通解
N =23+105t 1. 当t 1=0时N =23是最小的正整数解.
4 剩余定理的几个应用 4.1 在同余式组中的应用
例 " 韩信点兵" 问题：有兵一堆, 若列成五行纵列则末行一人; 成刘航纵队, 则末行五人；成七行纵队, 则末行死人；成是一行纵队, 则末行是人, 求兵数. 解：" 韩信点兵" 问题转化为数学语言即求解下列一次同余式组
⎧x ⎪⎪x ⎨⎪x ⎪⎩x
≡1(m od 5)≡5(m od 6)≡4(m od 7)≡10(m od 11)
按照中国剩余定理的记号m 1=5, m 2=6, m 3=7, m 4=11两两互素, 又
⎧M =5⨯6⨯7⨯11=2310⎪
M =6⨯7⨯11=462⎪1⎪
⎨M 2=5⨯7⨯11=385
⎪M =5⨯6⨯11=330⎪3⎪⎩M 4=5⨯6⨯7=210
又要求a i . M i ≡1(mod m i ), i =1, 2, 3, 4, 得a i =3, a 2=a 3=a 4=1, 又c 1=1, c 2=5, c 3=4, c 4=10, 于是
x ≡M 1a 1c 1+M 2a 2c 2+M 3a 3c 3+M 4a 4c 4(m od M
)
≡46⨯23⨯1+3⨯8⨯515+330⨯1⨯4+210⨯1⨯10(m od 2310)≡1386+1925+1320+2100(m od 2310)≡6731(m od 2310)≡2111(m od 2310)
即韩信的兵有2111+k 2310, k 为非负整数. 4.2 在多项式理论中的应用
中国剩余定理在多项式中的应用时比较广泛的, 其中Lagrange 内插多项式是处理许多多项式问题的基本工具；下面我们通过余数定理和插值多项式的存在唯一性定理导出Lagrange 内插多项式, 再通过Lagrange 内插多项式求一级数的和.
（1）余数定理
余数定理是指一个多项式f (x )除以一线性多项式x -a 的余数是f (a ). （2）插值多项式的存在和唯一性定理
设m 1(x ), m 2(x ),..., m 是n 个两两互素的多项式, a 1(x ), a 2(x ),..., a n (x )是n 个
⎧f (x )≡a 1(x )(m od m 1(x ))⎪
⎪f (x )≡a 2(x )(m od m 2(x ))
多项式, 而一定存在多项式f (x ), 使⎨
⎪.......................................... ⎪
f x ≡a n (x )(m od m n (x ))⎩()
当f (x )的次数不超过M (x )(M (x )≡m 1(x )m 2(x )... m n (x ))的次数时, f (x )唯一确定. 特别地, 当m i =x -b i ∈Q [x ]或R [x ], b i (i =1, 2,..., n )是不相等的常数, 从而
m i (x )(i =1, 2,..., n )也就是两两互素的多项式, 由余数定理可知
一定存在f (x ), 使得m i (x )≡m i (b i )(mod x -b i )(i =1, 2,..., n ), 从而定理可叙述为：
⎧f (x )≡a 1(m od x -b 1)
⎪
⎪f (x )≡a 2(m od x -b 2)
⎨
⎪................................... ⎪f (x )≡a (m od x -b )
n n ⎩
其中a i (i =1, 2,..., n )是任意给定的常数, 且多项式f (x )在次数不超过n 的条件下是唯一确定的. 由f (x )≡a i (mod x -b i )等价于f (b i )=a i (i =1, 2,..., n )知对任意的互不相同的b i (i =1, 2,..., n )及a i (i =1, 2,..., n )任意的存在唯一的次数小于n 的多项式f (x ), 使f (b i )=a i (i =1, 2,..., n ), 这就是插值多项式的存在和唯一性定理. （3）Lagrange 内插值多项式
n
n
f (x )=a 1M 1(x )+a 2M 2(x )+... +a n M n (x )=
∑
j =1
a j ∏
i =1
(x -b i )
(b
j
-b i )
(i ≠j )
其中M i (x )=
... (x -b 1)... (x -b i -1)(x -b (x -b i +1)n )n )是个两两互素的(i =1, 2,..., ... (b i -b 1)... (b i -b i -1)(b i -b +(b i -b n )i 1)
多项式, b i (i =1, 2,..., n )是不相等的常数, a i (i =1, 2,..., n )是任意给定的常数.
分析：根据插值多项式的存在和唯一性定理, 由中国剩余定理的证法, 只要找到多项式M i (x )(i =1, 2,..., n ), 使
⎧⎪M i (x )≡1(mod x -b i )
⎨
M x ≡0(mod x -b j ), i ≠j ⎪⎩i ()
而M i (x )=
(x -b 1)... (x -b i -1)(x -b i +1)... (x -b n )
(i =1, 2,..., n )符合要求, 于是插值
b -b ... b -b b -b ... b -b (i 1)(i i -1)(i i +1)(i n )
n
n
多项式f (x )=a 1M 1(x )+a 2M 2(x )+... +a n M n (x )=
∑
j =1
a j ∏
i =1
(x -b i )
(b
j
-b i )
(i ≠j )即所求.
2
例 利用内插值多项式简化下列数列求和问题, 02+12+22+... +(n -1). 解 设和为n 的三次多项式f (n ), n 代表项数, 于是有
f (0)=0, f (1)=0, f (2)=1, f (3)=5. 由插值公式得
f (n )=0⨯M 1(n )+0⨯M 2(n )+1⨯M 3(n )+5⨯M 4(n )=
(n -0)(n -1)(n -3)(n -0)(n -1)(n -2)
+5⨯
2-02-12-3()()()(3-0)(3-1)(3-2)
16
n (n -1)(2n -1)
2
=
所以02+12+22+... +(n -1)=4.3 在赋值理论中的应用
16
n (n -1)(2n -1).
赋值理论是域论的一个分支, 是研究近代数学中几个重要分支如代数理论, 交换数论的一个重要工具, 而中国剩余定理在赋值论中起着重要作用, 下面介绍中国剩余定理在赋值理论中的应用.
定理（赋值的独立性） 对于任意n 个p 赋值V p 1, V p 2,... V pn , a ∈Q , i =1, 2,..., n , 以及任意ε>0, P 1-l , P 2-l ,..., P m -l , 则存在b ∈Q 使
（1）V ∞(b -a )=b -a 1
i
证明 设m 为a 1, a 2,..., a n 的最少公分母, 令P i si =V pi (m ), r i =l i +s i , i =1, 2,..., n .
r =max {1, r 1, r 2,..., r n }. 根据中国剩余定理, 可求得一个c , 使得
c ≡ma 1(mod p 1
r
), c ≡ma (mod pr ),..., c ≡ma (mod p )
r
r
2
2
n
n
即V pi (c -m a i )≤p i -r , V pi
⎛c
⎫-l
-a i ⎪≤p i i . ⎝m ⎭
r
设q =(p 1p 2... p n ), 取适当的u , v ∈Z , 使
cl +uq m l +vq
-a
c l +u q m l +v q
=a , 则
显然b 满足条件（1）. 又由p 距离D P 的性质：max (D P (a , b ), D P (b , c ))≥D P (a , c )有V pi (b -a i )≤m ax ⎨V pi b -
⎩
⎝⎧
⎛
c ⎫⎛c ⎫⎫-l
+-a ≤p i i , i =1, 2,..., n . i ⎪⎬⎪ m ⎭⎝m ⎭⎭
4.4 在密码学中的应用
中国剩余定理虽是数论中的基本定理, 但是在计算机密码雪中有着重要的应用. 例如在Rabin 密码算法中用于解密运算. 在RSA 密码算法中, 中国剩余定理同样可用于RSA 的解密运算, 而且使RSA 的机密速度大约底稿4倍左右, 这无论对于软件还是硬件实现RSA 密码算法都非常重要的. 下面主要从基于中国剩余定理的一种加密算法和中国剩余定理的RSA 解密中的应用两点来说. 4.4.1 基于中国剩余定理的一种加密算法
根据中国剩余定理, 可以得出一种新的网络信息加密算法. A 1, A 2, A 3,..., A n 为
, 余数分别为n 个互质的素数, 若已知一个整数Y 除以A 1, A , 2A , 3. . . n A
B 1, B 2, B 3,..., B n , 求Y .
解 令M =A 1⨯A 2⨯A 3⨯... ⨯A n ,
X 1表示能被A 2, A 3,..., A n 整除的所有整数,
Y 1表示能被A 2⨯A 3⨯... ⨯A n 整除的所有整数且除以A 1余B 1的所有整数,
X 2表示能A 1⨯A 3⨯... ⨯A n 被整除的所有整数, Y 2表示能被A 1⨯A 3⨯... ⨯A n 整除的所有整数且除以A 2
余B 2的所有整数,
X i 表示能被A 1, A 2, A 3,..., A i -1, A i +1,..., A n 整除的所有整数,
Y i 表示能被整除A 1, A 2, A 3,..., A i -1, A i +1,..., A n 的所有整数且除以A i 余B i
的所有整数,
X 1=A 2⨯A 3⨯... ⨯A n ⨯m =M ⨯m
,
A 1
那么
X 2=A 1⨯A 3⨯... ⨯A n ⨯m =M ⨯m ...
X n =A 1⨯A 2⨯... A n -1⨯m =M ⨯m
,
A 2其中m 为任意整数.
A n
,
设F i 满足X i 和Y i , 且令其为Y i 中最小的正整数, 其中1≤i ≤n 则
Y 1=F 1+A 1⨯A 2⨯A 3⨯... ⨯A n ⨯m =F 1+M ⨯m ...
Y n =F n +A 1⨯A 2⨯A 3⨯... ⨯A n ⨯m =F n +M ⨯m
那么Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m .
用Y 表示明文, 是所要隐蔽和保护的机要信息, 用B 1, B 2, B 3,..., B n 表示密文, 要把明文转换成一种隐蔽的形式：A 1, A 2, A 3,..., A n 和N 为密钥.
加密算法步骤如下：
步骤1：选出n 个A 1, A 2, A 3,..., A n 作为" 密钥" ； 步骤2：求出这n 个素数的乘积M ; 步骤3：求出F 1, F 2, F 3,..., F n ;
步骤4：由Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m 得出
m =⎡⎣Y -(F 1+F 2+F 3+... +F n )⎤⎦M
;
步骤5：用Y 分别除以A 1, A 2, A 3,..., A n 得余数B 1, B 2, B 3,..., B n 并把它们作为密文.
解密算法的步骤如下：
已知密文B 1, B 2, B 3,..., B n 和密钥A 1, A 2, A 3,..., A n 和N 算出F 1, F 2, F 3,..., F n . 由Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m 得出Y . 这样就实现了从密文和密钥到明文的整个解密过程. 加密和解密举例：
令明文X =200, 密钥为5, 7,11, 密文1, 6, 为可求出
F 1=231, F 2=55, F 3=175,
那么m =⎡⎣2001-(231+55+175)⎤⎦5⨯7⨯11)=4为另一密钥. 解密:
Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m =221+175+55+5⨯7⨯11⨯4=2001.
4.4.2 中国剩余定理在RSA 解密中的应用
1978年美国麻省理工学院的三位教授R . L . Rivest , A . Shamir 和M . Adleman 提出来一种基于因子分解的指数函数作为单项陷门函数的公开密钥算法, 即著名的RSA 算法. RSA 算法是第一个较完善的PKC 算法, 也是非常容易理解和实现的PKC 算法. 它既可用于传输信息的加密, 也可用于数字签名系统, 是当前民用也是商业使用最广泛的公开密钥密码算法之一, 已被国际标准化组织ISO,JTU 和SWIFT 接受为标准.
随机选取两个不同的大素数p 和q （约为150位或更大的十进制数）, 计算它们的乘积M =pq 与相应的Euler 函数(Euler Totient Function )φ(n )=(p -1)(q -1)的值, 将公开, 而将φ(n ), p 和q 保密；显然, 如果不知道的素因子q 和p 的前提下, 计算φ(n )的值是属于NP 问题, 极难实现.
再随机选取一个正整数e , 是e 满足条件：e
-1
φ(N )最大共因素1）, 根据扩展Eulicd 算法计算d =e (mod φ(N )), 即计算满足
ed =1(mod (φ(M )))的d . 将e 公开, 而将d 保密, 就确定了RSA 算法的公开密钥
{(N , p , q , e , d )}
N =pq ,
PK =(e , N ), 私人密钥SK =(d , N ), 密钥空间：K =
p
与q 为不同大素数, ed =1(mod φ(N ))}.
相应地, RSA 算法中的单向陷门函数为f (x )=x t (mod N ), (其中t ∈K 且
x ∈Z N , 称为RSA
函数. 其秘密陷门信息为φ(N )及素数p , q 的值. 确实公钥
PK =(e , N )和私钥SK =(d , N )之后, RSA 算法的机密运算定义为：
c =E pk (m )=m
e
(mod N ), 其中为1≤m ≤N -1明文.
解密运算定义为：m =D sk (c )=c d (mod N )其中1≤c ≤N -1为密文.
RSA
秘密算法的明文m 应为1到N -1之间的整数, 即m ∈[1, N -1]' 如果明文
s
m 太长, 可将其转换成N 进制的形式, 即m =m s N
+m s -1N
S -1
+... +m 1N +m 0,
于
是得到分组后的明文序列m =(m 0, m 1,..., m s ), , 其中m i ∈[1, N ], 0≤i ≤s , 与之相应的密文序列为c =(c 0, c 1,... c s ), 其中c i 对应于m i (0≤i ≤s ).
中国剩余定理是初等数论中重要的基本定理之一, 它主要是刻画剩余系的结构和求解形如x =d i mod p i )(1≤i ≤s )的一次同余式方程. 在计算数论中, 计算中国剩余定理唯一解的方法有两种：单基数转换法和混合技术转换法, 这两种防范都是非常实用的计算方法.
算法一 CRT 的单基数转换法（SRC ） (1)计算p ←p 1p 2... p s 和p i ←p
-1
p i
(1≤i ≤s );
(2)计算Q 1←P 1(mod p i ), (1≤i ≤s );
(3)计算唯一解x ←d 1P 1Q 1+d 2P 2Q 2+... +d s P S Q s (mod P ).
利用混合技术转换法（MRC ）求CRT 的唯一解的方法是H . L . G arner 在1958年首先提出的. 之后D . E . K unth 将其用于计算数论, 并进行了有益的改进. 经过
D . E . K unth
改进后的MRC 方法用算法描述如下：
算法二 CRT 的混合基数转换法（MRC ） (1)计算B ji ←P J (mod P i ), (1≤j ≤i ≤s ); (2)分别计算
v i ←d 1(mod p i );
v 2←(d 2-v 1)B 12(mod p 2); ......
v s ←(d s -(v 1+p 1(v 2+p 2(v 3+... +p s -2v s -1))))B 1s B 2s ... B (s -1)s (mod p s ).
(3)计算唯一解X ←v s p s -1... p 2p 1+... +v 3p 2p 1+v 2p 1+v 1'
利用中国剩余定理对RSA 密码解密, 首先要将RSA 的解密运算由计算模N 的指数形式转化成求解同余式方程组的情形. 为此, 先介绍两个必须的数论定理
定理1 （中国剩余定理的推论） 设p 1, p 2,..., p s 是s 个两两互素的正整数,
P =p 1p 2... p 3, 则同余式f (x )≡0(mod p )与同余式方程组 f (x )≡0(mod p i )(1≤i ≤s )等价.
定理2（费马小定理） 设q 是一个素数, x 是一个满足x (mod p )≠0的整数, 则：x p -1≡1(mod p ).
算法三 RSA 的SRC 解密算法
(1)计算d 1←(mod p -1)与d 2←d (mod q -1); (2)计算C 1←c (mod p )C 2←c (mod q ); (3) 计算M 1←C 1d (mod p )M 2←C 2d (mod q )
1
2
(4)计算B 1←q -1(mod p )B 2←p -1(mod q ); (5)计算m ←M 1B 1q +M 2B 2p (mod M ). 4.5 在生活中的应用
在日常生活中我们所注意到的不是某些数, 而是这些数除某一固定的数所得到的余数. 例如, 假定现在是早上10点, 在两个小时前是几点? 我们立刻可得到正确答案是早上八点, 那么过了13个小时候又是几点呢? 算式为10+13-12=11即晚上11点; 在28个小时候手表的时针又是什么情况呢? 算式为（10+28）-（12⨯3）=2即是两点.
解决此类问题的方法是:若现在的事件是A , 问经过B 小时后的时间, 只需计算A +B ≡c (mod 12), 余数就是手表的时针数. 5 结束语
本文通过对中国剩余定理的描述阐述, 对中国剩余定理（孙子定理）在实际生活中的应用进行了初步的说明和描述. 以上只是一些简单的例子, 但足可见中国剩余定理应用之广泛, 地位之高, 作为数学史上名垂百世的成就, 其数学思想一直启发和指引着历代数学家.
致谢
历时将近两个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了. 尤其要强烈感谢我的论文指导老师—王众杰老师，他对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的修改和改进. 另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助. 在此向帮助和指导过我的各位老师表示最中心的感谢！
感谢这篇论文所涉及到的各位学者. 本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文的写作.
感谢我的同学和朋友，在我写论文的过程中给予我了很多你问素材，还在论文的撰写和排版灯过程中提供热情的帮助.
由于我的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正！
参考文献
《孙子算经》, 《张邱建算经》, 《夏侯阴算经导读》, 湖北教育出[1]纪志刚编：版社, 1999年.
[2]田金兵, 严政, 刘合国. 关于中国剩余定理[J ] . 湖北大学学报, 2006,28
（4）:325-327
《广义中国定理及其Maple 解法》, 重庆大学学报, 2004年. [3]冯国锋：
《公钥密码学》, 哈尔滨黑龙江出版社, 1993年. [4]曹珍富：
[5]贺毅朝, 刘建芹, 陈伟海, 《中国剩余定理在RSA 解密中的应用, 河北省科学学
院报, 第20卷第3期, 2003年.
[6]匡正:组合数学习题精解[M ]. 哈尔滨：哈尔滨工业大学出版社，2005. [7]钟善基. 小学迎春杯数学竞赛指导讲座. 北京师范大学出版社.
Chinese remainder theorem induction and its application
REN Xiao-yan
College of Mathematics Science No:080414001
Tutor: WANG Zhong-jie
Abstract ：Chinese remainder theorem is also known as the Chinese Remainder Theorem and its mathematical thoughts in modern mathematics plays a very important role .This paper summarizes the Chinese Remainder Theorem and prove and gives the relevant classical example and based on the multinomial theorem congruence group, Olympic, assignment theorem, cryptography and application were discussed and analysis.
Key words: ChineseRemainder Theorem Congruence group Polynomial Cryptography
LUOYANG NORMAL UNIVERSITY
2012届 本科毕业论文
中国剩余定理的归纳及其应用
院（系）名称 专 业 名 称 学
生
姓
名
数学科学学院 数学与应用数学
任晓燕 080414001 王众杰 讲师
2012.5
学 号 指
导
教
师
完 成 时 间
中国剩余定理的归纳及其应用
任晓燕
数学科学学院 数学与应用数学 学号：080414001
指导老师：王众杰
摘要：中国剩余定理又称为孙子定理, 它的数学思想在近代数学中占有非常重要的地位. 本文归纳了中国剩余定理并给出证明, 并给出相关的经典例, 并在此基础上对其在同余式组, 多项式定理、赋值定理、密码学以及生活中的应用进行初步的讨论和分析.
关键词：中国剩余定理； 同余式组； 多项式； 密码学 引言
中国古代著名数学著作记载, " 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何? " 此问题为中国剩余定理的原型. 解法和答案用算式表示为70×2+21×3+15×2-105×2=23.即得到适合题意的最小整数是23. " 物不知其数" 开创了一次同余式研究的先河, 但真正从完整的计算程序和理论上解决这个问题的事南宋时期的数学家秦九韶, 秦九韶在他的《数书九章》中提出了一个数学方法" 大衍求一术" .
1876年, 德国人马蒂生首先指出这一解法与19世纪高斯《算术探究》中关于一次同余式组的解法完全一致. 从此, 中国古代数学这一创造受到世界学者瞩目, 并在西方数学史著中正式称为" 中国剩余定理" .
. 1
中国剩余定理及其证明
设n 2, m 1, m 2,... m n 两两互素的正整数,
令M =m 1m 2... m n =m 1M 1=m 2M 2=... m n M n , 则同余式组
⎧x =c 1(m od m 1)⎪
⎪x =c 2(m od m 2)
⎨
⎪........................ ⎪x =c (m od m )
n n ⎩
有正整数解x =M 1a 1c 1+M 2a 2c 2+... M n a n c n (mod M )且解唯一；其中a i 是满足
M i a i ≡1(mod m i ), (i =1, 2,... n )的一个整数.
下面我们先给出裴蜀恒等式和一个性质, 然后证明中国剩余定理.
在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a 、b 和它们的最大公约数d ，关于未知数x 和y 的线性丢番图方程ax +by =d （称为裴蜀等式）：
裴蜀恒等式 如果两个数的最大公约数是d , 则必定存在两个整数x , y 使得等式ax +by =d 成立. .
性质 同余式组a ≡b (mod m j )j =1, 2,... n 同时成立的充要条件是a ≡b (m od ⎡⎣m 1, m 2,... m n ⎤⎦).
证明 先证存在性：因为m 1, m 2,... m 两两互素, M k =
M m k
,
故(M k , m k )=1, k =1, 2,... n , 由裴蜀恒等式可知一定存在整数αk , βk 使得
M k αk +βk m k =1, 即M k αk =-βk m k +1, 因此必定存在αk , 使
M k αk ≡1(mod m k ), k =1, 2,... n . 又因当λ≠k 时, 恒有m λM k ,
所以M k a k ≡1(mod m λ)(λ≠k ). 若令R =x =M 1a 1c 1+M 2a 2c 2+... M n a n c n , 则有
⎧R =M 1a 1c 1(m od m 1)⎪
⎪R =M 2a 2c 2(m od m 2)
⎨
⎪................................ ⎪R =M a c (m od m )
n n n n ⎩
又m k M , 故M ≡0(mod m k ), 从而x =R +M t ≡R ≡c k (mod m k ), k =1, 2,... n . 因此x ≡R (mod M ), 即R =x =M 1a 1c 1+M 2a 2c 2+... M n a n c n (m od M )为同余式组之解.
唯一性：该同余式组还有一组解y , 则有x ≡y (mod m k ), , k =1, 2,..., n 由于m 1, m 2,..., m n 两两互素, 因此M =[m 1, m 2,..., m n ]=m 1m 2... m , 利用所给性质可知
x ≡y (mod M ), 证毕.
2 中国剩余定理的推广
2.1 一元多项式环中的中国剩余定理
2.1.1 定理 设m 1(x ), m 2(x ),... 是两两既约的多项式, 那么对任意的多项式
r 1(x ), r 2(x ),... , ∃g (x )∈R [X ], 使得g (x )≡r j (x )(mod m j (x )), j =1, 2,... , 记此式为
(1)式, 且有：
g (x )≡M 1(x )M 1
-1
(x )r 1(x )+M 2(x )M 2-1(x )r 2(x )+... +M k (x )M k -1(x )r k (x )(mod m (x ))
这里g (x )在mod m (x )下是唯一的, 其中：m (x )=m 1(x )m 2(x )... , 且有下式：
m (x )=m j (x )M
j
(x ),
j =1, 2,... , 以及M
-1j (x )是M j (x )对模M j (x )的逆.
2.1.2 定理的应用
在上述定理中, 取M i (x )=x -a i , a i ≠a j , i ≠j 时, 令r i (x )=r , 则有：
r i (x )=r i =g (a ).
则可得到插值公式
M 1(x )M 1
-1
(x )r 1(x )+... +M k (x )M k
-1
⎛k ⎫
(x )r k (x )= ∏(x -a i )⎪q (x )
⎝i =1⎭
其中
M i (x )=
∏(x -a ), M (x )=∏(x -a ), 令为：h (x )(x -a k )+l 所以有：
j
k
j
j =1, j ≠i
j =1
k k -1
1l
M k (x )-
h (x )l
1l
(x -a k )=1
k -1
则M k (x )=. M k (a k )=∏(a k -a i )=h (a k )(a k -a k )+l =l .
-1
i =1
则=
l
11
k -1
M k
-a i )
-1
(x ), 同理求得M
-1j (x ),
j =1, 2,... , 代入上述插值公式, 即得
∏(a
i =1
k
到拉格朗日插值公式.
2.2 中国剩余定理在非标准数论中的推广 2.2.1 第一广义中国剩余定理
设(p 1, p 2... )是一列标准素数, (r 1, r 2... )是自然数集的任一无穷子列, 将它作为一组余数, 则Γ(x )={(∃q i p i )(x ≡q i p i +r i )|i =1, 2,... }与THN 和谐.
例 证明 可数THN 的模型的总数为2ω.
证明 由第一广义中国剩余定理知每个Γ(x )都是THN 和谐的, 因而可以扩充为一个极大的和谐式子集, 这样一个极大的和谐式子集是某个非标准数所满足的型. 每一序列(r 1, r 2,... )(0≤r i ≤p i )都可以对应着一个型. 不同的序列对应的型也不同. 因而, 数论中型的个数必然必这些无穷数列的个数多, 计算这样的无穷序列的个数可以得出型的个数的上界. 实际上, 易见这个数目为
∏
i
p i =2⨯3⨯⨯5⨯7, 由集合论可知.
(i )∏
i
p i ==2
∏i
i
(ii )ωω
i
ω
(iii )∏i =2ω
综上可知∏
i
p i =2. 另一方面, 作为可数理论, THN 之多有2ω个型. 因此
ω
THN 共有2ω个型. 由每个型出发, 利用它与THN 的和谐性可以有一个可数模型
实现它. 我们知道一个可数模型之多能实现可数多个型, 所以互不相同构的可数模型的总数仍为2ω. 2.2.2 第二广义中国剩余定理
设ψ是一个ω-饱和THN 模型. (p 1, p 2... )是一列标准或非标准素数(r 1, r 2... )是一列满足0≤r i
⎧x ≡r 1(m od m 1), ⎪⎪...
=1(i ≠j ), 那么对所有, 同余式⎨
⎪x ≡r n (m od m n ), ⎪... ⎩
设r 1..., r n ..., ∈N , 且(m i , m j )
有解.
例 证明 存在无限组孪生拟素数(p , p +2).
证明 首先构造一组孪生拟素数：
我们规定余数列为r 1=1, r 2=2, r i =1(i =3, 4,... ), 即(1, 2,1,1,... ), 由它得到式子集Γ(x )={(∃q i )(x ≡q i p i +r i )i =1, 2,... }与T 和谐, 在ℜ中又非标准数p 实现
Γ(x ),
显然它是一个拟素数, 而且余数列的特殊取值p +2也是拟素数, 即
=0, i =1, 2,..., 设它所对应
(p , p +2)使一组孪生拟素数. 另一方面, 如果余数列取r i
的非标准数为q .
那么令p 1=p +q , p 2=p +2⨯q , p 3=p +3⨯q ,..., 就得到了无限组孪生拟素数
(p , p +2), (p 1, p 1), (p 2, p 2+2)(p 3, p 3+2),...
3 中国剩余定理的另解 3.1 同余扩整法
设所求的整数为N , 引言中题意是：N 被3除余2被5除余3被7除余2求N 的最小值. 我们不妨从第三个条件切入. N 被7除余2就可以说和7对于模
是同余的那么2加上7的整数倍后所得的数与N 对于模7仍同余所以用2依次加7的1倍2倍3倍后经检验2+3=23既符合被3除余2又符合被5除余3
⎛7⎫
2+79+716+7 ⎪
916233. 故N 的最小值是23. 于是可写成：2(7) ⎪
5⎪⎝⎭
3.2 列方程组法
设被所得的整数商分别为依题意3x +2=5y +3=7z +2=N (1)
⎧⎪3x -5y =1
于是有⎨
⎪⎩5y -7z =-1
(2)(3)
t ⎧⎪x =2+5t ⎪⎩y =1+3
解方程(2)得通解 ⎨
(4)
(t ∈Z )
(5)
将(5)式代入(3)得7z -15t =6.
⎧⎪t =-1-7t 1此不定方程的通解为⎨
⎪⎩z =3+15t 1
(6)
(t 1∈z )
(7)
将(6)代入(4), (5)同时考虑式(7)得原方程组的全部整数解为
⎧x =7+35t 1⎪
⎨y =4+21t 1⎪
⎩z =3+15t 1
(8)(9).
(t 1∈Z )(10)
上式三式(8), (9), (10)中任意一个代入(1)得" 物不知其数" 问题的通解
N =23+105t 1. 当t 1=0时N =23是最小的正整数解.
4 剩余定理的几个应用 4.1 在同余式组中的应用
例 " 韩信点兵" 问题：有兵一堆, 若列成五行纵列则末行一人; 成刘航纵队, 则末行五人；成七行纵队, 则末行死人；成是一行纵队, 则末行是人, 求兵数. 解：" 韩信点兵" 问题转化为数学语言即求解下列一次同余式组
⎧x ⎪⎪x ⎨⎪x ⎪⎩x
≡1(m od 5)≡5(m od 6)≡4(m od 7)≡10(m od 11)
按照中国剩余定理的记号m 1=5, m 2=6, m 3=7, m 4=11两两互素, 又
⎧M =5⨯6⨯7⨯11=2310⎪
M =6⨯7⨯11=462⎪1⎪
⎨M 2=5⨯7⨯11=385
⎪M =5⨯6⨯11=330⎪3⎪⎩M 4=5⨯6⨯7=210
又要求a i . M i ≡1(mod m i ), i =1, 2, 3, 4, 得a i =3, a 2=a 3=a 4=1, 又c 1=1, c 2=5, c 3=4, c 4=10, 于是
x ≡M 1a 1c 1+M 2a 2c 2+M 3a 3c 3+M 4a 4c 4(m od M
)
≡46⨯23⨯1+3⨯8⨯515+330⨯1⨯4+210⨯1⨯10(m od 2310)≡1386+1925+1320+2100(m od 2310)≡6731(m od 2310)≡2111(m od 2310)
即韩信的兵有2111+k 2310, k 为非负整数. 4.2 在多项式理论中的应用
中国剩余定理在多项式中的应用时比较广泛的, 其中Lagrange 内插多项式是处理许多多项式问题的基本工具；下面我们通过余数定理和插值多项式的存在唯一性定理导出Lagrange 内插多项式, 再通过Lagrange 内插多项式求一级数的和.
（1）余数定理
余数定理是指一个多项式f (x )除以一线性多项式x -a 的余数是f (a ). （2）插值多项式的存在和唯一性定理
设m 1(x ), m 2(x ),..., m 是n 个两两互素的多项式, a 1(x ), a 2(x ),..., a n (x )是n 个
⎧f (x )≡a 1(x )(m od m 1(x ))⎪
⎪f (x )≡a 2(x )(m od m 2(x ))
多项式, 而一定存在多项式f (x ), 使⎨
⎪.......................................... ⎪
f x ≡a n (x )(m od m n (x ))⎩()
当f (x )的次数不超过M (x )(M (x )≡m 1(x )m 2(x )... m n (x ))的次数时, f (x )唯一确定. 特别地, 当m i =x -b i ∈Q [x ]或R [x ], b i (i =1, 2,..., n )是不相等的常数, 从而
m i (x )(i =1, 2,..., n )也就是两两互素的多项式, 由余数定理可知
一定存在f (x ), 使得m i (x )≡m i (b i )(mod x -b i )(i =1, 2,..., n ), 从而定理可叙述为：
⎧f (x )≡a 1(m od x -b 1)
⎪
⎪f (x )≡a 2(m od x -b 2)
⎨
⎪................................... ⎪f (x )≡a (m od x -b )
n n ⎩
其中a i (i =1, 2,..., n )是任意给定的常数, 且多项式f (x )在次数不超过n 的条件下是唯一确定的. 由f (x )≡a i (mod x -b i )等价于f (b i )=a i (i =1, 2,..., n )知对任意的互不相同的b i (i =1, 2,..., n )及a i (i =1, 2,..., n )任意的存在唯一的次数小于n 的多项式f (x ), 使f (b i )=a i (i =1, 2,..., n ), 这就是插值多项式的存在和唯一性定理. （3）Lagrange 内插值多项式
n
n
f (x )=a 1M 1(x )+a 2M 2(x )+... +a n M n (x )=
∑
j =1
a j ∏
i =1
(x -b i )
(b
j
-b i )
(i ≠j )
其中M i (x )=
... (x -b 1)... (x -b i -1)(x -b (x -b i +1)n )n )是个两两互素的(i =1, 2,..., ... (b i -b 1)... (b i -b i -1)(b i -b +(b i -b n )i 1)
多项式, b i (i =1, 2,..., n )是不相等的常数, a i (i =1, 2,..., n )是任意给定的常数.
分析：根据插值多项式的存在和唯一性定理, 由中国剩余定理的证法, 只要找到多项式M i (x )(i =1, 2,..., n ), 使
⎧⎪M i (x )≡1(mod x -b i )
⎨
M x ≡0(mod x -b j ), i ≠j ⎪⎩i ()
而M i (x )=
(x -b 1)... (x -b i -1)(x -b i +1)... (x -b n )
(i =1, 2,..., n )符合要求, 于是插值
b -b ... b -b b -b ... b -b (i 1)(i i -1)(i i +1)(i n )
n
n
多项式f (x )=a 1M 1(x )+a 2M 2(x )+... +a n M n (x )=
∑
j =1
a j ∏
i =1
(x -b i )
(b
j
-b i )
(i ≠j )即所求.
2
例 利用内插值多项式简化下列数列求和问题, 02+12+22+... +(n -1). 解 设和为n 的三次多项式f (n ), n 代表项数, 于是有
f (0)=0, f (1)=0, f (2)=1, f (3)=5. 由插值公式得
f (n )=0⨯M 1(n )+0⨯M 2(n )+1⨯M 3(n )+5⨯M 4(n )=
(n -0)(n -1)(n -3)(n -0)(n -1)(n -2)
+5⨯
2-02-12-3()()()(3-0)(3-1)(3-2)
16
n (n -1)(2n -1)
2
=
所以02+12+22+... +(n -1)=4.3 在赋值理论中的应用
16
n (n -1)(2n -1).
赋值理论是域论的一个分支, 是研究近代数学中几个重要分支如代数理论, 交换数论的一个重要工具, 而中国剩余定理在赋值论中起着重要作用, 下面介绍中国剩余定理在赋值理论中的应用.
定理（赋值的独立性） 对于任意n 个p 赋值V p 1, V p 2,... V pn , a ∈Q , i =1, 2,..., n , 以及任意ε>0, P 1-l , P 2-l ,..., P m -l , 则存在b ∈Q 使
（1）V ∞(b -a )=b -a 1
i
证明 设m 为a 1, a 2,..., a n 的最少公分母, 令P i si =V pi (m ), r i =l i +s i , i =1, 2,..., n .
r =max {1, r 1, r 2,..., r n }. 根据中国剩余定理, 可求得一个c , 使得
c ≡ma 1(mod p 1
r
), c ≡ma (mod pr ),..., c ≡ma (mod p )
r
r
2
2
n
n
即V pi (c -m a i )≤p i -r , V pi
⎛c
⎫-l
-a i ⎪≤p i i . ⎝m ⎭
r
设q =(p 1p 2... p n ), 取适当的u , v ∈Z , 使
cl +uq m l +vq
-a
c l +u q m l +v q
=a , 则
显然b 满足条件（1）. 又由p 距离D P 的性质：max (D P (a , b ), D P (b , c ))≥D P (a , c )有V pi (b -a i )≤m ax ⎨V pi b -
⎩
⎝⎧
⎛
c ⎫⎛c ⎫⎫-l
+-a ≤p i i , i =1, 2,..., n . i ⎪⎬⎪ m ⎭⎝m ⎭⎭
4.4 在密码学中的应用
中国剩余定理虽是数论中的基本定理, 但是在计算机密码雪中有着重要的应用. 例如在Rabin 密码算法中用于解密运算. 在RSA 密码算法中, 中国剩余定理同样可用于RSA 的解密运算, 而且使RSA 的机密速度大约底稿4倍左右, 这无论对于软件还是硬件实现RSA 密码算法都非常重要的. 下面主要从基于中国剩余定理的一种加密算法和中国剩余定理的RSA 解密中的应用两点来说. 4.4.1 基于中国剩余定理的一种加密算法
根据中国剩余定理, 可以得出一种新的网络信息加密算法. A 1, A 2, A 3,..., A n 为
, 余数分别为n 个互质的素数, 若已知一个整数Y 除以A 1, A , 2A , 3. . . n A
B 1, B 2, B 3,..., B n , 求Y .
解 令M =A 1⨯A 2⨯A 3⨯... ⨯A n ,
X 1表示能被A 2, A 3,..., A n 整除的所有整数,
Y 1表示能被A 2⨯A 3⨯... ⨯A n 整除的所有整数且除以A 1余B 1的所有整数,
X 2表示能A 1⨯A 3⨯... ⨯A n 被整除的所有整数, Y 2表示能被A 1⨯A 3⨯... ⨯A n 整除的所有整数且除以A 2
余B 2的所有整数,
X i 表示能被A 1, A 2, A 3,..., A i -1, A i +1,..., A n 整除的所有整数,
Y i 表示能被整除A 1, A 2, A 3,..., A i -1, A i +1,..., A n 的所有整数且除以A i 余B i
的所有整数,
X 1=A 2⨯A 3⨯... ⨯A n ⨯m =M ⨯m
,
A 1
那么
X 2=A 1⨯A 3⨯... ⨯A n ⨯m =M ⨯m ...
X n =A 1⨯A 2⨯... A n -1⨯m =M ⨯m
,
A 2其中m 为任意整数.
A n
,
设F i 满足X i 和Y i , 且令其为Y i 中最小的正整数, 其中1≤i ≤n 则
Y 1=F 1+A 1⨯A 2⨯A 3⨯... ⨯A n ⨯m =F 1+M ⨯m ...
Y n =F n +A 1⨯A 2⨯A 3⨯... ⨯A n ⨯m =F n +M ⨯m
那么Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m .
用Y 表示明文, 是所要隐蔽和保护的机要信息, 用B 1, B 2, B 3,..., B n 表示密文, 要把明文转换成一种隐蔽的形式：A 1, A 2, A 3,..., A n 和N 为密钥.
加密算法步骤如下：
步骤1：选出n 个A 1, A 2, A 3,..., A n 作为" 密钥" ； 步骤2：求出这n 个素数的乘积M ; 步骤3：求出F 1, F 2, F 3,..., F n ;
步骤4：由Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m 得出
m =⎡⎣Y -(F 1+F 2+F 3+... +F n )⎤⎦M
;
步骤5：用Y 分别除以A 1, A 2, A 3,..., A n 得余数B 1, B 2, B 3,..., B n 并把它们作为密文.
解密算法的步骤如下：
已知密文B 1, B 2, B 3,..., B n 和密钥A 1, A 2, A 3,..., A n 和N 算出F 1, F 2, F 3,..., F n . 由Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m 得出Y . 这样就实现了从密文和密钥到明文的整个解密过程. 加密和解密举例：
令明文X =200, 密钥为5, 7,11, 密文1, 6, 为可求出
F 1=231, F 2=55, F 3=175,
那么m =⎡⎣2001-(231+55+175)⎤⎦5⨯7⨯11)=4为另一密钥. 解密:
Y =Y 1+Y 2+Y 3+... +Y n =F 1+F 2+F 3+... +F n +M ⨯m =221+175+55+5⨯7⨯11⨯4=2001.
4.4.2 中国剩余定理在RSA 解密中的应用
1978年美国麻省理工学院的三位教授R . L . Rivest , A . Shamir 和M . Adleman 提出来一种基于因子分解的指数函数作为单项陷门函数的公开密钥算法, 即著名的RSA 算法. RSA 算法是第一个较完善的PKC 算法, 也是非常容易理解和实现的PKC 算法. 它既可用于传输信息的加密, 也可用于数字签名系统, 是当前民用也是商业使用最广泛的公开密钥密码算法之一, 已被国际标准化组织ISO,JTU 和SWIFT 接受为标准.
随机选取两个不同的大素数p 和q （约为150位或更大的十进制数）, 计算它们的乘积M =pq 与相应的Euler 函数(Euler Totient Function )φ(n )=(p -1)(q -1)的值, 将公开, 而将φ(n ), p 和q 保密；显然, 如果不知道的素因子q 和p 的前提下, 计算φ(n )的值是属于NP 问题, 极难实现.
再随机选取一个正整数e , 是e 满足条件：e
-1
φ(N )最大共因素1）, 根据扩展Eulicd 算法计算d =e (mod φ(N )), 即计算满足
ed =1(mod (φ(M )))的d . 将e 公开, 而将d 保密, 就确定了RSA 算法的公开密钥
{(N , p , q , e , d )}
N =pq ,
PK =(e , N ), 私人密钥SK =(d , N ), 密钥空间：K =
p
与q 为不同大素数, ed =1(mod φ(N ))}.
相应地, RSA 算法中的单向陷门函数为f (x )=x t (mod N ), (其中t ∈K 且
x ∈Z N , 称为RSA
函数. 其秘密陷门信息为φ(N )及素数p , q 的值. 确实公钥
PK =(e , N )和私钥SK =(d , N )之后, RSA 算法的机密运算定义为：
c =E pk (m )=m
e
(mod N ), 其中为1≤m ≤N -1明文.
解密运算定义为：m =D sk (c )=c d (mod N )其中1≤c ≤N -1为密文.
RSA
秘密算法的明文m 应为1到N -1之间的整数, 即m ∈[1, N -1]' 如果明文
s
m 太长, 可将其转换成N 进制的形式, 即m =m s N
+m s -1N
S -1
+... +m 1N +m 0,
于
是得到分组后的明文序列m =(m 0, m 1,..., m s ), , 其中m i ∈[1, N ], 0≤i ≤s , 与之相应的密文序列为c =(c 0, c 1,... c s ), 其中c i 对应于m i (0≤i ≤s ).
中国剩余定理是初等数论中重要的基本定理之一, 它主要是刻画剩余系的结构和求解形如x =d i mod p i )(1≤i ≤s )的一次同余式方程. 在计算数论中, 计算中国剩余定理唯一解的方法有两种：单基数转换法和混合技术转换法, 这两种防范都是非常实用的计算方法.
算法一 CRT 的单基数转换法（SRC ） (1)计算p ←p 1p 2... p s 和p i ←p
-1
p i
(1≤i ≤s );
(2)计算Q 1←P 1(mod p i ), (1≤i ≤s );
(3)计算唯一解x ←d 1P 1Q 1+d 2P 2Q 2+... +d s P S Q s (mod P ).
利用混合技术转换法（MRC ）求CRT 的唯一解的方法是H . L . G arner 在1958年首先提出的. 之后D . E . K unth 将其用于计算数论, 并进行了有益的改进. 经过
D . E . K unth
改进后的MRC 方法用算法描述如下：
算法二 CRT 的混合基数转换法（MRC ） (1)计算B ji ←P J (mod P i ), (1≤j ≤i ≤s ); (2)分别计算
v i ←d 1(mod p i );
v 2←(d 2-v 1)B 12(mod p 2); ......
v s ←(d s -(v 1+p 1(v 2+p 2(v 3+... +p s -2v s -1))))B 1s B 2s ... B (s -1)s (mod p s ).
(3)计算唯一解X ←v s p s -1... p 2p 1+... +v 3p 2p 1+v 2p 1+v 1'
利用中国剩余定理对RSA 密码解密, 首先要将RSA 的解密运算由计算模N 的指数形式转化成求解同余式方程组的情形. 为此, 先介绍两个必须的数论定理
定理1 （中国剩余定理的推论） 设p 1, p 2,..., p s 是s 个两两互素的正整数,
P =p 1p 2... p 3, 则同余式f (x )≡0(mod p )与同余式方程组 f (x )≡0(mod p i )(1≤i ≤s )等价.
定理2（费马小定理） 设q 是一个素数, x 是一个满足x (mod p )≠0的整数, 则：x p -1≡1(mod p ).
算法三 RSA 的SRC 解密算法
(1)计算d 1←(mod p -1)与d 2←d (mod q -1); (2)计算C 1←c (mod p )C 2←c (mod q ); (3) 计算M 1←C 1d (mod p )M 2←C 2d (mod q )
1
2
(4)计算B 1←q -1(mod p )B 2←p -1(mod q ); (5)计算m ←M 1B 1q +M 2B 2p (mod M ). 4.5 在生活中的应用
在日常生活中我们所注意到的不是某些数, 而是这些数除某一固定的数所得到的余数. 例如, 假定现在是早上10点, 在两个小时前是几点? 我们立刻可得到正确答案是早上八点, 那么过了13个小时候又是几点呢? 算式为10+13-12=11即晚上11点; 在28个小时候手表的时针又是什么情况呢? 算式为（10+28）-（12⨯3）=2即是两点.
解决此类问题的方法是:若现在的事件是A , 问经过B 小时后的时间, 只需计算A +B ≡c (mod 12), 余数就是手表的时针数. 5 结束语
本文通过对中国剩余定理的描述阐述, 对中国剩余定理（孙子定理）在实际生活中的应用进行了初步的说明和描述. 以上只是一些简单的例子, 但足可见中国剩余定理应用之广泛, 地位之高, 作为数学史上名垂百世的成就, 其数学思想一直启发和指引着历代数学家.
致谢
历时将近两个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了. 尤其要强烈感谢我的论文指导老师—王众杰老师，他对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的修改和改进. 另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助. 在此向帮助和指导过我的各位老师表示最中心的感谢！
感谢这篇论文所涉及到的各位学者. 本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文的写作.
感谢我的同学和朋友，在我写论文的过程中给予我了很多你问素材，还在论文的撰写和排版灯过程中提供热情的帮助.
由于我的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正！
参考文献
《孙子算经》, 《张邱建算经》, 《夏侯阴算经导读》, 湖北教育出[1]纪志刚编：版社, 1999年.
[2]田金兵, 严政, 刘合国. 关于中国剩余定理[J ] . 湖北大学学报, 2006,28
（4）:325-327
《广义中国定理及其Maple 解法》, 重庆大学学报, 2004年. [3]冯国锋：
《公钥密码学》, 哈尔滨黑龙江出版社, 1993年. [4]曹珍富：
[5]贺毅朝, 刘建芹, 陈伟海, 《中国剩余定理在RSA 解密中的应用, 河北省科学学
院报, 第20卷第3期, 2003年.
[6]匡正:组合数学习题精解[M ]. 哈尔滨：哈尔滨工业大学出版社，2005. [7]钟善基. 小学迎春杯数学竞赛指导讲座. 北京师范大学出版社.
Chinese remainder theorem induction and its application
REN Xiao-yan
College of Mathematics Science No:080414001
Tutor: WANG Zhong-jie
Abstract ：Chinese remainder theorem is also known as the Chinese Remainder Theorem and its mathematical thoughts in modern mathematics plays a very important role .This paper summarizes the Chinese Remainder Theorem and prove and gives the relevant classical example and based on the multinomial theorem congruence group, Olympic, assignment theorem, cryptography and application were discussed and analysis.
Key words: ChineseRemainder Theorem Congruence group Polynomial Cryptography