［PHP］多倍長整数で最大公約数を求める：gmp_gcd 関数の完全ガイド

PHP

はじめに

最大公約数（GCD: Greatest Common Divisor）は数学や暗号理論、アルゴリズムにおいて非常に重要な概念です。PHP で大きな整数の最大公約数を効率的に求めたい場合、GMP（GNU Multiple Precision）拡張モジュールの gmp_gcd 関数が強力なツールとなります。この記事では、gmp_gcd 関数の基本から応用までを詳しく解説します。

gmp_gcd 関数とは？

gmp_gcd 関数は、2つの整数の最大公約数（GCD）を計算するための GMP ライブラリの関数です。最大公約数とは、2つ以上の整数を同時に割り切ることができる最大の整数のことです。

基本的な構文

gmp_gcd(GMP|int|string $num1, GMP|int|string $num2): GMP
  • $num1: 最初の数値（GMP オブジェクト、整数値、または数値文字列）
  • $num2: 2番目の数値（GMP オブジェクト、整数値、または数値文字列）
  • 戻り値: 最大公約数を表す GMP オブジェクト

最大公約数（GCD）とは？

2つの整数 a と b の最大公約数は、a と b の両方を割り切ることができる最大の整数です。例えば、12 と 18 の最大公約数は 6 です。最大公約数は数論において基本的かつ重要な概念で、既約分数の計算、モジュラー逆数の計算、暗号アルゴリズムなど、様々な場面で利用されます。

使用例

基本的な使い方

<?php
// 12と18の最大公約数を計算
$gcd1 = gmp_gcd(12, 18);
echo "gcd(12, 18) = " . gmp_strval($gcd1) . "\n"; // 出力: gcd(12, 18) = 6

// 大きな数値の最大公約数
$a = "12345678901234567890";
$b = "98765432109876543210";
$gcd2 = gmp_gcd($a, $b);
echo "gcd($a, $b) = " . gmp_strval($gcd2) . "\n"; // 出力: gcd(12345678901234567890, 98765432109876543210) = 90
?>

GMP オブジェクトを使用する例

<?php
// GMP オブジェクトを使った計算
$a = gmp_init("123456789012345678901234567890");
$b = gmp_init("987654321098765432109876543210");
$gcd = gmp_gcd($a, $b);

echo "最大公約数: " . gmp_strval($gcd) . "\n";
// 出力例: 最大公約数: 90
?>

負の数値での計算

gmp_gcd は負の数値に対しても動作し、常に非負の結果を返します：

<?php
// 負の数の最大公約数
$gcd1 = gmp_gcd(-42, 56);
echo "gcd(-42, 56) = " . gmp_strval($gcd1) . "\n"; // 出力: gcd(-42, 56) = 14

$gcd2 = gmp_gcd(-105, -140);
echo "gcd(-105, -140) = " . gmp_strval($gcd2) . "\n"; // 出力: gcd(-105, -140) = 35
?>

実践的な活用例

分数の約分（既約分数への変換）

<?php
/**
 * 分数を既約形に約分する関数
 * @param GMP|int|string $numerator 分子
 * @param GMP|int|string $denominator 分母
 * @return array 約分された[分子, 分母]
 */
function reduce_fraction($numerator, $denominator) {
    // GMP オブジェクトに変換
    $num = gmp_init($numerator);
    $den = gmp_init($denominator);
    
    // 最大公約数を計算
    $gcd = gmp_gcd($num, $den);
    
    // GCDで割って約分
    $reduced_num = gmp_div_q($num, $gcd);
    $reduced_den = gmp_div_q($den, $gcd);
    
    return [gmp_strval($reduced_num), gmp_strval($reduced_den)];
}

// 例: 36/48 を約分
list($num, $den) = reduce_fraction(36, 48);
echo "36/48 を約分: $num/$den\n"; // 出力: 36/48 を約分: 3/4

// 大きな分数の約分
$large_num = "123456789012345678901234567890";
$large_den = "987654321098765432109876543210";
list($num, $den) = reduce_fraction($large_num, $large_den);
echo "$large_num/$large_den を約分:\n$num/$den\n";
// 出力例: 123456789012345678901234567890/987654321098765432109876543210 を約分:
// 1371742100137174210013717421/10973936901097393690109739369
?>

拡張ユークリッドアルゴリズム（GCDと線形結合係数を求める）

<?php
/**
 * 拡張ユークリッドアルゴリズム
 * GCD(a, b) = ax + by を満たす整数 x, y を求める
 * 
 * @param GMP|int|string $a 整数1
 * @param GMP|int|string $b 整数2
 * @return array [gcd, x, y] を含む配列
 */
function extended_gcd($a, $b) {
    $a = gmp_init($a);
    $b = gmp_init($b);
    
    // 初期値設定
    $s = gmp_init(0); $old_s = gmp_init(1);
    $t = gmp_init(1); $old_t = gmp_init(0);
    $r = $b; $old_r = $a;
    
    while (gmp_cmp($r, 0) !== 0) {
        $quotient = gmp_div_q($old_r, $r);
        
        // r の更新
        $temp = $r;
        $r = gmp_sub($old_r, gmp_mul($quotient, $r));
        $old_r = $temp;
        
        // s の更新
        $temp = $s;
        $s = gmp_sub($old_s, gmp_mul($quotient, $s));
        $old_s = $temp;
        
        // t の更新
        $temp = $t;
        $t = gmp_sub($old_t, gmp_mul($quotient, $t));
        $old_t = $temp;
    }
    
    return [
        'gcd' => gmp_strval($old_r),
        'x' => gmp_strval($old_s),
        'y' => gmp_strval($old_t)
    ];
}

