经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 其他 » 网络安全 » 查看文章
欧几里得算法与扩展欧几里得算法
来源:cnblogs  作者:童话Bluebells  时间:2021/1/25 11:09:52  对本文有异议

欧几里得算法

欧几里得算法,也叫辗转相除,简称 gcd,用于计算两个整数的最大公约数

  定义 gcd(a,b) 为整数 a 与 b 的最大公约数

给定整数a和b,且b>0,重复使用带余除法,即每次的余数为除数去除上一次的除数,直到余数为0,这样可以得到下面一组方程:
a = bq1+r1, 0 < r1 <b,
b = r1q2+r2, 0 < r2 < r1,
r1 = r2q3+r3, 0 < r3 < r2,
……
rj-1 = rjqj+1
最后一个不为0的余数rj就是a和b的最大公因子

求gcd (19701066)
用欧几里德算法的计算过程如下:
19701×1066+904
10661×904+162
9045×162+94
162=1×94+68
941×68+26
682×26+16
261×16+10
161×10+6
101×6+4
6=1×4+2
42×2+0
因此gcd (19701066) = 2

 

 

 扩展欧几里得算法

1.能够确定两个正整数的最大公约数
2.如果这两个正整数互素(互质),还能确定他们的逆元

如果整数n≥1,且gcd(a,n)=1,那么a有一个模n的乘法逆元a-1。即对小于n的正整数a,存在一个小于n的整数a,存在一个小于n的整数a-1,使得a * a-1≡1 mod n。

 

 

 (1)1234 mod 4321 用扩展欧几里德算法的计算过程如下:

循环次数 Q X1 X2 X3 Y(T1) Y(T2) Y(T3)
初始值 - 1 0 4321 0 1 1234
1 3 0 1 1234 1 -3 619
2 1 1 -3 619 -1 4 615
3 1 -1 4 615 2 -7 4
4 153 2 -7 4 -307 1075 3
5 1 -307 1075 3 309 -1082 1

- 1082 =3239 mod 4321,所以逆元是 3239

(2)24140 mod 40902

循环次数 Q X1 X2 X3 Y(T1)
Y(T2) Y(T3)
初始值 - 1 0 40902 0 1 24140
1 1 0 1 24140 1 -1 16762
2 1 1 -1 16762 -1 2 7378
3 2 -1 2 7378 3 -5 2006
4 3 3 -5 2006 -10 14 1360
5 1 -10 14 1360 13 -19 646
6 2 13 -19 646 -36 52 68
7 9 -36 52 68 326 -487 34
8 2 326 -487 34 -688 1026 0

无逆元

 

原文链接:http://www.cnblogs.com/Bluebells/p/14295919.html

 友情链接: NPS