下载文档原格式
中国剩余定理文章-回复中国剩余定理是一个数论中重要的定理，它被广泛应用于密码学、计算机科学以及通信等领域。
本文将以"中国剩余定理"为主题，详细介绍这一定理的含义、原理和应用。
一、引言中国剩余定理是古老而又精妙的数论问题之一。
它最早由我国古代数学家孙子所发现，被称为“孙子定理”。
孙子定理后来由中国数学家秦九韶进行了更加深入的研究和推广，因此也被称为“秦九韶定理”。
后来，西方的数学家们将其命名为中国剩余定理。
中国剩余定理是一个非常重要的数论定理，它解决了模运算中的一类复杂问题，并得到了广泛的应用。
二、数论的基本概念在介绍中国剩余定理之前，我们先了解一些基本的数论概念。
在数论中，我们经常碰到关于求余数的问题。
例如，当我们把一个数除以3时，有可能余数是0、1或2。
这种情况下，我们可以用数学符号表示为a ≡b (mod n)，其中a是被除数，b是余数，n是模数。
如果两个数满足这个关系，我们称它们是模n同余的。
三、中国剩余定理的原理中国剩余定理是一种基于同余关系的数论定理，它可以用来解决模n同余的问题。
具体而言，中国剩余定理告诉我们，如果给定了一组两两互质的模数，那么可以通过求解模数的一组同余方程来得到原方程的解。
换句话说，中国剩余定理帮助我们将原问题转化为一组相对简单的方程。
四、中国剩余定理的应用中国剩余定理在密码学和计算机科学中得到了广泛应用。
例如，在RSA 公钥加密算法中，中国剩余定理被用来加速密钥生成和解密过程。
在RSA 算法中，需要对大素数进行模n同余的计算，中国剩余定理的应用大大提高了计算效率。
此外，中国剩余定理还被用于解决模运算的扩展问题。
例如，我们可以利用中国剩余定理来求解模4、模3和模5的同余式，并得到一组解，用于解决一些问题。
中国剩余定理的应用不仅仅限于数论领域，在通信技术、电路设计等方面也有重要的应用。
五、范例让我们通过一个简单的例子来进一步理解中国剩余定理的应用。
中国剩余定理及其应用Chinese Remainder Theorem and Its Application专业:作者:指导老师:摘要本文主要讨论了中国剩余定理及其应用, 文中研究了中国剩余定理在初等数论范畴下的应用及在密码学方面的贡献, 说明了中国剩余定理的应用的广泛性.关键词: 中国剩余定理; 初等数论; RSA算法; 解密AbstractThe paper discusses the Chinese Remainder Theorem and Its Application. It studies the application in the context of Elementary Number Theory and the contributions in cryptography, and it illustrates the broad application of Chinese Remainder Theorem.Keywords:Chinese Remainder Theorem; Elementary Number Theory; RSAalgorithm; decrypt目录摘要 (I)ABSTRACT (II)0 引言 (1)1 中国剩余定理 (1)2 中国剩余定理的应用 (2)2. 1 中国剩余定理在赋值领域的体现 (2)2. 2 中国剩余定理在多项式中的应用 (3)2. 3 中国剩余定理在密码学中的应用 (4)3结束语 (11)参考文献 (12)0 引言中国剩余定理源于我国古代《孙子算经》, 其中有一题: “ 今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何？” 这就是求解一次同余式组:()()()⎪⎩⎪⎨⎧≡≡≡7mod 25mod 33mod 2x x x《孙子算经》中给出最小正整数解23, 解法传至今世. 中国剩余定理又称“孙子定理”. 它数初等数论中重要定理之一, 在代数数学和计算机领域中也有重要应用. 本文讨论中国剩余定理及其一些简单的应用.1 中国剩余定理中国剩余定理:设r m m m ,,,21 是两两互素的正整数, 设r a a a ,,,21 使整数, 则同余方程组 r i m a x i i ,,2,1),(mod =≡ 模r m m m M 21=有唯一解∑==ri i i i M y M a x 1mod其中i i m M M =, i i i m M y mod 1-=, r i ,,2,1 =.举世闻名的中国剩余定理最早以“ 物不知其数” 的问题载于《孙子算经》[1]中, 该问题可以理解为: 一个数除以3余2, 除以5余3, 除以7余2, 求合适这些条件的最小的自然数. 用现代数学符号表示, 即已知)7(mod 2)5(mod 3)3(mod 2≡≡≡N 求最小的正整数, 答案是23=N .《孙子算经》的解法是:“ 术曰: 三三数之剩二, 置一百四十; 五五数之剩三, 置六十三; 七七数之剩二, 置三十; 并之, 得二百三十三, 以二百一十减之即得.凡三三数之剩一, 则置七十;五五数之剩一, 则置二十一, 七七数之剩一, 则置十五. 一百六以上, 以一百五减之即得.”把“物不知其数”问题推广到一般情况[2], 设d c b a ,,,为非负整数, 且a 为某个数除以3的余数, b 为这个数除以5的余数, c 为这个数除以7的余数, 试求符合条件的最小的数m . 按《孙子算经》的解法有d c b a m 105152170-++=.我们可以证明, 因为d c b a m 105152170-++=可以改写为 c d c b a m +-++=)105152169(.又因为)105152169(3d c b a -++且20≤≤a , 所以m 除以3的余数必为a , 同理可得m 除以5的余数必为b , m 除以7的余数必为c . 又因为[]1057,5,3=, 所以m 减去105的整数倍就能得到符合题意的最小自然数.2中国剩余定理的应用中国定理是中国古代数学家为世界数学发展作出的巨大贡献, 它的数学思想在近代数学、当代秘密学研究及日常生活都有着广泛应用.2. 1中国剩余定理在赋值理论中的体现赋值理论是域论的一个分支, 是研究近代数学中几个重要分支如代数数论、交换数论的一个重要工具, 而中国剩余定理在赋值论中起着重要作用, 下面介绍中国剩余定理在赋值理论中的应用.定理 (赋值的独立性)对于任意n 个p 赋值pn p p V V V ,,,21 , Q a ∈, n i ,,2,1 =,以及任意0>ε, lm l l P P P ,,,21 --, 则存在Q b ∈使(1)()ε<-=-∞1a b a b V ; (2)()i l i i pi P a b V -≤-, n i ,,2,1 =证明 设m 为n a a a ,,,21 的最小公分母, 令()m V P pi Si i =, i i i s l r +=, n i ,,2,1 =,{}n r r r r ,,,,1max 21 =. 根据中国剩余定理, 可求得一个c , 使得()r p ma c 11mod ≡, ()r pr ma c 22mod ≡, , ()rnn p ma c mod ≡ 即 ()r i i pi p ma c V -≤-, i l i i pi p a m c V -≤⎪⎭⎫⎝⎛-设()rn p p p q 21=, 取适当的Z v u ∈,, 使ε<-++a vq uq m c 11, 再令a vquqm c =++11, 则b 显然满足条件(1).又由p 距离p D 的性质: ()()()()c a D c b D b a D p p p ,,,,max ≥有()i l i i pi i pi p a m c m c b V a b V -≤⎭⎬⎫⎩⎨⎧⎪⎭⎫ ⎝⎛-+⎪⎭⎫ ⎝⎛-=≤-max , n i ,,2,1 =.2. 2 中国剩余定理在多项式中的应用由中国剩余定理可得相似定理. 设()()()x m x m x m n ,,,21 是n 个两两互素的多项式,()()()x a x a x a n ,,,21 是n 个多项式, 则一定存在多项式, 使()()()()()()()()()()()()⎪⎪⎩⎪⎪⎨⎧≡≡≡x m x a x f x m x a x f x m x a x f n n mod mod mod 2211当()x f 的次数不超过()()()()()()x m x m x m x m x m n 21=的次数是, ()x f 唯一确定.特别地, 当()[]x Q b x x m i i ∈-=(或[]x R ), n i ,,2,1 =, ()n i b i ,,2,1 =是互不相等的常数, 从而()()n i x m i ,,2,1 =也是两两互素的多项式, 由余数定理可知()()()()i i i i b x b m x m -≡mod , ()n i ,,2,1 = 从而定理可叙述为, 一定存在多项式()x f , 是()()()()()()()()()()()()⎪⎪⎩⎪⎪⎨⎧-≡-≡-≡n n n b x m x a x f b x m x a x f b x m x a x f mod mod mod 222111其中()x a i ()n i ,,2,1 =是任意给定的常数, 且多项式()x f 在次数不超过n 的条件下唯一确定的, 有()()()i i b x a x f -≡mod 等价于()i i a b f ≡()n i ,,2,1 =得: 对任意互不相同的i b()n i ,,2,1 =存在唯一的次数小于n 的多项式()x f , 是()i i a b f ≡()n i ,,2,1 =. 这就是插值多项式的存在与唯一性定理.由中国剩余定理的证法, 只要找到多项式()x M i ()n i ,,2,1 =, 使()()()i i b x x M -≡mod 1 ()()()j j b x x M -≡mod 0, j i ≠ (1) 而()()()()()()()()()n i i i i i i n i i i b b b b b b b b b x b x b x b x x M --------=+-+-111111 满足(1), 于是的插值多项式()x f :()()()()()()()∑∏==≠--=+++=nj ni i ji j n n j i b bb x a x M a x M a x M a x f 112211这就是著名的Lagrange 内插多项式.中国剩余定理推导出的内插多项式是处理许多多项式问题的基本工具如简化数列求和问题: 计算()22221210-++++n解 假设和为n 的三次多项式()n f , n 代表项数, 于是有 ()()()()53,12,01,00====f f f f 由插值公式得()()()()()()()()()()()()()()()()()()()12161231303210532120231051004321--=-----++------=⋅+⋅+⋅+⋅=n n n n n n n n n n M n M n M n M n f 所以, ()()()1216112102222--=-++++n n n n .中国剩余定理主要是解决一次同余式问题, 在算术中还可以利用它来检查因数和验算整数计算的结果.2. 3中国剩余定理在密码学中的应用中国剩余定理虽是数论中的基本定理, 但是在计算机秘密学中有着重要的应用. 例如在Rabin 密码算法中用于解密运算. 在RSA 密码算法中, 中国剩余定理同样可用于RSA 的解密运算, 而且使RSA 的机密速度大约提高4倍左右, 这无论对于软件还是硬件实现RSA 密码算法都是非常重要的. 本文主要从基于中国剩余定理的一种加密算法和中国剩余定理在RSA 解密中的应用两点来说.2. 3. 1基于中国剩余定理的一种加密算法根据中国剩余定理, 可以得出一种新的网络信息加密算法. n A A A A ,,,,321 为n 个互质的素数, 若已知一个整数Y 除以n A A A A ,,,,321 余数分别为n B B B B ,,,,321 , 求Y .令n A A A A M ⨯⨯⨯⨯= 321,1X 表示能n A A A ,,,32 被n A A A ,,,32 整除的所有整数,1Y 表示能被n A A A ,,,32 整除的所有整数且除以1A 余1B 的所有整数, 2X 表示能被n A A A ,,,31 整数的所有整数,2Y 表示能被n A A A ,,,31 整数的所有整数且除以2A 余2B 的所有整数,i X 表示能被n i i A A A A A A ,,,,,,,11321 +-整除的所有整数,i Y 表示能被n i i A A A A A A ,,,,,,,11321 +-整除的所有整数且处于i A 余i B 的所有整数,那么1321/A m M A A A X n ⨯=⨯⨯⨯= , 2312/A m M m A A A X n ⨯=⨯⨯⨯⨯= ,n n n A m M m A A A X /121⨯=⨯⨯⨯⨯=- , 其中m 为任意整数.设i F 满足i X 和i Y , 且令其为i Y 中最小的正整数, 其中n i ≤≤1则 m M F m A A A F Y n ⨯+=⨯⨯⨯⨯+=12111m M F M A A A F Y n n n n ⨯+=⨯⨯⨯⨯+= 21那么m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321.用Y 表示明文, 是所要隐蔽和保护的机要消息. 用n B B B B ,,,,321 表示密文, 要把明文转换成一种隐蔽的形式: n A A A A ,,,,321 和N 为密钥.加密算法的步骤如下:步骤1: 选出n 个n A A A A ,,,,321 作为“密钥”; 步骤2: 求出这n 个素数的乘积M ; 步骤3: 求出n F F F F ,,,,321 ;步骤4: 由m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321得出 ()[]M F F F F Y N n /321++++-= ;步骤5: 用Y 分别除以n A A A A ,,,,321 得余数n B B B B ,,,,321 并把它们作为密文. 解密算法的步骤如下:已知密文n B B B B ,,,,321 和密钥n A A A A ,,,,321 和N 算出n F F F F ,,,,321 . 由m M F F F Y Y Y Y Y n n ⨯++++=++++= 21321得出Y . 这样就实现了从密文和密钥到明文的整个解密过程. 加密和解密举例: 加密:令明文2001=X , 密钥为11,7,5, 密文为10,6,1可求出175,55,231321===F F F , 那么()[]()41175/175552312001=⨯⨯++-=m 为另一密钥.解密:2001411755517522121321=⨯⨯⨯+++=⨯++++=++++=m M F F F Y Y Y Y Y n n .2. 3. 2中国剩余定理在RSA 解密中的应用1978年美国麻省理工学院的三位教授R. L. Rivest, A. Shamir 和M. Adleman 提出了一种基于因子分解的指数函数作为单项陷门函数[3](One-way Trapdoor Function)的公开密钥密码算法(Public-Key Cryptosystems, PKC), 即著名的RSA 算法[4]. RSA 算法是第一个较完善的PKC 算法, 也是非常容易理解和实现的的PKC 算法. 它既可用于传输信息的加密, 也可用于数字签名系统, 是当前民用也商业使用最广泛的公开密钥密码算法之一, 已被国际标准化组织ISO 、JTU 和SWIFT 接受为标准.随机选取两个不同的大素数p 和q (约为150位或更大的十进制数), 计算它们的乘积pq N =与相应的Euler 函数(Euler Totient Function)()()()11--=q p n φ的值, 将N 公开, 而将()n φ, p 和q 保密;显然, 如果不知道N 的素因子p 和q 的前提下, 计算()n φ的值是属于NP 问题, 极难实现.再随机选取一个正整数e , 是e 满足条件: ()N e φ<且()()1,gcd =N e φ(即e 与()N φ的最大共因素是1), 根据扩展Eulicd 算法(Extended Euclidean Algorihm)[5]计算()()N e d φmod 1-=, 即计算满足()()N ed φmod 1=的d . 将e 公开, 而将d 保密, 就确定了RSA 算法的公开密钥()N e PK ,=, 私人密钥()N d SK ,=, 密钥空间:(){}pq N d e q p N K ==,,,,, p 与q 为不同大素数, ()()N ed φmod 1=.相应的, RSA 算法中的单向陷门函数为()()N x x f t mod =(其中K t ∈且N Z x ∈), 称为RSA 函数. 其秘密陷门信息为()N φ及素数p 、q 的值.确定公钥()N e PK ,=和私钥()N d SK ,=之后, RSA 算法的机密运算定义为: ()()N m m E c e pk mod ==, 其中11-≤≤N m 为明文.解密运算定义为: ()()N c c D m d sk mod ==, 其中11-≤≤N c 为密文.RSA 秘密算法的明文m 应为1到1-N 之间的整数, 即[]1,1-∈N m . 如果明文m 太长, 可将其转换成N 进制的形式, 即0111m N m N m N m m s s s s ++++=-- , 于是得到分组后的明文序列 ()s m m m m ,,,10 =, 其中 []1,1-∈N m i , s i ≤≤0. 与之相应的密文序列为()s c c c c ,,,10 =, 其中1c 对应于1m ()s i ≤≤0.中国剩余定理(Chinese Remainder Throrem, CRT)是初等数论中重要的基本定理之一, 它主要是刻画剩余系的结构和求解形如()()s i p d x i i ≤≤≡1mod 的一次同余式方程. 在计算数论中, 计算中国剩余定理唯一解的方法有两种: 单基数转换法(Single-Radex Conversion, SRC)和混合技术转换法(Mixed-Radex Conversion, MRC), 这两种防范都是非常实用的计算方法.算法1 CRT 的单基数转化法(SRC)(1)计算s p p p P 21←和()s i p P P i i ≤≤←1/;(2)计算()()s i p P Q i ≤≤←-1,mod 111;、 (3)计算唯一解()P Q P d Q P d Q P d x s s s mod 222111+++← .利用混合技术转换法(MRC)求CTR 唯一解得方法是H. L. Garner 在1958年首先提出的. 之后D. E. Kunth 将其用于计算数论, 并进行了有益的改进. 经Kunth 改进后的MRC 方法用算法描述如下:算法2 CRT 的混合基数转换法(MRC) (1)计算()i j ji p p B mod ←, ()s i j ≤<≤1; (2)分别计算()i p d v mod 11←; ()()212122mod p B v d v -←;()()()()()()s s s s s s s s s p B B B v p v p v p v d v mod 1211232211---++++-← .(3)计算唯一解112123121v p v p p v p p p v X s s ++++←- .利用中国剩余定理对RSA 密码解密, 首先要将RSA 的解密运算由计算模N 的指数形式转化成求解同余方程组的情形. 为此, 先介绍两个必须的数论定理: 即中国剩余定理的一个推论(定理1)于费马小定理(Fermat's Little Theorem).定理1(CRT 的推论)[6, 7]设s p p p ,,,21 是s 个两两互素的正整数, s p p p P 21=, 则同余式()()P x f mod 0≡与同余式方程组()()()s i p x f i ≤≤≡1mod 0等价.定理2(费马小定理)[6, 7]设p 使一个素数, x 是一个满足()0mod ≠p x 的整数, 则:()p x p mod 11≡-.下面, 将着重分析利用SRC(算法1)和MRC(算法2)实现的RSA 解密算法. 对于RSA 的解密算法()()N c c D m d sk mod ==, 由于用于私钥()N d SK ,=的合法解密者已知pq N =(p 和q 为不同的素数), 因此根据定理1, 可将RSA 的解密由计算模N 的指数运算()()N c c D m d sk mod ==转化为计算模p 和模q 的同余式方程组:()()⎪⎩⎪⎨⎧≡≡q c m p c m d dmod mod 21 (2. 1) 而d 和c 通常是不小于p (或q )的, 因此可利用定理2及同余式的性质, 简化同余式方程组(2. 1)的模p (或q )的指数运算.事实上, 根据定理2及同余式的性质, 同余式()p c m d mod 1=可以如下简化: 令()1mod -=p d r , 则存在k 满足: ()r p k d +-=1. 于是()()()()()()()()p c p c p c c p c p c m r kp r p k r p k d mod mod mod mod mod 1111--+-≡≡≡=()()()()()()p p c p c p c p d p d r k mod mod mod mod 11m od 1m od --≡≡≡同理对于同余式()q c m d mod 2≡有()()()()()()q q c q c q c m q d q d d mod mod mod mod 1m od 1m od 2--≡≡≡最终, 同余式方程组(2. 1)转化为:()()()()⎪⎩⎪⎨⎧≡≡,mod mod mod mod 2121q q c m p p c m d d (2. 2)其中()()1mod ,1mod 21-=-=q d d p d d .于是, RSA 的解密运算转化为解同余式方程组(2. 2). 利用算法1(即SRC)解之, 即得到下面的快速RSA 解密算法.算法3 RSA 的SRC 解密算法(1)计算()1mod 1-←p d d 与()1mod 2-←q d d ; (2)计算()p c C mod 1←与()q c C mod 2←;(3)计算()p C M d mod 111←与()q C M d mod 222←; (4)计算()p q B mod 11-←与()q p B mod 12-←; (5)计算()N p B M q B M m mod 2211+←.同样地, 可利用改进的混合基数计算法(MMRC)(即算法2)解同余式方程组(2. 2). 首先, 构造三角形数值表:222111M M M其中111m M =, 221m M =,()()()()()()q q p m m q q p M M M mod mod mod mod 1121112122---=-=, 再由MMRC(算法2)得到:()()()[]p q q p m m m m *-+=-mod mod 1121 . 这样就得到另一个快速RSA 解密算法. 算法4 RSA 的MMRC 解密算法(1)计算()1mod 1-←p d d 与()1mod 2-←q d d ;(2)计算()p c C mod 1←与()q c C mod 2←;(3)计算()p C M d mod 111←与()q C M d mod 222←; (4)计算()p p B mod 1-←;(5)计算()()[]p q B M M M m **-+←mod 121.由于算法3和算法4的(1)-(3)相同, 因此只需比较它们的后两步. 对于算法3, 需要计算2次逆元、1次加法和1次模余(2k 比特)运算;而对于算法4, 需要计算1次逆元、2次惩罚、1次加法、1次减法和1次模余(k 比特)运算. 显然, 算法4的后两步的计算量比算法3的少一半(加法与减法的计算量相对减少, 忽略不计), 因此明显好于算法3. 利用MMRC 的解密算法(即算法4)使RSA 的解密速度加快大约4倍, 可大大提高用于RSA 的软硬件解密实现.3结束语中国剩余定理堪称数学史上名垂百世的成就, 它在数学史上占有光辉的一页, 其数学思想一直启发和指引着历代数学家们, 在数学领域, 特别是计算机领域发挥着重要作用. 以上只是它应用的一些例子, 可见中国剩余定理的应用之广泛, 地位之高.致谢 本文是在。
文章编号:1001 - 9383 (2003) 03 - 0138 - 06Ξ中国剩余定理在RSA 解密中的应用贺毅朝1 ,刘建芹2 ,陈维海3( 11 石家庄经济管理学院信息工程系,石家庄050000 ;21 石家庄信息工程职业学院,石家庄0500353 . 中国华融资产管理公司石家庄办事处, 石家庄050000)【摘要】在分析RSA 密码算法实现原理的基础上,着重论述了利用单基数转换法( SRC)和混合基数转换法( M R C) 计算中国剩余定理惟一解的方法以及利用这两种方法快速实现RSA 的解密算法。
【关键词】P KC 算法; 中国剩余定理; RSA 算法【中图分类号】T P 311 . 56 ;O156 【文献标识码】 AThe a ppl i cat i on of CRT to R SA decrypt i onHE Y i2chao 1 ,LI U J ian2qin2 ,CHE N Wei2hai3( 1 . Col l ege of I nf or m at i on En g i neeri n g , S hij i a z h u a n g U ni versi t y of Econ nom i cs , S hij i a z h u a n g 050000 , Chi n a ;2 . S hij i a z h u a n g I nf or m at i on En g i neeri n g V ocat i on al Col l ege , S hi j i a z h u a n g 050035 , Chi n a ;3 . S hi j i a z h u a n g Of f ice of Chi n a Hu a r on g A s sets M a n age m ents Corporat i on , S hij i a z h u a n g 050000 , Chi na) Abstract Based o n analysis of t h e p r inciple of RSA implementati o n ,t h e applicati o n issues of Sin2 gle2Radix C o nversi o n ( SRC) and Mixed2Radix C o nversi o n ( M RC) algo rit h ms o n Chinese Rem ain2 der Theo re m ( CR T) and high2speed realizati o n of RSA decryp ti o n using above met ho ds were il lu2 minated em p h atically.K ey w ords P KC algo r it h m ; Chinese Re mainder Theo r e m (CR T) ; RSA algo r it h m1978 年美国麻省理工学院的三位教授R. L . Rivest ,A. Shamir 和M . Ad leman 提出了一种以基于因子分解的指数函数作为单向陷门函数1 (One2way Trap d oor Functio n) 的公开密钥密码算法( Pub lic2Key Cryp to syst em , P KC) ,即著名的RSA 算法2 。
RSA加密算法的研究作者：李莹赵瑞曹宇张天宇刘霏凝来源：《智能计算机与应用》2020年第03期摘要：随着互联网和通信技术的发展，信息安全问题日益受到重视，基于数据加密的信息安全技术得到了迅速的发展。
数据加密就算法而言，分为对称加密和非对称加密两类。
RSA是应用最广泛的非对称算法之一，具有安全性高、易于实现等特点，但运算速度很慢，只能用于一些少量数据。
针对RSA运算效率慢的问题，提出了中國剩余定理和蒙哥马利模乘法相结合的方法来优化模幂，用三素数代替传统的二重素数。
实验结果表明，优化算法具有较高的速度和可行性。
关键词： RSA; 中国剩余定理; 蒙哥马利模乘法【Abstract】 With the development of Internet and communication technology， more and more attention has been paid to information security.In terms of algorithm， data encryption can be divided into symmetric encryption and asymmetric encryption.RSA is one of the most widely used asymmetric algorithms， and has the characteristics of high security， being easy to implement， but the operation speed is very slow， which can only be used for some small amount of data encryption.In order to solve the problem of slow arithmetic efficiency of RSA， a method combining Chinese residual theorem and Montgomery modular multiplication is proposed to optimize modular power and replace traditional double prime number with triple prime number. Experimental results show that the optimization algorithm has high speed and feasibility.【Key words】 ;RSA;Chinese remainder theorem; Montgomery model multiplication0 引言随着计算机技术的不断发展，互联网上共享的数据量有了显著增长。
中國剩餘定理台師大數學研究所碩士班研究生楊瓊茹一、前言在遊覽數學史這座寶山時，一幅幅數學風景呈現眼前，令人心曠神怡。
尤其是一些非常有趣的發現，總是帶給我們意外的驚喜！例如：中國《孫子算經》中的『物不知數』與義大利《算盤書》中的『一次同餘組』這兩者對比下的相似性，就是很值得進一步討論的問題。
在空間、時間差距甚大的場景下，它們竟有著『幾乎一致』的內容，其中是否有數學文化的交流？或者是歷史的巧合，是各自數學知識獨立的發展？甚至是否源於另一個數學文化？產生什麼影響？諸如這樣的問題，也往往引起數學史家的注意及興趣。
此外，我們也發現到其他相當具有特色的『物不知數』題型，例如數學詵歌、『翦管術』和『天算頌』。
在本篇文章的最後部分，我們嘗詴著將『物不知數』給予數學延拓。
對於『物不知數』和『一次同餘組』此種類型的問題，南宋秦九韶(1202-1261) 的一般化解法和德國數學家高斯(Gauss) 於1801年所發表的剩餘定理相同，因此，西方國家稱此類型的問題為『中國剩餘定理』(The Chinese Remainder Theorem)。
底下，我們將開始這趟數學之旅！二、文本對比首先，引述中國《孫子算經》中『物不知數』的文本內容：1今有物不知其數，三三數之賸二，五五數之賸三，七七數之賸二，問物幾何？答曰︰二十三術曰：三三數之賸二，置一百四十；五五數之賸三，置六十三；七七數之賸二，置三十。
并之得二百三十三。
以二百一十減之，即得。
凡三三數之賸一，則置七十，五五數之賸一，則置二十一，七七數之賸一，則置十五。
一百六以上，以一百五減之，即得。
再看《算盤書》中的『一次同餘組』︰2Let a contrived number be divided by 3, also by 5, also by 7; and ask each time what remains from each division. For each unity that remains from the division by 3, retain 70; for each unity that remains from the division by 5, retain 21; and for each unity that remains from the division by 7, retain 15. And as much as the number surpasses 105, subtract from it 105; and what remains to you is the contrived number. Example: suppose from the division by 3 the remainder is 2; for this you retain twice 70, or 140; from which you subtract 105, and 35 remains. From the division by 5, the remainder is 3; for which you retain three times 21, or 63, which you add to the above 35; you get 98; and from the division by 7, the remainder is 4, for which you retain four times 15, or 60; which you add to the above 98, and you get 158; from which you subtract 105, and thee remainder is 53, which is the contrived number.3面對這兩則文本，我們先嘗詴著用現代數學符號表示︰《孫子算經》的『物不知數』︰ N ≡2 (mod3)≡3 (mod5)≡2 (mod7)⇒N ＝70×2＋21×3＋15×2－105×2＝23 ； 《算盤書》的『一次同餘組』︰ N ≡2 (mod3)≡3 (mod5)≡4 (mod7)⇒N ＝(70×2－105)＋21×3＋15×4－105＝53 兩者共同都有的解題概念︰ N ≡1R (mod3)≡2R (mod5)≡3R (mod7)⇒N ＝70×1R ＋21×2R ＋15×3R －105T ,其中T 是使N 為最小正整數的數。
