扩展欧几里得算法求逆元

最近经常会遇到RSA的题目，都会用到扩展欧几里得算法来求逆元，所以去系统的学习了一下这个算法的原理。 先奉上dalao的博客 https://blog.sengxian.com/algorithms/gcd-extgcd

前置说明

a | b 表示：a可以整除b

用途

扩展欧几里得算法是用来求解方程$ax+by=c(a,b,c\in Z)$的

可解条件

$gcd(a,b)|c$

实现

记 exgcd(a, b, x, y) 为求解方程 $ax+by=gcd(a,b)$ 的函数

先考虑边界情况： 当b = 0时，有 ax = gcd(a, 0) 解得$\{\begin{array}{rl}x& =1\\ y& =0\end{array}$ 对于一般情况，设 $a^{{}^{\prime }}=a$, $b^{{}^{\prime }}=a\%b$ 则有： $$a^{{}^{\prime }}{x}^{{}^{\prime }}+b^{{}^{\prime }}{y}^{{}^{\prime }}=gcd(a^{{}^{\prime }},b^{{}^{\prime }})=gcd(b,a\%b)$$

恒定条件：$gcd(a,b)=gcd(b,a\%b)$

又有：$$gcd(a,b)=ax+by$$ 所以有： $$ax+by=a^{{}^{\prime }}{x}^{{}^{\prime }}+b^{{}^{\prime }}{y}^{{}^{\prime }}$$ $$a^{{}^{\prime }}{x}^{{}^{\prime }}+b^{{}^{\prime }}{y}^{{}^{\prime }}=b{x}^{{}^{\prime }}+(a\%b)y^{{}^{\prime }}=b{x}^{{}^{\prime }}+(a-└\frac{a}{b}┘b)y^{{}^{\prime }}=a{y}^{{}^{\prime }}+b(x^{{}^{\prime }}-└\frac{a}{b}┘y^{{}^{\prime }})$$ $$ax+by=a{y}^{{}^{\prime }}+b(x^{{}^{\prime }}-└\frac{a}{b}┘y^{{}^{\prime }})$$ 所以在迭代过程中有: $$\{\begin{array}{rl}x& =y^{{}^{\prime }}\\ y& =x^{{}^{\prime }}-└\frac{a}{b}┘y^{{}^{\prime }}\end{array}$$

至此扩展欧几里得算法的过程结束，那么这东西跟求逆元有什么关系呢？ 对于一个整数x，其逆元$x^{{}^{\prime }}$需要满足：$x{x}^{{}^{\prime }}\equiv 1(\%b)$ 那么一定存在：$x{x}^{{}^{\prime }}=kb+1$ 将该方程转化为：$ax-kb=1$ 再令 $y=-k$ 转化为：$ax+by=1$ 则该方程的解x即为我们要求的逆元

def exgcd(a, b): if b == 0: return 1, 0, a x, y, gcd = exgcd(b, a % b) return y, x - a // b * y, gcd def get_inv(a, b): x, y, gcd = exgcd(a, b) if gcd == 1: return (x % b + b) % b else: raise Exception("不存在逆元")