ユークリッドの互除法とは

ユークリッドの互除法 （Euclidean algorithm）は、2つの自然数（または整数）の最大公約数（Greatest Common Divisor, GCD）を効率的に求めるためのアルゴリズムです。紀元前300年頃に古代ギリシャの数学者ユークリッドが著した数学書『原論』（Elements）の第7巻に記載されており、「人類最古のアルゴリズム」の一つとしても広く知られています。

最大公約数を求める最も素朴な方法は、2つの数をそれぞれ素因数分解し、共通する素因数を掛け合わせることですが、数が大きくなると素因数分解そのものの計算量が膨大になり、現実的な時間で解くことが困難になります。一方、 ユークリッドの互除法 を用いれば、数千桁に及ぶ巨大な数同士であっても、極めて高速に最大公約数を計算することが可能です。

基本的な定理と仕組み

2つの自然数 $a$ と $b$ （$a \ge b$）の最大公約数を $\gcd(a, b)$ と表します。ユークリッドの互除法は、以下の単純な定理に基づいています。

$$ a = bq + r \implies \gcd(a, b) = \gcd(b, r) $$

つまり、「 $a$ を $b$ で割ったときの商を $q$ 、余りを $r$ としたとき、 $a$ と $b$ の最大公約数は、 $b$ と $r$ の最大公約数に等しい」という性質です。

定理の証明

なぜ $\gcd(a, b) = \gcd(b, r)$ が成り立つのでしょうか。簡単に証明してみましょう。

$a$ と $b$ の任意の公約数を $d$ とします。このとき、 $a = md, b = nd$ （$m, n$ は整数）と表せます。
$a = bq + r$ より、 $r = a - bq$ となります。
これに代入すると、 $r = md - (nd)q = d(m - nq)$ となります。
$m - nq$ は整数なので、 $d$ は $r$ の約数でもあります。よって、 $a$ と $b$ の公約数 $d$ は、 $b$ と $r$ の公約数でもあります。
逆に、 $b$ と $r$ の公約数を $e$ とすると、 $b = k e, r = l e$ と表せます。
$a = bq + r = (k e)q + l e = e(kq + l)$ となり、 $e$ は $a$ の約数になります。よって、 $b$ と $r$ の公約数 $e$ は、 $a$ と $b$ の公約数でもあります。
したがって、 $\{a, b\}$ の公約数の集合と $\{b, r\}$ の公約数の集合は完全に一致し、その最大値である最大公約数も等しくなります。 $\blacksquare$

アルゴリズムのフローチャート

この性質を利用し、余りが $0$ になるまで割り算を繰り返すのがユークリッドの互除法です。

  flowchart TD
    Start["開始: a, b を入力"] --> Check{"b == 0 ?"}
    Check -- "Yes" --> End["GCD は a"]
    Check -- "No" --> Calc["r = a % b"]
    Calc --> Update["a = b, b = r"]
    Update --> Check

具体例での計算プロセス

例として、 $a = 1071$ と $b = 1029$ の最大公約数を求めてみましょう。

$1071 \div 1029 = 1 \cdots 42$ （$a=1029, b=42$ に更新）
$1029 \div 42 = 24 \cdots 21$ （$a=42, b=21$ に更新）
$42 \div 21 = 2 \cdots 0$ （余りが $0$ になったので終了）

最後に割る数として残った $21$ が、 $1071$ と $1029$ の最大公約数です。

プログラムによる実装

Pythonでの実装

Pythonでは、再帰関数を用いる方法と、 while ループを用いる方法があります。ループを用いる方が関数呼び出しのオーバーヘッドがなく高速です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def gcd_loop(a: int, b: int) -> int:
    """
    ループを用いたユークリッドの互除法の実装
    """
    while b != 0:
        a, b = b, a % b
    return a

def gcd_recursive(a: int, b: int) -> int:
    """
    再帰を用いたユークリッドの互除法の実装
    """
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

print(gcd_loop(1071, 1029))  # 出力: 21

C++での実装

C++17以降では <numeric> ヘッダに std::gcd が標準実装されていますが、自作する場合は以下のようになります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include <iostream>

// 最大公約数を計算する関数（再帰版）
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    std::cout << "GCD: " << gcd(1071, 1029) << std::endl; // 出力: 21
    return 0;
}

計算量とラメの定理

ユークリッドの互除法はどれくらい速いのでしょうか。この計算量については、1844年にフランスの数学者ガブリエル・ラメによって証明された ラメの定理 （Lamé’s theorem）が有名です。

ラメの定理 2つの自然数 $a, b$ （$a > b$）に対してユークリッドの互除法を適用したときの割り算の回数は、 $b$ の十進法での桁数の $5$ 倍以下である。

これにより、アルゴリズムの時間計算量は $O(\log(\min(a, b)))$ となります。

最悪のケース（最も割り算の回数が多くなるケース）は、フィボナッチ数列の隣り合う2項を与えた場合です。例えば、 $F_{n+2}$ と $F_{n+1}$ の最大公約数を求める過程は、常に商が $1$ になり、次々に小さいフィボナッチ数へと移行していきます。

拡張ユークリッドの互除法

最大公約数を求めるだけでなく、以下のベズーの等式（Bézout’s identity）を満たす整数 $x, y$ を求めるアルゴリズムに拡張したものを、 拡張ユークリッドの互除法 （Extended Euclidean algorithm）と呼びます。

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

拡張ユークリッドの互除法の実装

再帰呼び出しから戻る過程で、 $x, y$ の係数を逆算していきます。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
    """
    ax + by = gcd(a, b) を満たす (gcd, x, y) を返す関数
    """
    if b == 0:
        return a, 1, 0
    
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    
    return g, x, y

g, x, y = ext_gcd(111, 30)
print(f"gcd: {g}, x: {x}, y: {y}")
# 出力: gcd: 3, x: 3, y: -11
# 確認: 111 * 3 + 30 * (-11) = 333 - 330 = 3

現代社会における応用（RSA暗号など）

拡張ユークリッドの互除法は、単なる数学パズルではなく、現代のインターネット社会を支える不可欠な技術です。代表的な例が RSA暗号 です。RSA暗号の鍵生成プロセスでは、ある数 $e$ と、オイラー関数 $\phi(N)$ に対して、 $e d \equiv 1 \pmod{\phi(N)}$ を満たす秘密鍵 $d$ （モジュラ逆元）を求める必要があります。これは $ed + k\phi(N) = 1$ という形に変形できるため、まさに拡張ユークリッドの互除法を用いて高速に $d$ を計算することができます。