表格式方法便于理解扩展欧几里得算法及其在求乘法倒数时的应用
文章目录
- 扩展欧几里得算法
- 求乘法逆元
扩展欧几里得算法
具体算法的原理参见扩展欧几里得算法求乘法逆元,本文仅以表格的形式展现计算过程,浅显易懂。下面通过例子进行说明。
例:求1234和4321的最大公约数,并将其表示为整系数的线性组合。
解: 根据定理内容列出以下表格,其中i为计算次数,ri 为原数及余数 ,qi 为商,xi yi 为新加的数,表格内数字的来历将在下面说明。
i | ri | qi | xi | yi |
---|---|---|---|---|
-1 | 4321 | 1 | 0 | |
0 | 1234 | 0 | 1 | |
1 | 619 | 3 | 1 | -3 |
2 | 615 | 1 | -1 | 4 |
3 | 4 | 1 | 2 | -7 |
4 | 3 | 153 | -307 | 1075 |
5 | 1 | 1 | 309 | -1082 |
6 | 0 | 3 |
由表格可知,gcd(1234,4321)=1,且整系数线性组合为4321×309+1234×(-1082)=1
以下对表格数字来历进行说明:
i的前两个数固定为 -1 和 0,xi 以及 yi 的前两个数分别固定为1、0和0、1,ri 的前两个数字为已知两数按大小排列,其余各数的计算过程以前三行数字为例:
紫色的619和粉色的3分别是橙色的4321与1234相除的余数和商,i==1行蓝色的1是由(红色的1)-(粉色的0粉色的3)得出来的,即1=1 - 3 * 0,同理i==1行蓝色的-3=(黄色的0)-(粉色的3粉色的1)得出来的,即-3=0 - 3 * 1,下面几行数字同理,以下一行为例,615和1分别为1234除以619的余数和商,-1=0 - 1 * 1,4=1 - 1 * -3,直到算到ri为0为止(本步不计入),此时的xi与yi即为所求系数,即4321×309+1234×(-1082)=1,ri为最大公约数,即gcd(1234,4321)=1
求乘法逆元
通过上述扩展欧几里得算法,可以得到1234mod4321的乘法逆元为最后一步的yi,即 -1082,将负数调整为正数即 -1028+4321=3239,故1234*3239≡1(mod 4321),同理,4321mod1234的乘法逆元为最后一步的xi,即4321*309≡1(mod 1234)
上一篇: 乘法逆元