扩展欧几里得算法这名字听起来像是个只会在数学竞赛和密码学课本里出现的东西但实际上我工作这些年发现它的出场频率远比想象中高做算法题求模逆元、写安全相关逻辑算 RSA 私钥、甚至解一个简单的不定方程找整数解翻来覆去绕不开它。教材上通常就甩给你一段递归代码加一句“设 axbygcd(a,b)回溯求出整数解 x,y”然后就没然后了。等你真正上手用的时候各种坑就冒出来了x 是负数怎么办gcd 不整除 c 方程还有没有解递归里 x 和 y 传参为什么是反着的迭代写法又该怎么对应数学过程这篇文章我把自己从入门到实际项目里用这套算法的完整经验梳理了一遍包括原理推导、递归和迭代两套实现、求模逆元和解不定方程的完整流程再配上 RSA 私钥计算和中国剩余定理这两个工程里最典型的场景。代码给全案例给足你照着抄就能跑跑完就知道为什么每一步要这么写。1. 从欧几里得算法说起扩展到底扩展了什么1.1 先聊聊老祖宗留下的求 gcd 套路欧几里得算法本身很简单核心就一句话gcd(a, b) gcd(b, a mod b)。反复套用这个等式把两个数越滚越小直到某个数变成 0另一个数就是最大公约数。我拿 252 和 105 举例子252 2 × 105 42 105 2 × 42 21 42 2 × 21 0所以 gcd(252, 105) 21。这个算法的好处是效率极高每轮至少让较大的数缩小一半整体复杂度是 O(log min(a, b))哪怕两个数都是几十位的长整数也就是几百次除法的事儿这也是为啥它能进 RSA 这类大数运算场景。但传统欧几里得算法有个“性格缺陷”它只告诉你最大公约数是多少完全不关心这些余数是怎么一步步组合出来的。打个比方你只知道一堆食材最后炖出了一锅汤但每样食材放了多少、先后顺序是什么它一概不管。实际工程和数学问题里我们经常需要的不只是“gcd 是多少”而是“gcd 能不能用原来的 a 和 b 线性组合出来组合系数是多少”。这就是扩展欧几里得算法存在的意义。1.2 扩展出来的核心能力一组黄金系数扩展欧几里得算法要解决的问题是给定两个整数 a 和 b求整数 x 和 y使得a × x b × y gcd(a, b)这个等式叫裴蜀定理Bézouts identity它保证只要 gcd(a, b) 能被某个数整除那对应系数的整数解就一定存在。扩展欧几里得算法的本质就是在跑一遍标准欧几里得算法的过程中把每一轮的商记下来最后逆着推回去把最大公约数重新写成 a 和 b 的线性组合。我继续用 252 和 105 演示。从最后一步往上回溯21 105 - 2 × 42 105 - 2 × (252 - 2 × 105) 5 × 105 - 2 × 252所以 exgcd(252, 105) 得到的一组系数是 x -2y 5验证一下252 × (-2) 105 × 5 -504 525 21完全正确。注意 x 是负数这不是 bug这是常态。后面所有“负数怎么规范化”的讨论根源都在这里。1.3 这套算法到底能用在哪儿我盘点了一下实际开发里最常见的几类场景求模逆元解 ax ≡ 1 (mod m)这是 RSA、ElGamal 这类公钥密码算法的地基操作。解线性丢番图方程形如 ax by c 求整数解工程里设计找零、资源分配这类整数规划问题会碰到。中国剩余定理实现解同余方程组时需要求多个模数下的逆元一步一个 exgcd。分数模运算、组合数取模、以及各种数论算法内部的基础模块。可以说扩展欧几里得跟快速幂、素数筛一样属于数论工具箱里的“基础款工具”不会它后面一堆算法都施展不开。2. 数学推导为什么回溯能求出系数2.1 核心递推式的完整推导理解扩展欧几里得关键是抓住一个递推关系。设我们在某一步要算 exgcd(a, b)按欧几里得算法的套路下一步要算 exgcd(b, a mod b)。假设我们已经知道了后者的结果b × x (a mod b) × y gcd(b, a mod b)而 gcd(b, a mod b) gcd(a, b)所以等号右边不变。接下来把 a mod b 展开a mod b a - ⌊a/b⌋ × b代回上面的等式b × x (a - ⌊a/b⌋ × b) × y gcd(a, b)把含 b 的项合并一下a × y b × (x - ⌊a/b⌋ × y) gcd(a, b)对比目标式 a × x b × y gcd(a, b)系数就一目了然了x y y x - ⌊a/b⌋ × y这就是为什么递归实现里要把 x 和 y 交换着传进去再在回溯时做一次减法。如果你理解了这个推导后面看代码就不会觉得“传参为什么是反的”很玄学了那正是为了保证回溯后的 x 取到下一层的 y。2.2 终止条件与回溯过程拆解递归的终止条件是 b 0。此时 gcd(a, 0) a等式变成 a × x 0 × y a显然取 x 1y 0 就行。这是唯一一组“拍脑袋”定出来的初始值剩下的全靠回溯一层层修正。我还是用 252 和 105 完整走一遍递归过程把每一层的中间结果列出来你就能看到系数是怎么“长”出来的递归层传入 (a, b)回溯后的 x回溯后的 y验证第 1 层(252, 105)-25252×(-2)105×521第 2 层(105, 42)2-1105×242×(-1)21第 3 层(42, 21)0142×021×121第 4 层(21, 0)1021×10×021从最后一行往上走每一层的系数都保持“a 乘 x 加 b 乘 y 等于 21”这个不变量。这就是回溯法的精妙之处不变量贯穿始终每层只做 O(1) 的算术总复杂度依然是 O(log min(a, b))。2.3 系数的数量级与时间复杂度很多人担心一个问题递归回溯这么多次系数会不会爆炸式增长实测下来完全不用担心。可以证明回溯过程中 x 和 y 的绝对值都不会超过 max(a, b) 的数量级更精确地说|x| ≤ b / (2 × gcd(a, b))|y| ≤ a / (2 × gcd(a, b))大致量级。所以在 64 位整数范围内使用只要 a、b 本身不超范围系数一般也不会溢出。不过这里有个前提如果你在循环里反复用乘法更新系数比如我后面讲的迭代写法中间过程确实有溢出风险实操时用 long long 是个好习惯Python 这种大整数语言则完全没这个顾虑。3. 代码实现递归、迭代与细节打磨3.1 递归实现与传参顺序的坑递归版本最简洁也最贴近数学推导。我用 C 写一版long long exgcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long g exgcd(b, a % b, y, x); y - a / b * x; return g; }这段代码里唯一反直觉的点就在递归调用exgcd(b, a % b, y, x)把当前帧的 y 当作下一层的 x 传进去把当前帧的 x 当作下一层的 y 传进去。结合上一节的推导就清楚了回溯后我们需要 x y、y x - ⌊a/b⌋ × y而递归返回后下一层的 x、y 分别落在了当前帧的 y、x 里正好对上公式。我见过不少人手写这个版本时漏掉 y 的更新或者把减法写成加法结果算出来怎么验都不对。我的建议是写完立刻用一组小数据验证比如 exgcd(252, 105)预期得到 g21, x-2, y5。把这一步当成单元测试写进代码里之后怎么改都不怕。3.2 迭代实现与数学过程的对应递归虽然好写但在极端情况下a、b 相差巨大递归深度达到几十层也可能让人心里没底而且某些语言环境递归栈开销大。迭代写法则完全避免了这个问题。关键思路是维护两组系数分别对应“当前余数”和“上一个余数”的线性表示def exgcd_iter(a, b): # 初始化始终维护 a*x0 b*y0 当前余数 x0, y0 1, 0 # 当前余数初始为 a x1, y1 0, 1 # 上一个余数初始为 b while b: q a // b a, b b, a % b # 同步更新两行系数 x0, x1 x1, x0 - q * x1 y0, y1 y1, y0 - q * y1 return a, x0, y0我拿 a 30, b 12 验证一遍30 × 1 12 × 0 30当前余数 3012 × 0 30 × 0不对一步步来。初始 x01,y00 对应 30x10,y11 对应 12。第一轮 q2新余数 30 mod 12 6而 6 30 - 2×12所以要用“旧 30 的系数”减去 q 倍“旧 12 的系数”也就是 x0 x1 0, x1 1 - 2×0 1y0 y1 1, y1 0 - 2×1 -2。现在 30×0 12×1 12? 不对这里的对应关系要仔细捋一下。其实迭代写法里每次循环x0、y0 表示的是“新的更小的那个数”即新余数如何由原始 a、b 组合出来x1、y1 表示的是“被减掉的较大的那个数”即旧的 b如何组合出来。刚才第一轮后新余数 6 a×1 b×(-2)带入 30×1 12×(-2) 6对的。而旧 b 12 a×0 b×1也对。第二轮 q2新余数 12 mod 6 06 12 - 2×6此时更新系数最终返回的 a6, x01, y0-2验证 30×1 12×(-2) 6完美。只要保证“每轮结束时x0,y0 组合出当前 a”代码就不会出错。这个版本我建议在 C、Java、Python 里都存一份遇到递归深度恐惧症的时候直接换用。3.3 细节打磨负数处理、溢出防护与返回值约定实际工程中输入不一定都是正整数。比如求模逆元时a 和 m 可能出现在某些边界场景里带着负数进来。标准的扩展欧几里得算法对负数也能跑只是系数符号会变得很难看而且中间的取模运算在 C 里对负数是向零取整跟数学定义不一致容易出隐蔽 bug。我的统一做法是进函数前先把 a、b 都转成正数记录符号最后再把符号作用到结果上。具体到求模逆元这种场景更常见的做法是直接用(a % m m) % m把 a 规整到 [0, m-1] 再调函数这样省心得多。另外凡是用 64 位整数的场景我建议所有参与运算的变量一律 long long乘法中间结果用__int128或者 Python 的大整数兜底别在这种地方省溢出排错的时间成本远高于换类型的一秒钟。返回值约定也要提前定好我的习惯是函数返回 gcdx、y 通过引用带出。这样调用方一眼就能判断 gcd 是否为 1、是否满足可逆条件不用额外传指针判断成败。4. 核心应用一模逆元的完整求解4.1 模逆元是什么、什么时候存在模逆元的定义很直白给定 a 和模数 m如果存在整数 b 使得 a × b ≡ 1 (mod m)那 b 就叫 a 在模 m 下的逆元记作 a⁻¹。说白了就是在模世界里跟 a 相乘等于 1 的那个数。这个操作在 RSA 私钥计算、组合数取模、哈希一致性哈希环等场景到处都是。存在条件是一条硬规则只有当 gcd(a, m) 1即 a 与 m 互质时逆元才存在。原因也不难理解a × b 1 k × m 移项就是 a × b - k × m 1根据裴蜀定理左边能表示的最小正整数正好是 gcd(a, m)所以 gcd 必须是 1。这也意味着如果你算出来的 gcd 不是 1直接放弃别试图硬凑数学上就不可能有解。4.2 用扩展欧几里得求模逆元完整案例回到方程本身求 a 在模 m 下的逆元等价于解 a × x m × y 1。调用一次 exgcd(a, m) 得到 xx 就是逆元。这里有个小坑x 可能是负数而逆元的习惯表示是 [0, m-1] 里的正整数所以需要规范化long long mod_inverse(long long a, long long m) { long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) { return -1; // 不存在模逆元 } x (x % m m) % m; // 关键把负数规范到 [0, m-1] return x; }我举一个具体的数字例子方便你对照验证求 17 在模 3120 下的逆元。调用 exgcd(17, 3120)会得到一组 x -367y 2你可以用上面的代码跑一下或者手推一遍因为 17 × (-367) 3120 × 2 1。规范化后d (-367 % 3120 3120) % 3120 2753验证一下17 × 2753 4680146801 mod 3120 1完全正确。这个例子不是随便编的它就是经典的 RSA 小参数案例我后面在 RSA 那一节还会用到 2753 这个数。4.3 为什么费马小定理不能通吃很多人会问求逆元不是还能用费马小定理吗a^(m-2) mod m 一步幂运算就出来了为什么要费劲写扩展欧几里得答案是适用条件不同。费马小定理的前提是模数 m 必须是素数这在很多工程场景里是硬伤。比如 RSA 里计算私钥时用的模数是 φ(n)它几乎不可能是素数又比如你只想求 5 在模 12 下的逆元12 不是素数a^(12-2) 那条路直接不成立。扩展欧几里得对任意互质的 a、m 都成立而且复杂度 O(log min(a, m)) 比快速幂 O(log m) 在常数上更小因为每次迭代只有除法和减法。所以除非你 100% 确定模数是素数否则我建议一律用扩展欧几里得一条路走到底。5. 核心应用二线性丢番图方程5.1 有解条件与特解计算形如 ax by c 的方程要求 x、y 都是整数这就是线性丢番图方程。工程里遇到“要把总量 c 拆成 a 和 b 两种规格的整数份”这类问题本质上就是在解这种方程。第一步先算 g gcd(a, b)。方程有整数解的充要条件是 g 整除 c理由还是裴蜀定理那条线ax by 能表示的所有值都是 g 的倍数所以 c 必须是 g 的倍数。有解的情况下先解 ax by g得到特解 x₀、y₀然后整体放大 c / g 倍x x₀ × (c / g) y y₀ × (c / g)我用一个具体例子走一遍。解 6x 15y 9。先算 exgcd(6, 15)结果是 g3, x-2, y1注意这里的 y1 正是让等式 6×(-2) 15×1 3 成立的那组系数。因为 9 / 3 3所以x -2 × 3 -6 y 1 × 3 3验证6×(-6) 15×3 -36 45 9成立。5.2 通解构造与最小非负整数解有了特解还不够实际问题通常要的是“所有解”或者“在某个范围内的解”。通解的形式是所有做过整数规划的人都该刻进 DNA 的x x (b / g) × t y y - (a / g) × t其中 t 取任意整数。为什么这么构造因为要让 ax by 的值不变x 每增加 b/gy 必须对应减少 a/g这样 a × (b/g) b × (-a/g) 0线性组合的增量正好抵消。很多场景下我们需要最小非负整数解比如找零问题里要 x ≥ 0 且尽量小。这时候用模运算卡范围就行long long step b / g; // x 的增量步长 if (step 0) step -step; long long x_min (x % step step) % step; // 最小非负特解 long long y_min (c - a * x_min) / b; // 对应的 y拿上面的例子继续x 的步长 step 15 / 3 5x -6规范到 [0, 4] 区间是 (-6 % 5 5) % 5 4对应的 y (9 - 6×4) / 15 -15 / 15 -1。验证 6×4 15×(-1) 24 - 15 9正确。这里 y 允许是负数如果你的业务要求 x、y 都非负那就得额外检查通解区间内是否存在这样的组合判断方法可以归结为一元一次不等式组求解思路不复杂但容易算错建议写个小函数统一处理。6. 进阶应用RSA 私钥计算与同余方程组6.1 RSA 里私钥 d 的计算流程RSA 的核心密钥生成过程里扩展欧几里得算法的位置至关重要。简单回顾一下选两个大素数 p、q计算 n p×q再算欧拉函数 φ(n) (p-1)(q-1)。选一个与 φ(n) 互质的公钥指数 e然后私钥 d 要满足e × d ≡ 1 (mod φ(n))这不就是求 e 在模 φ(n) 下的逆元吗一步 mod_inverse 搞定。我用教材里最经典的小参数案例p61, q53那么 n 3233φ(n) 60 × 52 3120。取 e 1717 和 3120 互质因为 gcd(17, 3120)1可以先用 exgcd 自检然后long long e 17, phi 3120; long long x, y; exgcd(e, phi, x, y); // 17x 3120y 1 long long d (x % phi phi) % phi; // 输出d 2753得到的 d 2753这正是我之前在模逆元一节验证过的结果。这里有一个工程上容易忽略的点φ(n) 本身不一定是素数所以费马小定理那条路走不通必须用扩展欧几里得这个细节在真实密钥生成库的底层实现里一定会出现。6.2 用一次 exgcd 解同余方程组CRT 的工程实现中国剩余定理CRT解决的是同余方程组x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)当 m₁、m₂ 互质时在模 m₁×m₂ 下有唯一解。标准算法需要分别求 M₁ m₂ 在模 m₁ 下的逆元、M₂ m₁ 在模 m₂ 下的逆元看起来要调两次 exgcd。但细想一下一次 exgcd(m₁, m₂) 得到的是 m₁×t₁ m₂×t₂ 1这个等式已经同时蕴含了两个逆元——m₂×t₂ ≡ 1 (mod m₁)m₁×t₁ ≡ 1 (mod m₂)。所以一次调用就够了// 解 x ≡ a1 (mod m1), x ≡ a2 (mod m2), gcd(m1,m2)1 long long t1, t2; exgcd(m1, m2, t1, t2); // m1*t1 m2*t2 1 long long M m1 * m2; long long x (a1 * m2 % M * t2 a2 * m1 % M * t1) % M; x (x M) % M; // 规范化到 [0, M-1]我验证一个具体例子解 x ≡ 2 (mod 3)x ≡ 3 (mod 5)。exgcd(3, 5) 得到 3×2 5×(-1) 1即 t₁2, t₂-1。代入公式x 2×5×(-1) 3×3×2 -10 18 8 (mod 15)验证8 mod 3 28 mod 5 3完全正确。这个写法比教科书上“分别求逆再组合”少了一次 exgcd 调用在需要大量解同余方程组的场景比如 RSA-CRT 加速解密性能收益是实打实的。7. 常见问题与排查技巧7.1 问题速查表我把这些年实际用扩展欧几里得时踩过的坑和排查思路整理成一张表遇到问题先对照一遍现象可能原因排查与解决递归版算出的 x、y 验证不成立回溯时漏更新 y或 a/b 计算时用的变量已经变化用 (a, b) (252, 105) 等小数据单步调试重点看每层回溯后的 x、y算模逆元返回负数忘记做规范化(x % m m) % m求逆元出口统一做一次规范化保证结果落在 [0, m-1]模逆元不存在的判断失败调用前没检查 gcd(a, m) 是否为 1返回值约定为 gcd调用方判断 g 1 再继续迭代版跑大数结果溢出中间乘法 q*x1 超出 32 位全部换 long long必要时用 __int128输入含负数导致结果诡异C 取模对负数向零取整与数学定义不一致入口处统一把参数规整到非负或单独处理符号CRT 结果验证不对逆元求反或者公式里 a₁、a₂ 位置搞混用 (2,3,3,5) 这类小例子验证对比手算结果7.2 几个实打实的调试经验第一永远先写验证函数再写业务代码。不管你是递归派还是迭代派算完一组 (a, b, x, y) 后立刻检查a*x b*y gcd(a, b)这个断言能拦截九成以上的低级错误。我在项目里甚至会专门写一个测试用例集把 (30, 12)、(252, 105)、(17, 3120) 这些经典组合全放进去改一次代码跑一遍回归。第二注意区分“数学上的模”和“C 里的 %”。数学上模运算结果恒为非负而 C 里负数取模可能是负数。凡是涉及逆元、CRT 最终结果的最后一步务必统一做规范化处理这个习惯能省掉大量边界 bug。第三递归深度不是大问题但也不是完全没问题。虽然 O(log min(a,b)) 深度通常只有几十层但在某些嵌入式或结构化编程环境里还是优先用迭代版更稳妥。别等到线上偶发栈溢出再后悔写库代码时直接迭代版起步。第四当 gcd 不等于 1 时算法并不会报错而是静默返回一组“看起来能用”的系数。切记调用方必须检查返回值否则你会拿着一个根本不存在的模逆元去加密然后得到一堆乱码排查半天才发现是逆元那一步出了问题。7.3 我个人沉淀的几个使用习惯最后分享几个我自己写代码时的固定套路。求逆元我统一封装成 mod_inverse 函数里面自带 gcd 检查和规范化调用方不需要懂扩展欧几里得的细节只看函数名就知道语义。解不定方程我封装成返回结构体{g, x0, y0, step_x, step_y}把特解和步长一起带出来方便上层直接构造通解。写算法题时我会用递归版因为短、快、好调试写库代码时我用迭代版因为稳、可控、无栈风险。另外所有涉及大数乘法的场景我习惯先估算一下数量级再决定用 int64 还是上大整数库别迷信“64 位够用”在一些中间展开式里系数临时变大是常有的事。这套算法我前前后后在各种项目里用了不下几十次从最开始照着书本抄代码抄错到后来闭着眼都能写对最大的体会就是数论算法跟业务代码不一样它的正确性不是靠“感觉”就能保证的而是靠严谨推导和持续验证。只要你把裴蜀定理那层关系吃透了把递归回溯的系数变化捋顺了剩下的纯粹是机械操作。希望这篇梳理能帮你少走点弯路也欢迎在实践中多拿小数据验证跑多了自然就熟了。
扩展欧几里得算法全解析：从数学原理到RSA私钥计算与工程实践
扩展欧几里得算法这名字听起来像是个只会在数学竞赛和密码学课本里出现的东西但实际上我工作这些年发现它的出场频率远比想象中高做算法题求模逆元、写安全相关逻辑算 RSA 私钥、甚至解一个简单的不定方程找整数解翻来覆去绕不开它。教材上通常就甩给你一段递归代码加一句“设 axbygcd(a,b)回溯求出整数解 x,y”然后就没然后了。等你真正上手用的时候各种坑就冒出来了x 是负数怎么办gcd 不整除 c 方程还有没有解递归里 x 和 y 传参为什么是反着的迭代写法又该怎么对应数学过程这篇文章我把自己从入门到实际项目里用这套算法的完整经验梳理了一遍包括原理推导、递归和迭代两套实现、求模逆元和解不定方程的完整流程再配上 RSA 私钥计算和中国剩余定理这两个工程里最典型的场景。代码给全案例给足你照着抄就能跑跑完就知道为什么每一步要这么写。1. 从欧几里得算法说起扩展到底扩展了什么1.1 先聊聊老祖宗留下的求 gcd 套路欧几里得算法本身很简单核心就一句话gcd(a, b) gcd(b, a mod b)。反复套用这个等式把两个数越滚越小直到某个数变成 0另一个数就是最大公约数。我拿 252 和 105 举例子252 2 × 105 42 105 2 × 42 21 42 2 × 21 0所以 gcd(252, 105) 21。这个算法的好处是效率极高每轮至少让较大的数缩小一半整体复杂度是 O(log min(a, b))哪怕两个数都是几十位的长整数也就是几百次除法的事儿这也是为啥它能进 RSA 这类大数运算场景。但传统欧几里得算法有个“性格缺陷”它只告诉你最大公约数是多少完全不关心这些余数是怎么一步步组合出来的。打个比方你只知道一堆食材最后炖出了一锅汤但每样食材放了多少、先后顺序是什么它一概不管。实际工程和数学问题里我们经常需要的不只是“gcd 是多少”而是“gcd 能不能用原来的 a 和 b 线性组合出来组合系数是多少”。这就是扩展欧几里得算法存在的意义。1.2 扩展出来的核心能力一组黄金系数扩展欧几里得算法要解决的问题是给定两个整数 a 和 b求整数 x 和 y使得a × x b × y gcd(a, b)这个等式叫裴蜀定理Bézouts identity它保证只要 gcd(a, b) 能被某个数整除那对应系数的整数解就一定存在。扩展欧几里得算法的本质就是在跑一遍标准欧几里得算法的过程中把每一轮的商记下来最后逆着推回去把最大公约数重新写成 a 和 b 的线性组合。我继续用 252 和 105 演示。从最后一步往上回溯21 105 - 2 × 42 105 - 2 × (252 - 2 × 105) 5 × 105 - 2 × 252所以 exgcd(252, 105) 得到的一组系数是 x -2y 5验证一下252 × (-2) 105 × 5 -504 525 21完全正确。注意 x 是负数这不是 bug这是常态。后面所有“负数怎么规范化”的讨论根源都在这里。1.3 这套算法到底能用在哪儿我盘点了一下实际开发里最常见的几类场景求模逆元解 ax ≡ 1 (mod m)这是 RSA、ElGamal 这类公钥密码算法的地基操作。解线性丢番图方程形如 ax by c 求整数解工程里设计找零、资源分配这类整数规划问题会碰到。中国剩余定理实现解同余方程组时需要求多个模数下的逆元一步一个 exgcd。分数模运算、组合数取模、以及各种数论算法内部的基础模块。可以说扩展欧几里得跟快速幂、素数筛一样属于数论工具箱里的“基础款工具”不会它后面一堆算法都施展不开。2. 数学推导为什么回溯能求出系数2.1 核心递推式的完整推导理解扩展欧几里得关键是抓住一个递推关系。设我们在某一步要算 exgcd(a, b)按欧几里得算法的套路下一步要算 exgcd(b, a mod b)。假设我们已经知道了后者的结果b × x (a mod b) × y gcd(b, a mod b)而 gcd(b, a mod b) gcd(a, b)所以等号右边不变。接下来把 a mod b 展开a mod b a - ⌊a/b⌋ × b代回上面的等式b × x (a - ⌊a/b⌋ × b) × y gcd(a, b)把含 b 的项合并一下a × y b × (x - ⌊a/b⌋ × y) gcd(a, b)对比目标式 a × x b × y gcd(a, b)系数就一目了然了x y y x - ⌊a/b⌋ × y这就是为什么递归实现里要把 x 和 y 交换着传进去再在回溯时做一次减法。如果你理解了这个推导后面看代码就不会觉得“传参为什么是反的”很玄学了那正是为了保证回溯后的 x 取到下一层的 y。2.2 终止条件与回溯过程拆解递归的终止条件是 b 0。此时 gcd(a, 0) a等式变成 a × x 0 × y a显然取 x 1y 0 就行。这是唯一一组“拍脑袋”定出来的初始值剩下的全靠回溯一层层修正。我还是用 252 和 105 完整走一遍递归过程把每一层的中间结果列出来你就能看到系数是怎么“长”出来的递归层传入 (a, b)回溯后的 x回溯后的 y验证第 1 层(252, 105)-25252×(-2)105×521第 2 层(105, 42)2-1105×242×(-1)21第 3 层(42, 21)0142×021×121第 4 层(21, 0)1021×10×021从最后一行往上走每一层的系数都保持“a 乘 x 加 b 乘 y 等于 21”这个不变量。这就是回溯法的精妙之处不变量贯穿始终每层只做 O(1) 的算术总复杂度依然是 O(log min(a, b))。2.3 系数的数量级与时间复杂度很多人担心一个问题递归回溯这么多次系数会不会爆炸式增长实测下来完全不用担心。可以证明回溯过程中 x 和 y 的绝对值都不会超过 max(a, b) 的数量级更精确地说|x| ≤ b / (2 × gcd(a, b))|y| ≤ a / (2 × gcd(a, b))大致量级。所以在 64 位整数范围内使用只要 a、b 本身不超范围系数一般也不会溢出。不过这里有个前提如果你在循环里反复用乘法更新系数比如我后面讲的迭代写法中间过程确实有溢出风险实操时用 long long 是个好习惯Python 这种大整数语言则完全没这个顾虑。3. 代码实现递归、迭代与细节打磨3.1 递归实现与传参顺序的坑递归版本最简洁也最贴近数学推导。我用 C 写一版long long exgcd(long long a, long long b, long long x, long long y) { if (b 0) { x 1; y 0; return a; } long long g exgcd(b, a % b, y, x); y - a / b * x; return g; }这段代码里唯一反直觉的点就在递归调用exgcd(b, a % b, y, x)把当前帧的 y 当作下一层的 x 传进去把当前帧的 x 当作下一层的 y 传进去。结合上一节的推导就清楚了回溯后我们需要 x y、y x - ⌊a/b⌋ × y而递归返回后下一层的 x、y 分别落在了当前帧的 y、x 里正好对上公式。我见过不少人手写这个版本时漏掉 y 的更新或者把减法写成加法结果算出来怎么验都不对。我的建议是写完立刻用一组小数据验证比如 exgcd(252, 105)预期得到 g21, x-2, y5。把这一步当成单元测试写进代码里之后怎么改都不怕。3.2 迭代实现与数学过程的对应递归虽然好写但在极端情况下a、b 相差巨大递归深度达到几十层也可能让人心里没底而且某些语言环境递归栈开销大。迭代写法则完全避免了这个问题。关键思路是维护两组系数分别对应“当前余数”和“上一个余数”的线性表示def exgcd_iter(a, b): # 初始化始终维护 a*x0 b*y0 当前余数 x0, y0 1, 0 # 当前余数初始为 a x1, y1 0, 1 # 上一个余数初始为 b while b: q a // b a, b b, a % b # 同步更新两行系数 x0, x1 x1, x0 - q * x1 y0, y1 y1, y0 - q * y1 return a, x0, y0我拿 a 30, b 12 验证一遍30 × 1 12 × 0 30当前余数 3012 × 0 30 × 0不对一步步来。初始 x01,y00 对应 30x10,y11 对应 12。第一轮 q2新余数 30 mod 12 6而 6 30 - 2×12所以要用“旧 30 的系数”减去 q 倍“旧 12 的系数”也就是 x0 x1 0, x1 1 - 2×0 1y0 y1 1, y1 0 - 2×1 -2。现在 30×0 12×1 12? 不对这里的对应关系要仔细捋一下。其实迭代写法里每次循环x0、y0 表示的是“新的更小的那个数”即新余数如何由原始 a、b 组合出来x1、y1 表示的是“被减掉的较大的那个数”即旧的 b如何组合出来。刚才第一轮后新余数 6 a×1 b×(-2)带入 30×1 12×(-2) 6对的。而旧 b 12 a×0 b×1也对。第二轮 q2新余数 12 mod 6 06 12 - 2×6此时更新系数最终返回的 a6, x01, y0-2验证 30×1 12×(-2) 6完美。只要保证“每轮结束时x0,y0 组合出当前 a”代码就不会出错。这个版本我建议在 C、Java、Python 里都存一份遇到递归深度恐惧症的时候直接换用。3.3 细节打磨负数处理、溢出防护与返回值约定实际工程中输入不一定都是正整数。比如求模逆元时a 和 m 可能出现在某些边界场景里带着负数进来。标准的扩展欧几里得算法对负数也能跑只是系数符号会变得很难看而且中间的取模运算在 C 里对负数是向零取整跟数学定义不一致容易出隐蔽 bug。我的统一做法是进函数前先把 a、b 都转成正数记录符号最后再把符号作用到结果上。具体到求模逆元这种场景更常见的做法是直接用(a % m m) % m把 a 规整到 [0, m-1] 再调函数这样省心得多。另外凡是用 64 位整数的场景我建议所有参与运算的变量一律 long long乘法中间结果用__int128或者 Python 的大整数兜底别在这种地方省溢出排错的时间成本远高于换类型的一秒钟。返回值约定也要提前定好我的习惯是函数返回 gcdx、y 通过引用带出。这样调用方一眼就能判断 gcd 是否为 1、是否满足可逆条件不用额外传指针判断成败。4. 核心应用一模逆元的完整求解4.1 模逆元是什么、什么时候存在模逆元的定义很直白给定 a 和模数 m如果存在整数 b 使得 a × b ≡ 1 (mod m)那 b 就叫 a 在模 m 下的逆元记作 a⁻¹。说白了就是在模世界里跟 a 相乘等于 1 的那个数。这个操作在 RSA 私钥计算、组合数取模、哈希一致性哈希环等场景到处都是。存在条件是一条硬规则只有当 gcd(a, m) 1即 a 与 m 互质时逆元才存在。原因也不难理解a × b 1 k × m 移项就是 a × b - k × m 1根据裴蜀定理左边能表示的最小正整数正好是 gcd(a, m)所以 gcd 必须是 1。这也意味着如果你算出来的 gcd 不是 1直接放弃别试图硬凑数学上就不可能有解。4.2 用扩展欧几里得求模逆元完整案例回到方程本身求 a 在模 m 下的逆元等价于解 a × x m × y 1。调用一次 exgcd(a, m) 得到 xx 就是逆元。这里有个小坑x 可能是负数而逆元的习惯表示是 [0, m-1] 里的正整数所以需要规范化long long mod_inverse(long long a, long long m) { long long x, y; long long g exgcd(a, m, x, y); if (g ! 1) { return -1; // 不存在模逆元 } x (x % m m) % m; // 关键把负数规范到 [0, m-1] return x; }我举一个具体的数字例子方便你对照验证求 17 在模 3120 下的逆元。调用 exgcd(17, 3120)会得到一组 x -367y 2你可以用上面的代码跑一下或者手推一遍因为 17 × (-367) 3120 × 2 1。规范化后d (-367 % 3120 3120) % 3120 2753验证一下17 × 2753 4680146801 mod 3120 1完全正确。这个例子不是随便编的它就是经典的 RSA 小参数案例我后面在 RSA 那一节还会用到 2753 这个数。4.3 为什么费马小定理不能通吃很多人会问求逆元不是还能用费马小定理吗a^(m-2) mod m 一步幂运算就出来了为什么要费劲写扩展欧几里得答案是适用条件不同。费马小定理的前提是模数 m 必须是素数这在很多工程场景里是硬伤。比如 RSA 里计算私钥时用的模数是 φ(n)它几乎不可能是素数又比如你只想求 5 在模 12 下的逆元12 不是素数a^(12-2) 那条路直接不成立。扩展欧几里得对任意互质的 a、m 都成立而且复杂度 O(log min(a, m)) 比快速幂 O(log m) 在常数上更小因为每次迭代只有除法和减法。所以除非你 100% 确定模数是素数否则我建议一律用扩展欧几里得一条路走到底。5. 核心应用二线性丢番图方程5.1 有解条件与特解计算形如 ax by c 的方程要求 x、y 都是整数这就是线性丢番图方程。工程里遇到“要把总量 c 拆成 a 和 b 两种规格的整数份”这类问题本质上就是在解这种方程。第一步先算 g gcd(a, b)。方程有整数解的充要条件是 g 整除 c理由还是裴蜀定理那条线ax by 能表示的所有值都是 g 的倍数所以 c 必须是 g 的倍数。有解的情况下先解 ax by g得到特解 x₀、y₀然后整体放大 c / g 倍x x₀ × (c / g) y y₀ × (c / g)我用一个具体例子走一遍。解 6x 15y 9。先算 exgcd(6, 15)结果是 g3, x-2, y1注意这里的 y1 正是让等式 6×(-2) 15×1 3 成立的那组系数。因为 9 / 3 3所以x -2 × 3 -6 y 1 × 3 3验证6×(-6) 15×3 -36 45 9成立。5.2 通解构造与最小非负整数解有了特解还不够实际问题通常要的是“所有解”或者“在某个范围内的解”。通解的形式是所有做过整数规划的人都该刻进 DNA 的x x (b / g) × t y y - (a / g) × t其中 t 取任意整数。为什么这么构造因为要让 ax by 的值不变x 每增加 b/gy 必须对应减少 a/g这样 a × (b/g) b × (-a/g) 0线性组合的增量正好抵消。很多场景下我们需要最小非负整数解比如找零问题里要 x ≥ 0 且尽量小。这时候用模运算卡范围就行long long step b / g; // x 的增量步长 if (step 0) step -step; long long x_min (x % step step) % step; // 最小非负特解 long long y_min (c - a * x_min) / b; // 对应的 y拿上面的例子继续x 的步长 step 15 / 3 5x -6规范到 [0, 4] 区间是 (-6 % 5 5) % 5 4对应的 y (9 - 6×4) / 15 -15 / 15 -1。验证 6×4 15×(-1) 24 - 15 9正确。这里 y 允许是负数如果你的业务要求 x、y 都非负那就得额外检查通解区间内是否存在这样的组合判断方法可以归结为一元一次不等式组求解思路不复杂但容易算错建议写个小函数统一处理。6. 进阶应用RSA 私钥计算与同余方程组6.1 RSA 里私钥 d 的计算流程RSA 的核心密钥生成过程里扩展欧几里得算法的位置至关重要。简单回顾一下选两个大素数 p、q计算 n p×q再算欧拉函数 φ(n) (p-1)(q-1)。选一个与 φ(n) 互质的公钥指数 e然后私钥 d 要满足e × d ≡ 1 (mod φ(n))这不就是求 e 在模 φ(n) 下的逆元吗一步 mod_inverse 搞定。我用教材里最经典的小参数案例p61, q53那么 n 3233φ(n) 60 × 52 3120。取 e 1717 和 3120 互质因为 gcd(17, 3120)1可以先用 exgcd 自检然后long long e 17, phi 3120; long long x, y; exgcd(e, phi, x, y); // 17x 3120y 1 long long d (x % phi phi) % phi; // 输出d 2753得到的 d 2753这正是我之前在模逆元一节验证过的结果。这里有一个工程上容易忽略的点φ(n) 本身不一定是素数所以费马小定理那条路走不通必须用扩展欧几里得这个细节在真实密钥生成库的底层实现里一定会出现。6.2 用一次 exgcd 解同余方程组CRT 的工程实现中国剩余定理CRT解决的是同余方程组x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)当 m₁、m₂ 互质时在模 m₁×m₂ 下有唯一解。标准算法需要分别求 M₁ m₂ 在模 m₁ 下的逆元、M₂ m₁ 在模 m₂ 下的逆元看起来要调两次 exgcd。但细想一下一次 exgcd(m₁, m₂) 得到的是 m₁×t₁ m₂×t₂ 1这个等式已经同时蕴含了两个逆元——m₂×t₂ ≡ 1 (mod m₁)m₁×t₁ ≡ 1 (mod m₂)。所以一次调用就够了// 解 x ≡ a1 (mod m1), x ≡ a2 (mod m2), gcd(m1,m2)1 long long t1, t2; exgcd(m1, m2, t1, t2); // m1*t1 m2*t2 1 long long M m1 * m2; long long x (a1 * m2 % M * t2 a2 * m1 % M * t1) % M; x (x M) % M; // 规范化到 [0, M-1]我验证一个具体例子解 x ≡ 2 (mod 3)x ≡ 3 (mod 5)。exgcd(3, 5) 得到 3×2 5×(-1) 1即 t₁2, t₂-1。代入公式x 2×5×(-1) 3×3×2 -10 18 8 (mod 15)验证8 mod 3 28 mod 5 3完全正确。这个写法比教科书上“分别求逆再组合”少了一次 exgcd 调用在需要大量解同余方程组的场景比如 RSA-CRT 加速解密性能收益是实打实的。7. 常见问题与排查技巧7.1 问题速查表我把这些年实际用扩展欧几里得时踩过的坑和排查思路整理成一张表遇到问题先对照一遍现象可能原因排查与解决递归版算出的 x、y 验证不成立回溯时漏更新 y或 a/b 计算时用的变量已经变化用 (a, b) (252, 105) 等小数据单步调试重点看每层回溯后的 x、y算模逆元返回负数忘记做规范化(x % m m) % m求逆元出口统一做一次规范化保证结果落在 [0, m-1]模逆元不存在的判断失败调用前没检查 gcd(a, m) 是否为 1返回值约定为 gcd调用方判断 g 1 再继续迭代版跑大数结果溢出中间乘法 q*x1 超出 32 位全部换 long long必要时用 __int128输入含负数导致结果诡异C 取模对负数向零取整与数学定义不一致入口处统一把参数规整到非负或单独处理符号CRT 结果验证不对逆元求反或者公式里 a₁、a₂ 位置搞混用 (2,3,3,5) 这类小例子验证对比手算结果7.2 几个实打实的调试经验第一永远先写验证函数再写业务代码。不管你是递归派还是迭代派算完一组 (a, b, x, y) 后立刻检查a*x b*y gcd(a, b)这个断言能拦截九成以上的低级错误。我在项目里甚至会专门写一个测试用例集把 (30, 12)、(252, 105)、(17, 3120) 这些经典组合全放进去改一次代码跑一遍回归。第二注意区分“数学上的模”和“C 里的 %”。数学上模运算结果恒为非负而 C 里负数取模可能是负数。凡是涉及逆元、CRT 最终结果的最后一步务必统一做规范化处理这个习惯能省掉大量边界 bug。第三递归深度不是大问题但也不是完全没问题。虽然 O(log min(a,b)) 深度通常只有几十层但在某些嵌入式或结构化编程环境里还是优先用迭代版更稳妥。别等到线上偶发栈溢出再后悔写库代码时直接迭代版起步。第四当 gcd 不等于 1 时算法并不会报错而是静默返回一组“看起来能用”的系数。切记调用方必须检查返回值否则你会拿着一个根本不存在的模逆元去加密然后得到一堆乱码排查半天才发现是逆元那一步出了问题。7.3 我个人沉淀的几个使用习惯最后分享几个我自己写代码时的固定套路。求逆元我统一封装成 mod_inverse 函数里面自带 gcd 检查和规范化调用方不需要懂扩展欧几里得的细节只看函数名就知道语义。解不定方程我封装成返回结构体{g, x0, y0, step_x, step_y}把特解和步长一起带出来方便上层直接构造通解。写算法题时我会用递归版因为短、快、好调试写库代码时我用迭代版因为稳、可控、无栈风险。另外所有涉及大数乘法的场景我习惯先估算一下数量级再决定用 int64 还是上大整数库别迷信“64 位够用”在一些中间展开式里系数临时变大是常有的事。这套算法我前前后后在各种项目里用了不下几十次从最开始照着书本抄代码抄错到后来闭着眼都能写对最大的体会就是数论算法跟业务代码不一样它的正确性不是靠“感觉”就能保证的而是靠严谨推导和持续验证。只要你把裴蜀定理那层关系吃透了把递归回溯的系数变化捋顺了剩下的纯粹是机械操作。希望这篇梳理能帮你少走点弯路也欢迎在实践中多拿小数据验证跑多了自然就熟了。
