扩展欧几里德算法求逆元

扩展欧几里德算法求逆元假设正整数an且gcd(a,n)=1，则模方程a-1modn=1有唯一解。求解过程如下：n=a*q0+r0a=r0*q1+r1r0=r1*q2+r2……r1=r2*q3+r3，r3=1则r3=1=r1–r2*q3=r1–(r0–r1*q2)*q3=(q2*q3+1)*r1–q3*r0=(q2*q3+1)*(a–r0*q1)–q3*r0=(q2*q3+1)*a–((q2*q3+1)*q1+q3)*r0=(q2*q3+1)*a–((q2*q3+1)*q1+q3)*(n-a*q0)=((q2*q3+1)+((q2*q3+1)*q1+q3)*q0)*a–((q2*q3+1)*q1+q3)*n因此，a模n的逆元为：((q2*q3+1)+((q2*q3+1)*q1+q3)*q0)。主要思路：通过反向迭代替换掉扩展算法中后续出现的余数，将最大公约数表示为n和a的线性组合：gcd(a,n)=n*x+a*y=1，则y即为所求a模n之逆元。举例：求12模67的逆元。由于gcd(12,67)=1，故其逆元存在且唯一。列表求解如下：iSTQR06712571127152751235221当R=1时过程终止，进行反向代入得到：1=5–2*2=5–(7–5*1)*2=3*5–2*7=3*(12–7*1)–2*7=3*12–5*7=3*12–5*(67–12*5)=28*12–5*67因此，12模67的逆元为28。验证：12*28=336，336mod67=1。