密码学 欧几里得算法

密码学 欧几里得算法

一、求最大公因子

设a,b是任意两个正整数，将他们的最大公因子gcd(a,b)简记为(a,b)。
重要的结论如下所示：

(a,b) = (b,a mod b)

a mod b 可以理解为a与b相除之后所得的余数，听上去有点抽象，我们可以通过简单的例子来理解。
例如：

(55,22)=(22,55 mod 22) = (22,11) = (11,0) = 11

就可以简单的理解为

55 = 22*2 + 1122 = 11*2 + 0

通过上述简单的例子，我们就可以掌握辗转相除法，伪代码如下所示：

EUCLID(a,b)1.X <--- a; Y <--- b;2.if Y=0 then return X = (a,b);3.if Y=1 then return Y = (a,b);4.R = X mod Y;5.X = Y;6.Y = R;7.goto 2.

当然，上面伪代码提供的只是算法的实现，我们可以使用Python代码简单实现

def gcd(a,b):    if a<b: t = a a = b b = t    while a%b != 0: temp = a%b a = b b = temp    return ba = int(input("a="))b = int(input("b="))r = gcd(a,b)print(r)

二、求乘法逆元

如果(a,b) = 1，则b在mod a下有乘法逆元（不妨设b<a），即存在一个x(x<a),使得bx = 1 mod a。推广的欧几里得算法先求出（a,b）,当（a,b）= 1时，则返回b的逆元。
算法使用伪代码表示为：

EXTENED EUCLID(a,b)(设b<a)1.(X1,X2,X3) <—— (1,0,a);(Y1,Y2,Y3) <—— (0,1,b);2.if Y3=0 then return X3 = (a,b);no inverse;3.if Y3=1 then return Y3 = (a,b);Y2 = b^-1 mod f;4.Q = [X3/Y3];5.(T1,T2,T3) <—— (X1-QY1,X2-QY2,X3-QY3);6.(X1,X2,X3) <—— (Y1,Y2,Y3);7.(Y1,Y2,Y3) <—— (T1,T2,T3);8.goto 2.

其实，此算法并没有我们想象中那么可怕，我们可以简单的理解为X1，X2的初始值分别为1，0；Y1，Y2的初始值分别为0，1；a,b非别是我们所要求的两个未知数；当然这里有个小细节就是（b < a）.
初始值赋值完毕后
(1)我们进行判断Y3的值，如果等于0，返回X3 =（a,b）直接就没有乘法逆元 ；如果Y3等于1，返回Y3 =（a,b），Y2就是b的乘法逆元;
(2)如果都不满足前面的判断，那么Q等于X3除以Y3，T1 = X1-QY1，T2 = X2-QY2，T3 = X3-QY3，X1 = Y1，X2 = Y2，X3 = Y3 ，Y1 = T1，Y2 = T2，Y3 = T3
(3)其实(2)中的判断就是循环，循环结束就得看Y3的值，这又用到(1)的判断方法

就拿(1769,550)来举例

所以(1769，550）= 1，550^-1 mod 1769 = 550

当然，上面伪代码提供的只是算法的实现，我们可以使用Python代码简单实现

def Eu_kz(m,b):    if m < b: t = m m = b b = t    x1,x2,x3 = 1,0,m    y1,y2,y3 = 0,1,b    while True: if y3==0:     return None     break elif y3==1:     return y2%m     break else:     Q = x3//y3     t1,t2,t3 = x1-Q*y1,x2-Q*y2,x3-Q*y3     x1,x2,x3 = y1,y2,y3     y1,y2,y3 = t1,t2,t3m = int(input("m="))b = int(input("b="))r = Eu_kz(m,b)print(r)

PS：一开始接触辗转相除法和乘法逆元可能会有点困难，但是不要担心，多思考一会儿，一定可以理解的，如果算法理解上存在问题或困难欢迎评论区留言或私信我，感谢支持！！！