在前三十篇中，我们讨论的算法大多建立在图、序列、集合等数据结构之上。然而，有一类算法直接以整数为操作对象，利用数论的基本性质——整除性、同余性、素数分布——来构造加密、认证、哈希等安全机制。这类算法的正确性不依赖于启发式规则或近似保证，而是建立在严格的数论定理之上。本文将从最基础的欧几里得算法开始，逐步深入到扩展欧几里得算法、模逆元计算与线性同余方程求解，建立数论算法的基本工具箱。
一、欧几里得算法与复杂度分析
最大公约数（GCD）是数论中最基本的概念之一。给定两个非负整数 aa 和 bb，其最大公约数 gcd(a,b)gcd(a,b) 是能同时整除 aa 和 bb 的最大正整数。欧几里得算法以极其简洁的递归结构求解GCD，其正确性基于一个关键引理。
引理：若 a≥b>0a≥b>0，则 gcd(a,b)=gcd(b,a mod b)gcd(a,b)=gcd(b,amodb)。
证明概要：设 d=gcd(a,b)d=gcd(a,b)，则 d∣ad∣a 且 d∣bd∣b。由 a mod b=a−qbamodb=a−qb（其中 q=⌊a/b⌋q=⌊a/b⌋），知 d∣(a mod b)d∣(amodb)，故 dd 是 bb 和 a mod bamodb 的公因子。反之，设 d′=gcd(b,a mod b)d′=gcd(b,amodb)，则 d′∣bd′∣b 且 d′∣(a−qb)d′∣(a−qb)，进而 d′∣(qb+(a−qb))=ad′∣(qb+(a−qb))=a。因此 gcd(a,b)gcd(a,b) 和 gcd(b,a mod b)gcd(b,amodb) 互相整除，必然相等。
基于此引理，欧几里得算法的递归形式极为简洁：
gcd(a,b)={a若 b=0gcd(b,a mod b)若 b>0gcd(a,b)={agcd(b,amodb)若 b=0若 b>0
复杂度分析是本文的重点之一。设 a≥ba≥b。每次递归将 (a,b)(a,b) 替换为 (b,a mod b)(b,amodb)。注意到 a mod b<a/2amodb<a/2 当 b≤a/2b≤a/2 时显然成立；当 b>a/2b>a/2 时，a mod b=a−b<a/2amodb=a−b<a/2 同样成立。这意味着每经过两次递归，两个数中较大的那个至少减半。因此递归深度至多为 O(logmax(a,b))O(logmax(a,b))。每次递归的除法操作耗时 O(log2a)O(log2a)（若考虑大整数运算的位复杂度），总复杂度为 O(log3a)O(log3a)。对于适合机器字长的整数，单次除法为常数时间，总复杂度仅 O(loga)O(loga)。
二、扩展欧几里得算法
欧几里得算法告诉我们最大公约数是多少。但许多应用——尤其是模逆元计算——不仅需要知道 gcd(a,b)gcd(a,b) 的值，还需要将其表示为 aa 和 bb 的线性组合。具体而言，要求找到整数 xx 和 yy，使得：
ax+by=gcd(a,b)ax+by=gcd(a,b)
这一等式称为贝祖等式，满足该等式的 xx 和 yy 称为贝祖系数。扩展欧几里得算法在计算GCD的同时递推地求出这两个系数。
算法的推导基于递归假设。设在递归调用 gcd(b,a mod b)gcd(b,amodb) 中，我们已获得系数 x′x′ 和 y′y′，满足：
b⋅x′+(a mod b)⋅y′=gcd(b,a mod b)=gcd(a,b)b⋅x′+(amodb)⋅y′=gcd(b,amodb)=gcd(a,b)
将 a mod b=a−⌊a/b⌋⋅bamodb=a−⌊a/b⌋⋅b 代入：
b⋅x′+(a−⌊a/b⌋⋅b)⋅y′=gcd(a,b)b⋅x′+(a−⌊a/b⌋⋅b)⋅y′=gcd(a,b)
整理：
a⋅y′+b⋅(x′−⌊a/b⌋⋅y′)=gcd(a,b)a⋅y′+b⋅(x′−⌊a/b⌋⋅y′)=gcd(a,b)
因此，上一层递归的系数为 x=y′x=y′，y=x′−⌊a/b⌋⋅y′y=x′−⌊a/b⌋⋅y′。算法的非递归实现从底部向上迭代，始终保持这一递推关系。
扩展欧几里得算法的时间复杂度与欧几里得算法完全相同，仅为常数倍的差异。
三、模逆元的快速计算
在模算术中，若存在整数 xx 使得：
ax≡1(modn)ax≡1(modn)
则称 xx 为 aa 模 nn 的乘法逆元，记为 a−1 mod na−1modn。模逆元存在的充要条件是 gcd(a,n)=1gcd(a,n)=1，即 aa 与 nn 互质。
证明上述充要条件非常简单。若 gcd(a,n)=1gcd(a,n)=1，由扩展欧几里得算法可得 ax+ny=1ax+ny=1。模 nn 取同余，ax≡1(modn)ax≡1(modn)，故 xx 即为所求逆元。反之，若 aa 模 nn 存在逆元 xx，则 ax=1+knax=1+kn，即 ax−kn=1ax−kn=1，由贝祖等式知 gcd(a,n)gcd(a,n) 整除 11，故必为 11。
因此，计算模逆元的算法就是扩展欧几里得算法的一次调用。求得 xx 后，通常将其规约到 [0,n−1][0,n−1] 区间：a−1 mod n=(x mod n+n) mod na−1modn=(xmodn+n)modn。
当模数 nn 为素数 pp 时，费马小定理提供了另一种方法：ap−2 mod pap−2modp 即为 aa 的逆元。这可通过快速幂在 O(logp)O(logp) 时间内计算，但仅适用于素数模。扩展欧几里得算法对任意互质的 aa 和 nn 均适用，是最通用的模逆元算法。
四、线性同余方程的求解
一般形式的线性同余方程为：
ax≡b(modn)ax≡b(modn)
目标是求出所有满足该同余式的整数 xx（模 nn 意义下）。
求解过程分为三步。
第一步，计算 d=gcd(a,n)d=gcd(a,n)。若 d∤bd∤b，则方程无解。因为左侧 axax 模 nn 只能取到 dd 的倍数，而右侧 bb 不是 dd 的倍数时矛盾。
第二步，若 d∣bd∣b，将方程整体除以 dd：
ad⋅x≡bd(modnd)da⋅x≡db(moddn)
此时 gcd(ad,nd)=1gcd(da,dn)=1，adda 模 nddn 存在逆元。方程两端同乘该逆元，得：
x≡(ad)−1⋅bd(modnd)x≡(da)−1⋅db(moddn)
记此解为 x0x0，它是模 nddn 意义下的唯一解。
第三步，将解“提升”回模 nn。原方程在模 nn 下恰好有 dd 个互不同余的解：
x≡x0+k⋅nd(modn),k=0,1,…,d−1x≡x0+k⋅dn(modn),k=0,1,…,d−1
线性同余方程的求解算法完整展示了数论算法的设计范式：利用数论定理将问题转化为GCD检验与模逆元计算，算法步骤简单但正确性依赖于严谨的数学论证。
五、应用场景
数论基础算法在现代密码学中扮演着核心角色。
RSA密钥生成过程中，需要计算公钥指数 ee 模 φ(N)=(p−1)(q−1)φ(N)=(p−1)(q−1) 的逆元以得到私钥指数 dd。这一步直接调用扩展欧几里得算法。RSA的安全性部分依赖于扩展欧几里得算法的高效性——如果攻击者能快速计算 φ(N)φ(N)，就能同样快速地计算私钥。
在中国剩余定理的计算中，线性同余方程组的求解需要反复调用模逆元。具体而言，给定同余方程组 x≡ai(modni)x≡ai(modni)（其中 nini 两两互质），解的表达式中含有 Mi⋅(Mi−1 mod ni)Mi⋅(Mi−1modni) 的项，每个都需要一次扩展欧几里得算法。
Diffie-Hellman密钥交换和ElGamal加密体制虽然在密钥生成阶段依赖大素数和原根，但其解密步骤同样涉及模逆元的计算。可以说，扩展欧几里得算法是整个公钥密码基础设施中最频繁调用的子程序之一。
六、总结与展望
从欧几里得算法的对数级复杂度，到扩展形式的线性组合构造，再到模逆元与同余方程的求解，本文建立了一套完整的整数运算算法框架。这些算法的共同特征是：结构简洁、复杂度低、正确性依赖于数论定理的严格保证。
基于本篇奠定的基础，下一篇将进入素数检测与大整数分解的概率方法。Miller-Rabin素数测试如何以任意接近1的概率判定素数，Pollard Rho算法如何以期望平方根时间找到大整数的非平凡因子，将成为下一篇的核心议题。从理论到实践，数论算法的优雅与威力将持续展现。
