拓展欧几里得算法

密码中的数学系列——拓展欧几里得算法

题外话：前提摘要，“鸽了两个月左右，最近忙于各种比赛的爆零，实力还是太菜了，真的需要沉下心来学习了。先从复现新生赛开始，这篇就是复盘basectf2024得来的笔记”，和前一篇一起记下的笔记

上接欧几里得算法

现在我们来看一下拓展欧几里得算法

续上

有$g=r_n$ ，$r_{n-1}>r_n$

$$\begin{align*} r_{n-1}\cdot x_n~~~ +~~~ r_n\cdot y_n~~~~&=\gcd(r_{n-2},r_{n-1})\\ r_{n-2}\cdot x_{n-1} + r_{n-1}\cdot y_{n-1}&=\gcd(r_{n-3},r_{n-2})\\ \end{align*}$$

且$r_{i+2}$%$r_{i+1}=r_i$

$\Bigg\lceil{r_{n-1}=r_{n-3}\%r_{n-2}}\\r_{n-2}=r_{n-4}\%r_{n-3}$

则有

$$\begin{align*} g &=\gcd(r_{n-2},r_{n-1})\\ &= r_{n-1}\cdot x_n+r_n\cdot y_n \\ &=r_{n-1}\cdot x_n+(r_{n-2}\%r_{n-1})\cdot y_n \\ &=r_{n-1}\cdot x_n+[r_{n-2}-(r_{n-2}/r_{n-1})\cdot r_{n-1}]\cdot y_n \\ &=r_{n-1}\cdot x_n+r_{n-2}\cdot y_n-(r_{n-2}/r_{n-1})\cdot r_{n-1}\cdot y_n \\ &=r_{n-2}\cdot y_n+r_{n-1}\cdot [x_n-(r_{n-2}/r_{n-1})\cdot y_n ] \end{align*}$$

且有

$$g=\gcd(r_{n-3},r_{n-2})=r_{n-2}\cdot x_{n-1}+r_{n-1}\cdot y_{n-1}$$

则

$$\begin{align*} x_{n-1}&=y_n\\ y_{n-1}&=x_n-(r_{n-2}/r_{n-1})\cdot y_n \end{align*}$$

代码实现为

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = exgcd(b, a%b)
    return g, y, x - (a//b)*y

（代码来自Crypto系列——RSA（三） | NSSCTF）

推算稿纸