// 例: 35と15のGCDと係数を求める
$result = extended_gcd(35, 15);
echo "GCD(35, 15) = {$result['gcd']} = 35*({$result['x']}) + 15*({$result['y']})\n";
// 出力: GCD(35, 15) = 5 = 35*(1) + 15*(-2)

// 検証
$verification = gmp_add(gmp_mul(35, $result['x']), gmp_mul(15, $result['y']));
echo "検証: 35*({$result['x']}) + 15*({$result['y']}) = " . gmp_strval($verification) . "\n";
// 出力: 検証: 35*(1) + 15*(-2) = 5
?>

モジュラー逆数の計算

モジュラー逆数は、暗号理論やRSAアルゴリズムなどで重要です：

<?php
/**
 * モジュラー逆数を計算する関数
 * a * x ≡ 1 (mod m) となる x を求める
 * 
 * @param GMP|int|string $a 整数
 * @param GMP|int|string $m モジュロ
 * @return string 逆数（存在しない場合は false）
 */
function modular_inverse($a, $m) {
    $a = gmp_init($a);
    $m = gmp_init($m);
    
    // GCD(a, m) = 1 でなければ逆数は存在しない
    $gcd = gmp_gcd($a, $m);
    if (gmp_cmp($gcd, 1) !== 0) {
        return false;
    }
    
    // 拡張ユークリッドアルゴリズムを使用
    $result = extended_gcd($a, $m);
    $x = $result['x'];
    
    // 結果が負の場合、m を加えて正の値にする
    if (gmp_cmp($x, 0) < 0) {
        $x = gmp_add($x, $m);
    }
    
    return gmp_strval($x);
}

// 例: 3 のモジュロ 11 での逆数
$inverse = modular_inverse(3, 11);
echo "3 のモジュロ 11 での逆数: " . ($inverse !== false ? $inverse : "存在しない") . "\n";
// 出力: 3 のモジュロ 11 での逆数: 4

// 検証: (3 * 4) mod 11 = 1 になるはず
$check = gmp_mod(gmp_mul(3, $inverse), 11);
echo "検証: (3 * $inverse) mod 11 = " . gmp_strval($check) . "\n";
// 出力: 検証: (3 * 4) mod 11 = 1

// 例: 4 のモジュロ 8 での逆数（存在しない）
$inverse2 = modular_inverse(4, 8);
echo "4 のモジュロ 8 での逆数: " . ($inverse2 !== false ? $inverse2 : "存在しない") . "\n";
// 出力: 4 のモジュロ 8 での逆数: 存在しない
?>

複数の数の最大公約数

3つ以上の数の最大公約数を求める場合：

<?php
/**
 * 複数の数の最大公約数を計算する関数
 * @param array $numbers 数値の配列
 * @return GMP 最大公約数
 */
function gcd_multiple($numbers) {
    if (empty($numbers)) {
        return gmp_init(0);
    }
    
    $result = gmp_init(abs($numbers[0]));
    $count = count($numbers);
    
    for ($i = 1; $i < $count; $i++) {
        $result = gmp_gcd($result, $numbers[$i]);
        
        // GCD が 1 になった場合、早期終了（これ以上小さくはならない）
        if (gmp_cmp($result, 1) === 0) {
            break;
        }
    }
    
    return $result;
}

// 例: [24, 36, 48, 60] の最大公約数
$numbers = [24, 36, 48, 60];
$gcd = gcd_multiple($numbers);
echo "GCD(" . implode(", ", $numbers) . ") = " . gmp_strval($gcd) . "\n";
// 出力: GCD(24, 36, 48, 60) = 12
?>

注意点

  1. ゼロとの最大公約数: gmp_gcd(a, 0) は、（ゼロでない）a の絶対値を返します。数学的には、GCD(a, 0) = |a| と定義されています。
  2. 負の数: gmp_gcd は負の数に対しても正しく動作し、常に非負の結果を返します。
  3. パフォーマンス: gmp_gcd は効率的なユークリッドアルゴリズムを使用しているため、非常に大きな数の最大公約数でも高速に計算できます。
  4. GMP 拡張モジュール: この関数を使用するには、PHP に GMP 拡張モジュールがインストールされている必要があります。

まとめ

gmp_gcd 関数は、PHP で大きな整数の最大公約数を効率的に計算するための強力なツールです。分数の約分、拡張ユークリッドアルゴリズム、モジュラー逆数の計算など、様々な数学的問題や暗号理論の実装に役立ちます。

GMP を使うことで、標準の整数型では扱えないような巨大な数値でも、正確かつ効率的に最大公約数を求めることができます。数論や暗号理論に関わるアプリケーション開発において、gmp_gcd 関数は必須のツールと言えるでしょう。

タイトルとURLをコピーしました