扩展欧几里得求逆元步骤(手动+python求解)
学RSA的时候自己重新理解了一下扩展欧几里得,根据常见求逆元的相关代码,稍微总结了一下步骤,就分享出来叭~
例子:701^(-1) mod 1848=?
换言之,也就是701×?-1848×k=1,k是系数,问号?即为701模1848的逆元.
Step 1 先用辗转相除法“求”701和1848的最大公因数gcd
为什么这个求要加双引号呢?因为最大公因数有这样一条性质:
设整数a,b不同时为零,则存在一对整数m,n,使得gcd(a.b) = am+bn
因此不用求也知道这两个数的gcd必然为1,否则无法求出逆元,我们要做的只是把求到1的过程列出来,方便后面用扩展欧几里得~
过程如图:
Step 2 推出相邻式子关系
根据
gcd(a,b) = gcd(b,a%b)
已知:
gcd(a,b)=ax+by
a%b=a-(a//b)*b  //指取商的整数部分
gcd(b,a%b) = bx’+(a-(a//b)*b)*y’ = ay’+b(x’– a//b*y’)
推得:
x = y’
y = x’ – a//b*y’
(其中x,y所在式子的下一条是x’,y’)
Step 3 扩展欧几里得
从Step 1中最后得到的1和0我们可以列出a*1+b*0=gcd(a,b)=1这一式子,再根据Step 2推得的x=y’可以一步一步往上代入,以此类推,从而推出每一步的因子x和y,顺序如下(从最底下往上推):
推到刚开始的1848和701后,我们得到y为29,即为所求的逆元.
注意:如果得到的y为负数,需要取模才能得到逆元.
容易验证:701×29 = 1 (mod 1848)
以下为python代码:
1 | def ext_gcd(a, b): #扩展欧几里得算法 |
以上述数据为例:
1 | ext_gcd(1848,701) |
完结撒花~!
参考链接
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Leland's Blog!