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

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

欧几里得算法

又称辗转相除法

已知有整数a，b（不妨设a>b），$g=\gcd(a,b)$

有

$$a = k_1\cdot b+r_1\\ r_1=a\%b$$

（$k_1$为任意整数，$r_1$为a%b的余数）

两边同时除以整数g，得

$$\frac{a}{g}=k_1\cdot\frac{b}{g}+\frac{r_1}{g}$$

因为g是a，b的最大公因数（$g|a$ 且 $g|b$），即$\frac{a}{g}$，$\frac{b}{g}$都是整数

根据上式，整数之间的加减乘运算，那么$\frac{r_1}{g}$也是整数，即g 也是$r_1$的因子，而且$a = k_1\cdot b+r_1\to$ （$a>b>r_1$），g是a，b的最大公因数，那么g也是$r_1$的最大公因数。

欲求a，b的最大公因数，即求b与$r_1$的最大公因数。（$a>b>r_1$，数值减小）

继续，$b=k_2\cdot r_1+r_2$，同理g是$r_2$的最大公因数 （$r_2=b\%r_1$）

此时，我们列出我们得到的这两个式子看看

$$\begin{align*} a&=k_1\cdot b+r_1\\ b&=k_2\cdot r_1+r_2 \end{align*}$$

那么等式右边第一项（原来b的位置）的数会越来越小，逐渐靠近0，到0就是这个递归的边界（$b`=0 $）。

最终

$$\begin{align*} a&=k_1\cdot b+r_1\\ b&=k_2\cdot r_1+r_2\\ r_1&=k_3\cdot r_2+r_3\\ &……\\ r_{n-1}&=k_{n+1}\cdot r_n+0……①\\ r_{n}&=k_{n+2}\cdot 0+g \end{align*}$$

递归：递归的本质是归约，把一个困难的问题转化为另一个简单的问题，且这个简单问题和前者是同一个问题，那么我们称为归约。

递归流水线：

$$\begin{align*} \gcd(a,b)&=\gcd(b,r_{1})\\ &=\gcd(r_1,r_2)\\ &=\gcd(r_2,r_3)\\ &……\\ &=\gcd(r_{n-1},r_n)\\ &=\gcd(r_n,0)\\ \end{align*}$$

而因为0除以任何数都为一个整数0，那么所有数都是0的因子（$\frac{0}{k}=0\to $$k|0$）。

则$\gcd(r_n,0)=r_n$，$r_n$与0的最大公因数就是$r_n$本身。

代码实现

def gcd(a, b):
    # 递归边界情况：如果b为0，返回a
    if b == 0:
        return a
    # 否则，递归调用 gcd(b, a % b)
    return gcd(b, a % b)

推导稿纸