More than 3 years have passed since last update.

ユークリッドの互除法

Last updated at 2021-09-19Posted at 2021-09-18

RSA暗号について勉強していたら、久しぶり（大学受験以来？）に遭遇したため、アルゴリズムについてまとめました。

正の整数 $a_0,a_1$ の最大公約数 gcd($a_0,a_1$) を出力するアルゴリズム
Input : $a_0,a_1 \in \mathbb{N},\ a_0>a_1>0$
Output : gcd($a_0,a_1$)
Algorithm :
1. $i\ ← 0$
2. $a_{i+2} ← a_i \ \text{mod}\ a_{i+1}\quad (0\leq a_{i+2}\leq a_{i+1})$
3. $\text{if}\ a_{i+2}=0\ \text{then return}\ a_{i+1}$
4. $\text{else}\ i←i+1\ \text{and return to line }2$

\left\{
\begin{array}{lllll}
a_0=q_1a_1+a_2 \\
a_1=q_2a_2+a_3\\
\qquad\vdots\\
a_{k-1}=q_ka_k+a_{k+1}\\
a_k=q_{k+1}a_{k+1}
\end{array}
\right.

$\text{gcd}(a,b)=\text{gcd}(b,a\ \text{mod}\ b)$
$\text{gcd}(a_0,a_1)=\text{gcd}(a_1,a_2)=\cdots =\text{gcd}(a_k,a_{k+1})=\text{gcd}(a_{k+1},a_{k+2})=a_{k+1}$

例

$a_0=354, a_1=156$の最大公約数を求める。
1. $i\ ← 0$
2. $a_{i+2} ← a_i \ \text{mod}\ a_{i+1}\quad (0\leq a_{i+2}\leq a_{i+1})$
3. $\text{if}\ a_{i+2}=0\ \text{then return}\ a_{i+1}$
4. $\text{else}\ i←i+1\ \text{and return to line }2$

\left\{
\begin{array}{lllll}
354=2\cdot156+42 \\
156=3\cdot42+30\\
42=1\cdot30+12\\
30=2\cdot12+6\\
12=2\cdot6+0
\end{array}
\right.

def gcd(a: int, b: int) -> int:
    x = a % b
    while x > 0:
        a = b
        b = x
        x = a % b
    return b

以下、再起を用いたユークリッドの互除法。

def re_gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    else:
        return re_gcd(b, a % b)

次は，拡張ユークリッドのアルゴリズムについてまとめます。