1、教学目标 理解 求最大公约数的算法 掌握 欧几里德公式 的推广 掌握 求解同余方程 的算法 掌握运用中国剩余定理解决实际问题 理解 双钥密码体制 概念 掌握 RSA算法（实验四）8.1最大公约数 定义 1 设 a， b是整数 ， b0，如果 存在整数 c，使得a=bc成立则称 a被 b整除， a是 b的倍数， b是 a的约数 (因数或除数 )，可记为 b|a；如果不存在整数 c使得a bc成立，则称 a不被 b整除，记为 。 定理 1(带余数除法 ) 设 a与 b是两个整数， b0，则 存在唯一的两个整数 q和 r， 使得 a=bq+r， 0r|b|。 定义 2 在定理 1的表达式 a=bq+
2、r中，称 q是 a被 b除的商 ， r是 a被 b除的 余数 。 最大公约数是指 两个或两个以上整数的 公共约数中最大者 。8.1.1欧几里德算法 欧几里德定理 任意给定两个整数 a， b（不妨假设 ab） 。它们的最大公约数用 gcd(a,b)表示， 则 gcd(a,b)=gcd(b,a mod b) ，其中 a mod b表示a被 b除所得的余数 欧几里德递归定义式 P249算法 应用举例（求 b=100和 a=210最大公约数）gcd(100,210mod100)=gcd(100,10)=gcd(10,100mod10)=10。 欧几里德递归公式的推广 （ P250算法设计 ） 解决 “
3、已知 a, b求解一组 x， y使得 ax+by=gcd(a, b) ”问题 令 gcd(a, b)=d，则 ax+by=d； gcd(b,a mod b)=d (8-1) （ 1） 当 b=0时，则 gcd(a,b)=a； ax+by=a，即 ax=a，则x=1， y取任意实数。简单起见，算法取 y=0； （ 2） 当 b0时，令 a=b， b=a mod b，则 gcd(a, b)=d， ax+by=d。 由于 b=a mod b = ，则 ax+by=bx+( )y= ay +b(x - )=d (8-2) 让式 (8-1)和式 (8-2)对应项相等，则 x=y， y= x - 。8.1
4、.2 Stein算法 当 a,b很大时 （超出计算机表示能力），欧氏算法复杂， 最好不用 除法 和 取模 运算 。 基于的两条结论 （ 1） gcd(a,0)=a。 （ 2） gcd(ka,kb)=kgcd(a,b) 算法步骤 步骤 1：初始时，令 c=1； 步骤 2： 如果 a=0， c=b*c；如果 b=0， c=a*c； 算法结束。 步骤 3：令 a1=a， b1=b； 步骤 4： a和 b奇偶性的判断。如果 a和 b都是偶数，则 a=a/2， b=b/2， c=2*c；如果 a是偶数， b不是偶数，则 a=a/2；如果 b是偶数， a不是偶数，则 b=b/2；如果 a和 b都不是偶数，
5、则 a =|a1 b1|，b=min(a1,b1)；转步骤 2。P251算法 应用举例 求 15和 9的最大公约数解： c=1,a1=15,b1=9 a=6,b=9 a=3,b=9 a1=3,b1=9 a=6,b=3 a1=3,b1=3 a=0,b=3 c=b*c=38.2同余方程 同余式 设 a、 b和 m为整数，其中 m 0。若 a和 b被 m除得的余数相同，则称 a和 b对模 m同余 。记为 或 同余式的简单性质 （ 1）若 a b(m)，则 m|(b-a)。反过来，若 m|(b-a)，则 a b(m)； （ 2）如果 a=km+b(k为整数 )，则 a b(m)； （ 3）每个整数恰与
6、 0,1, ， m-1这 m个整数中的某一个对模m同余； （ 4）同余关系是一种 等价关系 ： 反身性 a a(m)； 对称性 a b(m)，则 b a(m)，反之亦然； 传递性 a b(m)， b c(m)，则 a c(m)。 （ 5）如果 a b(m)， x y(m)，则 a x (b y)(m); 特别地 。 例 1：求使 2n+1能被 3整除的一切自然数 n 例 2：求 2999最后两位数码 P252 同余方程 设 是整系数多项式， m是正整数，称 f(x) 0(mod m) (8-4)是 关于未知数 x的模 m的同余方程 ，简称为模 m的同余方程。若 则称式 (8-4)为 n次同余方程 同余方程的解 设 x0是整数，当 x x0时式 (8-4)成立，则称 x0是同余方程 (8-4)的解。 凡对于模 m同余的解，被视为同一个解，最多 m个解。 一次同余方程 设 a， b为整数，且， a 0 mod m， 则称同余方程ax b(mod m) (8-5)为 一次同余方程 。 定义 7 设 a1,a2,an 是非零整数， b是整数，称关于未知数 x1,x2, xn的方程a1x1+a2x2+ anxn=b是 n元一次不定方程。 定理 3 一次同余方程 有解的充要条件 是gcd(a,m)|b。若有解，则恰有 d=gcd(a， m)个解。 一次同余方程的求解步骤
