擴展歐基里德算法 (Extended Euclidean algorithm)

歐基里德算法

歐基里德算法又稱輾轉相除法，是計算兩個整數的最大公因數(Greatest Common Divisor, GCD)的方法。

有兩個數字

$a,b$，令

$p=gcd(a,b)$，那麼一定存在兩個正整數

$n,m\in \mathbb{R}$ 使得

$$a=np,b=mp$$

那麼如果要求

$p$，我們可以不斷讓

$a,b$ 互減，最後就會剩下

$p$
下圖是從維基百科上抓來的，兩線段分別表示

$252$ 及

$105$，每個單位為其最大公因數

$21$

可以發現到，當我們重複將較大的一方扣除較小的一方，直到其中一方為

$0$ 時，剩下的就會剛好是最大公因數

$p$

從這裡我們可以發現到，最大公因數實際上有這樣的性質:

$$gcd(a,b)=\{\begin{array}{ll}gcd(a-b,b)& a>b\\ gcd(b-a,a)& a<b\end{array}$$

不過實際上我們也不需要做那麼多次減法，因為我們總是會減到直到不能再減

• 假設
  $a>b$，那麼
  $a-b$ 的次數就是
  $\lfloor a/b\rfloor$，而這最後的
  $a$ 其實就是
  $a\mathrm{\%}b$
• 假設
  $a<b$，那麼
  $b-a$ 的次數就是
  $\lfloor b/a\rfloor$，而這最後的
  $b$ 其實就是
  $b\mathrm{\%}a$

附註:

$\lfloor \rfloor$ 為下高斯符號，也就是向下取整
舉例來說:

$\lfloor 3.14\rfloor =3,\lfloor 4.9\rfloor =4$

附註: 雖然沒有提到

$a=b$ 的情況，不過在

$a=b$ 時無論放在

$a>b$ 的作法或是

$a<b$ 的做法也都會是正確的

也就是說:

$$gcd(a,b)=\{\begin{array}{ll}gcd(a\mathrm{\%}b,b)& a>b\\ gcd(b\mathrm{\%}a,a)& a<b\end{array}$$

換個方法敘述
已知

$a/b=q\dots r$

$$\begin{gathered} a=qb+r \\ gcd(a,b)=gcd(qb+r,b)=gcd(r,b)=gcd(a\mathrm{\%}b,b) \end{gathered}$$

已知

$b/a=q\dots r$

$$\begin{gathered} b=qa+r \\ gcd(a,b)=gcd(qa+r,a)=gcd(r,a)=gcd(b\mathrm{\%}a,a) \end{gathered}$$

在實作上，可以透過

$gcd(a,b)=gcd(b,a\mathrm{\%}b)$ 來簡寫
如果

$a<b$ 的話，因為

$gcd(b,a\mathrm{\%}b)$ 會將兩者交換，因此下一次計算

$gcd$ 時就會計算到

$gcd(a,b\mathrm{\%}a)$ 了

def gcd(a, b):
    if(b == 0): return a
    return gcd(b, a%b)

擴展歐基里德算法

擴展歐基里德算法的命題如下:

已知

$\mathrm{\forall }a,b\in \mathbb{Z}$，必定存在

$x,y$ 使得貝祖定理成立

$$ax+by=gcd(a,b)$$
求

$x,y$ 分別為何

根據命題可得

$$\begin{array}{rl}a{x}_1+b{y}_1& =gcd(a,b)\\ b{x}_2+(a\mathrm{\%}b)y_2& =gcd(b,a\mathrm{\%}b)\end{array}$$

又因為

$$gcd(a,b)=gcd(b,a\mathrm{\%}b)$$

因此

$$\begin{array}{rl}a{x}_1+b{y}_1& =b{x}_2+(a\mathrm{\%}b)y_2\\ & =b{x}_2+(a-\lfloor a/b\rfloor b)y_2\end{array}$$

整理式子後可以得到

$$a{x}_1+b{y}_1=a{y}_2+b(x_2-\lfloor a/b\rfloor y_2)$$

因此

$$\{\begin{array}{l}{x}_1=y_2\\ y_1=x_2-\lfloor a/b\rfloor y_2\end{array}$$

因此，由於

$gcd(a,b)=gcd(b,a\mathrm{\%}b)$，我們可以將原問題轉換成等價的新問題，並且新問題得出來的

$x,y$ 可以幫助我們得到原問題的

$x,y$
如此一來就可以實作出擴展歐基里德算法囉!

補充: 在

$b=0$ 的情況下我們知道

$a=1\times a+0\times b$，因此回傳

$(x,y)=(1,0)$

def exd_gcd(a, b):
    if(b == 0): return 1, 0
    else:
        x, y = exd_gcd(b, a%b)
        return y, x-(a//b)*y

tags: Crypto