欧几里得算法
背景知识:
欧几里得算法:又叫做辗转相除法,用来求两个数的最大公约数。通过辗转相除,当余数为0的时候,最后的除数就是两个数的最大公约数。
例如:求20和11的最大公约数
每次将除数作为下一个式子的被除数,将余数作为下一个式子的除数。
20➗11=1......9
11➗9=1......2
9➗2=4......1
2➗1=2......0
所以最大公约数为最后一个式子的除数1,即gcd(20,11)=1
扩展欧几里得算法与逆元
扩展欧几里得算法结论:对整数 a 与 b来说, 必存在整数 x 与 y 使得
ax + by = gcd(a,b)
注:具体证明此处不做展开
逆元定义:ax = 1(mod p),此时a与x互为逆元
例如a = 4,p = 11,由于4*3=12,12 mod 11 = 1,a=4在模11条件下的逆元为x=3。
为什么扩展欧几里得算法可以求解逆元:
由逆元定义可知满足ax%p=1,因此a与b互为逆元时,加上k倍的p也不影响,毕竟kp对p取余之后为0,所以可以将求逆元的过程转换成:ax+kp=1,此时a与p已知,这就成功转化成扩展欧几里得算法求解的形式,我们可以求出x和k,x即为a对应的逆元。
对于复杂式子我们不能直接看出对应的逆元,具体操作步骤如下所示。
例如:求11在(mod20)条件下的逆元
上个例子中求得:gcd(20,11)=1
代入扩展欧几里得式子:
11x+20y=1
具体求解方法如下所示(类似于欧几里得算法求解过程):
20=11*1+9----------①
11=9*1+2----------②
9=2*4+1 ----------③
写成上述的形式是类似于计算机求解过程,因此下面的移向操作并不是多此一举。
由式子①,②(移项)可得:
20-11*1=9 ----------④
11-9*1=2 ----------⑤
④带入⑤(目的是消去9,当求解过程中有很多式子时,就是这样一步步消去中间项)
11-(20-11*1)*1=2 ----------⑥
再将④和⑥代入③消去中间值9和2,可得:
20-11*1=(11-(20-11*1)*1)*4+1
合并同类项可得:
5*20-9*11=1
也就解除了最开始的式子11x+20y=1,得到x=-9,y=5
总结:对式子ax = 1(mod p)我们已知a和p,先求p=a*x1+p1(此时的p1实际上时p与a运算的余数),然后将p=a,a=p1代入式子不断进行迭代,直到计算出余数为1时,pi=a*xi+1,就可以不断移向消去中间项,最后计算出对应的逆元。
乘法密码
答疑:
图中是以英文字母为例,假设26个字母对应数字0-25
1.为什么k要与26互素
因为互素的条件下才能将0-25与k运算之后均匀的映射到每一个位置,否则肯定会有重叠的部分。
2.怎么求k的逆元
由于k与26互素,所以gcd(k,26)=1.
已知k和p=26,利用扩展欧几里得算法:kx+py=1可求得x,y,此时x即为对应的逆元。