扩展欧几里德算法
的<年代trong>欧几里得算法
欧几里德算法
欧几里得算法基本上就是整数除法算法的不断重复。关键是要重复除数除以余数,直到余数为0。GCD是这个算法中最后一个非零余数。下面的例子演示了求102和38的GCD的算法:
GCD是2,因为它是算法结束前出现的最后一个非零余数。 我们有
最后一个非零余数是17,因此GCD是17。<年代pan class="katex">
这个算法可以通过递归实现,如下图所示:
用欧几里得算法求出42823和6409的GCD。
欧几里德算法的递归实现
1 2 3 4 5 6 |
|
扩展欧几里德算法
扩展的欧几里得算法是一种计算整数的算法<年代pan class="katex">
和<年代pan class="katex">
这样
鉴于<年代pan class="katex">
和<年代pan class="katex">
. 这些整数的存在由<一个t一个rget="_blank" rel="nofollow" href="//www.parkandroid.com/wiki/bezouts-identity/">Bézout引理 推广后的欧几里得算法可以看成是模指数的倒数。 通过把欧几里得算法的步骤倒过来,就有可能找到这些整数<年代pan class="katex">
和<年代pan class="katex">
. 整个想法是从GCD开始,以递归的方式向后工作。这可以通过将数字视为变量来实现,直到我们得到一个表达式,它是初始数字的线性组合。我们将使用上面使用的示例来实现这一点。 我们从GCD开始。我们用前两项重写它:
我们更换了<年代pan class="katex">