高中数学选修53(密码学算法基础)数学与密码学6-省公开课一等奖全国示范课微课金奖课件

密码学概论密码学数学基础（四）第1页★本讲讲课提要★（1）中国剩下定理（2）费马小定理（3）欧拉定理第2页★本讲讲课提要★（1）中国剩下定理（2）费马小定理（3）欧拉定理第3页★中国剩下定理★中国剩下定理发觉和发展韩信是汉高祖刘邦手下大将，他英勇善战，智谋超群，为汉朝建立了卓绝功劳。听说韩信数学水平也非常高超，他在点兵时候，为了保住军事机密，不让敌人知道自己部队实力，先令士兵从1至3报数，然后记下最终一个士兵所报之数；再令士兵从１至５报数，也记下最终一个士兵所报之数；最终令士兵从1至7报数，又记下最终一个士兵所报之数；这么，他很快就算出了自己部队士兵总人数，而敌人则一直无法搞清他部队终究有多少名士兵。第4页★中国剩下定理★中国剩下定理发觉和发展这个故事中所说韩信点兵计算方法，就是现在被称为“中国剩下定理”一次同余式解法。它是中国古代数学家一项重大创造，在世界数学史上含有主要地位。

最早提出并记叙这个数学问题，是南北朝时期数学著作《孙子算经》中“物不知数”题目。第5页★中国剩下定理★中国剩下定理发觉和发展“物不知数”题目是这么：

“今有物不知其数：三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这个问题普通称孙子问题。“今有一些物不知其数量。假如三个三个地去数它，则最终还剩二个；假如五个五个地去数它，则最终还剩三个；假如七个七个地去数它，则最终也剩二个。问：这些物一共有多少？”第6页★中国剩下定理★中国剩下定理发觉和发展《孙子算经》中记载了这个问题解法，有些人将其解法编成歌诀：“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。”它意思是用3除剩下数乘70，用5除剩下数乘21，用7除剩下数乘15，将所得结果相加再减去105倍数，即可得所求数。算式是2×70＋3×21＋2×15=233，233－105×2＝23，所以，最小正整数解是23。第7页★中国剩下定理★中国剩下定理发觉和发展《孙子算经》实际上是对下面同余方程组总结出一套经验解法。x≡a1(mod3)x≡a2(mod5)x≡a3(mod7)经验公式：x=70a1+21a2+15a3-105k第8页★中国剩下定理★中国剩下定理发觉和发展《孙子算经》“物不知数”题即使开创了一次同余式研究先河，但因为题目比较简单，甚至用试猜方法也能求得，所以尚没有上升到一套完整计算程序和理论高度。真正从完整计算程序和理论上处理这个问题，是南宋时期数学家秦九韶。秦

九韶在他《算术九章》中提出了一个数学方法“大衍求一术”，系统地叙述了一次同余式组解法基本原理和普通程序。第9页★中国剩下定理★中国剩下定理发觉和发展秦九韶为何要把他这一套计算程序和基本原理称为“大衍求一术”呢？这是因为其计算程序关键问题是要“求一”。所谓“求一”，通俗地说，就是求“一个数多少倍除另一个数，所得余数为一”。那么为何要“求一”呢？第10页★中国剩下定理★中国剩下定理发觉和发展我们能够从“物不知数”题几个关键数字７０、２１、１５中找到以下规律：70是5和7倍数，但被3除余1；21是3和7倍数，但被5除余1；15是3和5倍数，但被7除余1；任何一个一次同余式组，只要依据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出第11页★中国剩下定理★中国剩下定理完整正式版设是两两互素正整数，则一次同余方程组对模M有唯一解其中ei满足第12页★中国剩下定理★中国剩下定理用途中国剩下定理是数论中最有用一个工具，定理说假如已知某个数关于一些两两互素数同余方程，就能够重构这个数。换句话说，中国剩下定理能够用于求解同余方程组。同时中国剩下定理提供了一个非常有用特征，即在模M下可将非常大整数x由一组两两互素小整数来表示。第13页★中国剩下定理★中国剩下定理应用——求同余方程组举例：已知下面同余方程组，求x第14页★中国剩下定理★中国剩下定理应用——求同余方程组第一步：求MM=2×3×5×7＝210第二步：求M1=105,M2=70,M3=42,M4=30第15页★中国剩下定理★中国剩下定理应用——求同余方程组第三步：求eiei满足即ei是在模mi条件下乘法逆元素使用观察法求得乘法逆元素以下e1=1,e2=1,e3=3,e4=4第16页★中国剩下定理★中国剩下定理应用——求同余方程组第四步：第17页★练习★1.求解下面同余方程组X≡1(mod2)X≡2(mod3)x≡1(mod5)x≡2(mod7)第18页★本讲讲课提要★（1）中国剩下定理（2）费马小定理（3）欧拉定理第19页★费马定理★费马定理假如p是素数，a是正整数，且gcd(a,p)=1，那么ap-1≡1(modp)费马定理另一个形式假如p是素数，a是任意正整数，则对gcd(a,p)=1，有ap≡a(modp)第20页★费马定理★费马定理主要用途——快速寻找素数通常情况下，假如2n-1≡1(modn)，那么n为素数。之所以是“通常情况下”，是因为有例外比如2560≡1(mod561)，但561=3×11×17但这种“例外”并不多见。例：a=7,p=19,求ap-1modp第21页★费马定理★费马定理主要用途——快速寻找素数模以2为底幂运算有很快迭代算法，加之满足2n-1≡1(modn)n为素数可能性较大，那么就能够以此为基础设计寻找素数算法。选择初始n0，然后依次检验接下来奇数n>n0，看是否满足2n-1≡1(modn)，假如满足，则采取复杂素数判定算法做深入检验。这种算法比因数分解法快得多。第22页★本讲讲课提要★（1）中国剩下定理（2）费马小定理（3）欧拉定理第23页★欧拉定理★欧拉函数欧拉函数φ(m)表示比m小且与m互素正整数个数。以m=24为例，比24小而与24互素正整数为1,5,7,11,13,17,19,23。所以，φ(24)=8。第24页★欧拉定理★欧拉函数性质（1）m是素数时，有φ(m)=m-1因为与m互素数有1,2,…,m-1共m-1个。（2）m=pq，且p和q均是素数时，有φ(m)=φ(p)φ(q)=(p-1)(q-1)（3）若m和n互素，则φ(m×n)=φ(m)×φ(n)（4）若p是一个素数，则φ(pe)=pe-pe-1例：

φ(21)=