公钥加密数学基础 - 欧几里得算法

标准算法

一般用来算两个整数的公因数

即使在大数求公因数时也极其高效

  • 另一个耳熟能详的名字辗转相除法
1
2
3
4
5
6
7
8
9
10
#欧几里得算法
count = 0

def Euclidean(A,B):
    if A % B == 0:
        return B
    global count
    count += 1
    r = A % B
    return Euclidean(B, r)

扩展欧几里得算法

用来算模逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#扩展欧几里得算法
global ls
global lt
ls = [1,0] 
lt = [0,1]
s = t = -1


def EEA(A,B):
    if A % B == 0:
        return 0
    r = A % B
    q = A // B
    global s
    s = ls[0] - q*ls[1]
    global t
    t = lt[0] - q*lt[1]
    ls[0],ls[1] = ls[1],s
    lt[0],lt[1] = lt[1],t
    return EEA(B,r)