大衍求一术
| 大衍求一术 | |
|---|---|
| 术语名称 | 大衍求一术 |
| 英语名称 | Dayan-Qiuyi rule |
大衍求一术是用于求模逆 [math]\displaystyle{ ax \equiv 1 \pmod n }[/math] 的一种算法，类似于扩展欧几里得算法。
算法
原理
对 [math]\displaystyle{ a, n }[/math] 存在整数 [math]\displaystyle{ x, v }[/math] 使得 [math]\displaystyle{ xa + v n = 1 }[/math] ，则 [math]\displaystyle{ x }[/math] 就是 [math]\displaystyle{ a }[/math] 的模逆。其原理与扩展欧几里得算法几乎一致，只是后者会计算 [math]\displaystyle{ ua + vb = d }[/math] 中 [math]\displaystyle{ d }[/math] 取最小正数时的 [math]\displaystyle{ u, v }[/math] ，而前者只需要在 [math]\displaystyle{ d=1 }[/math] 时（也就是说不需要计算到和）计算 [math]\displaystyle{ x=u }[/math] 而不需要 [math]\displaystyle{ v }[/math] 。
伪代码
过程 大衍求一术
别名 dayan_qiuyi_rule
参数 a, n : 整数 // 被求最大公因数的两个数
返回 : 整数 // 模逆（a 的系数）
令 r₀ ← n, t₀ ← 0
令 r₁ ← a, t₁ ← 1
循环 k ← 1
当 rₖ ≠ 1 时
执行
记 qₖ, rₖ₊₁ ← rₖ divmod rₖ₋₁
记 tₖ₊₁ ← tₖ₋₁ - qₖ tₖ
继续循环 k ← k + 1
返回 tₖ