密码学算法 - 欧几里得算法 | Alice and Bobの神秘小屋

本章节我们将深入探讨欧几里得算法（Euclidean Algorithm），这是一个古老而又强大的工具，用于计算两个整数的最大公约数（GCD）。这个算法不仅在数学领域有着重要的地位，更是密码学中不可或缺的基础算法之一。

在密码学中，我们常常使用这个算法完成对裴蜀定理的解决，计算模逆元，以及在一些加密算法中进行关键的数论运算。通过理解欧几里得算法的原理和实现，我们可以更好地掌握密码学中的许多核心概念。

欢迎来到《密码学核心算法实战》的欧几里得算法专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

欧几里得算法的原理 😋

欧几里得算法基于一个重要的性质：对于两个整数 $ a $ 和 $ b $，如果 $ a > b $，那么

$\text{gcd}(a, b) = \text{gcd}(b, a \mod b)$

这个性质告诉我们，两个数的最大公约数等于较小的数和较大的数对较小的数取模后的结果的最大公约数。通过不断地将较大的数替换为较小的数和它们的余数，我们可以快速找到最大公约数。

欧几里得算法的实现 🤨

下面是欧几里得算法的一个简单实现：

def gcd(a, b):
    # a, b = max(a, b), min(a, b)
    # 先确保 a >= b，简化后续循环逻辑（也可以省略这一步，循环本身能处理）
    while b != 0: # 当b不为0时，不断用余数替换，直到b为0
        a, b = b, a % b
    return a

裴蜀定理与扩展欧几里得算法 🥰

裴蜀定理（Bézout’s Identity）是整数关系中的一个重要定理，它告诉我们对于任意两个整数 $ a $ 和 $ b $，存在整数 $ x $ 和 $ y $，使得性质：

$ax + by = \text{gcd}(a, b)$

扩展欧几里得算法（Extended Euclidean Algorithm）就是基于裴蜀定理的一种算法，它不仅可以计算最大公约数，还可以找到满足裴蜀定理的整数 $ x $ 和 $ y $。

扩展欧几里得算法的原理 🙃

操作步骤也是这样的，证明的时候顺便就是算法的步骤了。

设 $ d = \text{gcd}(a, b) $。
用辗转相除法：

$\begin{align*} a = bq_1 + r_1 ， 0 < r_1 < b \\ b = r_1q_2 + r_2 ， 0 < r_2 < r_1 \end{align*}$

不断进行下去，直到余数为 0：

$\begin{align*} r_{n-2} = r_{n-1}q_n + r_n ， 0 < r_n < r_{n-1} \\ r_{n-1} = r_nq_{n+1} + 0 ， r_n = d \end{align*}$

最后余数为 0，说明 $ r_n = d = \text{gcd}(a, b) $。

反向替换求解 $ x $ 和 $ y $

倒数第二步：

$d = r_n = r_{n-2} - r_{n-1}q_n$

再把$r_{n-1}$用上一行表示：

$r_{n-1} = r_{n-3} - r_{n-2}q_{n-1}$

往回带入：

$d = A \cdot r_{n-2} + B \cdot r_{n-3}, A ,B \in \mathbb{Z}$

一直往上带入，最终可以表示为：
$d = x \cdot a + y \cdot b$，其中 $ x, y \in \mathbb{Z} $

扩展欧几里得算法的实现 🤪

下面是扩展欧几里得算法的一个简单实现：

def extended_gcd(a, b):
    # 递归终止条件：当a=0时，gcd就是b，此时等式为0*x + b*y = b，解为x=0, y=1
    if a == 0:
        return b, 0, 1
    # 递归调用：把问题规模缩小，计算 gcd(b%a, a) 及其对应的解x1, y1
    # 此时满足：(b%a)*x1 + a*y1 = gcd(b%a, a) = gcd(a, b)
    gcd, x1, y1 = extended_gcd(b % a, a)
    # 核心推导：将 b%a 替换为 b - (b//a)*a，推导当前层的x和y
    # 替换后：(b - (b//a)*a)*x1 + a*y1 = gcd
    # 整理得：a*(y1 - (b//a)*x1) + b*x1 = gcd
    # 因此当前层的x = y1 - (b//a)*x1，y = x1
    x = y1 - (b // a) * x1
    y = x1
    # 返回当前层的gcd和对应的x、y
    return gcd, x, y

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import xgcd # sage环境中才生效
g, x, y = xgcd(a, b) # 直接获得 x·a + y·b = g 的解

怎么样，是不是非常简单？🤣👉🤡

上一章：密码学算法 - 前言 👈
下一章：密码学算法 - 中国剩余定理CRT 👈
回到开始：关于我 👈

相关链接：
密码学数学基础 - 整数关系 👈