Zenn
📘

【C#アルゴリズム】拡張ユークリッドの互除法

2024/11/28に公開
C#
アルゴリズム
tech

はじめに

paiza　で拡張ユークリッドの互除法にまつわる問題が出てきたのでこれについてまとめました。

拡張ユークリッドの互除法 (Extended Euclidean Algorithm)

拡張ユークリッドの互除法は、通常のユークリッドの互除法を拡張して、以下のような整数 x と y を求める方法です。

問題

整数 a, b に対して、以下の 線形整数方程式を満たす x, y を求めます：
\text{GCD}(a, b) = ax + by
ここで、\text{GCD}(a, b) は a と b の最大公約数です。

概要

拡張ユークリッドの互除法では、通常の互除法で最大公約数を計算する過程で、逆方向に操作を展開して、x, y を求めます。

通常のユークリッドの互除法

  1. a > b とする。
  2. ユークリッドの互除法を適用：
    a = q \cdot b + r \quad \text{(余り \(r = a \mod b\))}
    最大公約数は、b と r に対して再帰的に計算されます。

拡張版の手順

  1. 通常のユークリッドの互除法で最大公約数を計算。
  2. 逆にたどり、r を x, y の線形結合として表現します。

具体例

例: a = 30, b = 20

  1. ユークリッドの互除法
    30 = 1 \cdot 20 + 10
    20 = 2 \cdot 10 + 0
    最大公約数は \text{GCD}(30, 20) = 10。

  2. 逆方向で展開

    1. 10 = 30 - 1 \cdot 20（第1式）
    2. ここで終了（余りが0になったため）。

  3. 結果
    10 = 30 \cdot 1 + 20 \cdot (-1)
    x = 1, y = -1。

C#での実装

以下は、拡張ユークリッドの互除法を実装したコードです。

using System;

class Program
{
    static void Main()
    {
        int a = 30, b = 20;

        // 拡張ユークリッドの互除法を適用
        (int gcd, int x, int y) = ExtendedGcd(a, b);

        Console.WriteLine($"GCD: {gcd}");
        Console.WriteLine($"x: {x}, y: {y}");
        Console.WriteLine($"Verification: {a}*{x} + {b}*{y} = {gcd}");
    }

    private static (int gcd, int x, int y) ExtendedGcd(int a, int b)
    {
        if (b == 0)
        {
            return (a, 1, 0); // 基底ケース: gcd(a, 0) = a, x = 1, y = 0
        }

        // 再帰的にGCDを計算
        (int gcd, int x1, int y1) = ExtendedGcd(b, a % b);

        // xとyを更新
        int x = y1;
        int y = x1 - (a / b) * y1;

        return (gcd, x, y);
    }
}

実行結果

例として、(a = 30, b = 20) の場合:

GCD: 10
x: 1, y: -1
Verification: 30*1 + 20*(-1) = 10

応用例

  1. 整数方程式の解
    ax + by = c の形の方程式が解を持つのは、\text{GCD}(a, b) が c を割り切るときです。
    拡張ユークリッドで、初期解を得ることができます。

  2. 数論・暗号理論
    RSA暗号など、数論的問題でしばしば利用されます。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion