[Cryptography] 數論相關筆記-用Extended Eculid algorithm求Modular multiplicative inverse

在數論中，最大公因數是一個很重要的概念，因為如果兩個數的最大公因數為1，則代表兩個數互質(relatively prime)。要求兩數的最大公因數，可以透過Extended Eculid algorithm來計算。



Extended Eculid algorithm的概念是，假使我們今天有兩個數x和y，而最大公因數是標記為gcd(x,y)，則一定滿足：

a * x + b * y = gcd(x,y)

也就是說，存在參數a和b，使的相乘計算的結果會是最大公因數。

假設我們今天要求7和23的最大公因數，利用底下python的實作來計算。(注意a,b是要計算的數字；x,y則為參數，與上面公式不同)

#!/usr/bin/env python

def ext_eculid(a, b):
    print('a = {0}, b = {1}'.format(a, b))
    if b == 0:
        print('Finally, {0} {1} {2}'.format(1, 0, a))
        return 1, 0, a
    else:
        x, y, q = ext_eculid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a//b)*y)
        print('{0} {1} {2}'.format(x, y, q))
        return x, y, q

print(ext_eculid(7, 23))

讓我們來試著觀察一下計算過程，

演算法總共經過了五次的計算，從最後結果畫一條線，上面是a和b數字交換的過程；底下則是所對應的參數x和y。基本上每一組都會滿足a * x + b * y = N這個公式，舉例來說：

• 第一組：1*1 + 0*0 = 1
• 第三組：7*1 + 2*(-3) = 1

所以，經過計算之後就可以把兩個參數和最大公因數計算出來。那問題是，這可以幹嘛？10和-3這兩個數字是有意義的，因為這代表著Modular multiplicative inverse(模反元素)，也就是10是7在23之下的模反元素。再說一次，從Extended Eculid algorithm計算所得到互質的兩數字，其參數是該數字的模反元素。

從上述解釋，我們就可以求得7^-1在Z₂₃之下，就是10。其中Z₂₃代表{0, 1, 2, ..., 22}，也就是除以23之後的餘數集合。

接著，我們可以試著解下列式子：

3x + 2 = 7 in Z₁₉

從課堂講義我們得到

x = -b*a^-1

a^-1這時候就可以利用Extended Eculid algorithm來計算。所以題目就變成

x = (7-2) * 3^-1 = 5 * 3^-1 in Z₁₉

而3^-1在Z₁₉之就可以利用剛剛上面的Extended Eculid algorithm來計算啦！

#!/usr/bin/env python

def ext_eculid(a, b):
    print('a = {0}, b = {1}'.format(a, b))
    if b == 0:
        print('Finally, {0} {1} {2}'.format(1, 0, a))
        return 1, 0, a
    else:
        x, y, q = ext_eculid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a//b)*y)
        print('{0} {1} {2}'.format(x, y, q))
        return x, y, q

print(ext_eculid(3, 19))

其值為-6，所以答案為8。

x = 5 * (-6) mod 19 = -30 mod 19 = 8 mod 19