查看“︁大衍求一术”︁的源代码

[[分类:同余理论]]
{{InfoBox
|name=大衍求一术
|eng_name=Dayan-Qiuyi rule
}}
'''大衍求一术'''是用于求模逆 <math>ax \equiv 1 \pmod n</math> 的一种算法，类似于[[扩展欧几里得算法]]。

== 算法 ==

=== 原理 ===

对 <math>a, n</math> 存在整数 <math>x, v</math> 使得 <math>xa + v n = 1</math> ，则 <math>x</math> 就是 <math>a</math> 的模逆。其原理与[[扩展欧几里得算法]]几乎一致，只是后者会计算 <math>ua + vb = d</math> 中 <math>d</math> 取最小正数时的 <math>u, v</math> ，而前者只需要在 <math>d=1</math> 时（也就是说不需要计算到和）计算 <math>x=u</math> 而不需要 <math>v</math> 。

=== 伪代码 ===

<syntaxhighlight>
过程 大衍求一术
别名 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ₖ
</syntaxhighlight>


{{同余理论}}