はじめに
拡張ユークリッドアルゴリズム（Extended Euclidean Algorithm）は、数論において非常に重要なアルゴリズムです。PHP で大きな整数に対してこのアルゴリズムを効率的に実行したい場合、GMP（GNU Multiple Precision）拡張モジュールの gmp_gcdext 関数が強力なツールとなります。今回は、この関数の使い方と応用例について詳しく解説します。
gmp_gcdext 関数とは？
gmp_gcdext 関数は、2つの整数 a, b に対して、その最大公約数（GCD）と、ベズー等式 ax + by = gcd(a,b) を満たす整数 x, y を同時に求める関数です。この機能は拡張ユークリッドアルゴリズムとして知られています。
基本的な構文
gmp_gcdext(GMP|int|string $a, GMP|int|string $b): array
$a: 最初の数値（GMP オブジェクト、整数値、または数値文字列）$b: 2番目の数値（GMP オブジェクト、整数値、または数値文字列）- 戻り値: 連想配列
['g' => GCD, 's' => x, 't' => y]g: a と b の最大公約数（GMP オブジェクト）s: ベズー係数 x（GMP オブジェクト）t: ベズー係数 y（GMP オブジェクト）
拡張ユークリッドアルゴリズムとは？
拡張ユークリッドアルゴリズムは、通常のユークリッドアルゴリズム（最大公約数を求めるアルゴリズム）を拡張したもので、最大公約数だけでなく、ベズーの等式 ax + by = gcd(a,b) を満たす整数 x, y も同時に求めることができます。
この等式は、線形ディオファントス方程式の解法や、モジュラー逆数の計算など、様々な数学的問題の解決に応用されます。
使用例
基本的な使い方
<?php
// 35と15の拡張GCDを計算
$result = gmp_gcdext(35, 15);
// 結果を出力
echo "GCD(35, 15) = " . gmp_strval($result['g']) . "\n";
echo "ベズー係数 x = " . gmp_strval($result['s']) . "\n";
echo "ベズー係数 y = " . gmp_strval($result['t']) . "\n";
// ベズー等式の検証: 35*x + 15*y = gcd
$verification = gmp_add(gmp_mul(35, $result['s']), gmp_mul(15, $result['t']));
echo "検証: 35*(" . gmp_strval($result['s']) . ") + 15*(" . gmp_strval($result['t']) . ") = " . gmp_strval($verification) . "\n";
/* 出力:
GCD(35, 15) = 5
ベズー係数 x = 1
ベズー係数 y = -2
検証: 35*(1) + 15*(-2) = 5
*/
?>
大きな数値での計算
<?php
// 非常に大きな数値での拡張GCD計算
$a = "12345678901234567890";
$b = "98765432109876543210";
$result = gmp_gcdext($a, $b);
echo "GCD($a, $b) = " . gmp_strval($result['g']) . "\n";
echo "ベズー係数 x = " . gmp_strval($result['s']) . "\n";
echo "ベズー係数 y = " . gmp_strval($result['t']) . "\n";
// ベズー等式の検証
$verification = gmp_add(gmp_mul($a, $result['s']), gmp_mul($b, $result['t']));
echo "検証: a*x + b*y = " . gmp_strval($verification) . "\n";
// 最大公約数と一致するか確認
if (gmp_cmp($verification, $result['g']) === 0) {
echo "ベズー等式が成立しています\n";
} else {
echo "エラー: ベズー等式が成立していません\n";
}
?>
実践的な活用例
モジュラー逆数の計算
モジュラー逆数は、暗号理論（特にRSA暗号）やモジュラー演算において重要な概念です。a に対するモジュロ m での逆数とは、(a * x) ≡ 1 (mod m) となる x のことです。
<?php
/**
* モジュラー逆数を計算する関数
* @param GMP|int|string $a 整数
* @param GMP|int|string $m モジュロ
* @return string|false 逆数（存在しない場合は false）
*/
function modular_inverse($a, $m) {
$a = gmp_init($a);
$m = gmp_init($m);
// 拡張ユークリッドアルゴリズムを使用
$result = gmp_gcdext($a, $m);
// GCD(a, m) = 1 でなければ逆数は存在しない
if (gmp_cmp($result['g'], 1) !== 0) {
return false;
}
// 結果が負の場合、m を加えて正の値にする
$inverse = $result['s'];
if (gmp_cmp($inverse, 0) < 0) {
$inverse = gmp_add($inverse, $m);
}
return gmp_strval($inverse);
}
// 例: 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 での逆数: 存在しない
?>
線形ディオファントス方程式の解法
線形ディオファントス方程式 ax + by = c の整数解を求める方法：
<?php
/**
* 線形ディオファントス方程式 ax + by = c の整数解を求める
* @param GMP|int|string $a 係数a
* @param GMP|int|string $b 係数b
* @param GMP|int|string $c 定数項c
* @return array|false 整数解の組 [x, y] または解なしの場合は false
*/
function solve_linear_diophantine($a, $b, $c) {
$a = gmp_init($a);
$b = gmp_init($b);
$c = gmp_init($c);
// 拡張ユークリッドアルゴリズムを使用
$result = gmp_gcdext($a, $b);
$gcd = $result['g'];
$x0 = $result['s'];
$y0 = $result['t'];
// c が gcd(a,b) で割り切れない場合、整数解は存在しない
if (gmp_cmp(gmp_mod($c, $gcd), 0) !== 0) {
return false;
}
// 方程式を gcd で割って簡略化
$a_prime = gmp_div_q($a, $gcd);
$b_prime = gmp_div_q($b, $gcd);
$c_prime = gmp_div_q($c, $gcd);
// 特殊解を計算
$x = gmp_mul($x0, $c_prime);
$y = gmp_mul($y0, $c_prime);
return [gmp_strval($x), gmp_strval($y)];
}
// 例: 方程式 35x + 15y = 10 の整数解
$solution = solve_linear_diophantine(35, 15, 10);
if ($solution !== false) {
echo "35x + 15y = 10 の特殊解: x = {$solution[0]}, y = {$solution[1]}\n";
// 検証
$check = gmp_add(gmp_mul(35, $solution[0]), gmp_mul(15, $solution[1]));
echo "検証: 35*({$solution[0]}) + 15*({$solution[1]}) = " . gmp_strval($check) . "\n";
// 一般解の形式を表示
echo "一般解: x = {$solution[0]} + " . gmp_strval(gmp_div_q(15, 5)) . "t, ";
echo "y = {$solution[1]} - " . gmp_strval(gmp_div_q(35, 5)) . "t (t は任意の整数)\n";
} else {
echo "方程式 35x + 15y = 10 には整数解が存在しません\n";
}
// 例: 方程式 6x + 9y = 15 の整数解
$solution2 = solve_linear_diophantine(6, 9, 15);
if ($solution2 !== false) {
echo "\n6x + 9y = 15 の特殊解: x = {$solution2[0]}, y = {$solution2[1]}\n";
} else {
echo "\n方程式 6x + 9y = 15 には整数解が存在しません\n";
}
// 例: 方程式 4x + 6y = 5 の整数解（解なし）
$solution3 = solve_linear_diophantine(4, 6, 5);
if ($solution3 !== false) {
echo "\n4x + 6y = 5 の特殊解: x = {$solution3[0]}, y = {$solution3[1]}\n";
} else {
echo "\n方程式 4x + 6y = 5 には整数解が存在しません\n";
}
?>
RSA暗号の鍵生成
RSA暗号では、公開鍵と秘密鍵の生成にモジュラー逆数の計算が必要で、これに gmp_gcdext が使用できます：
<?php
/**
* 簡易的なRSA鍵ペア生成（教育目的のみ - 実際の暗号化には使用しないでください）
* @param int $bits 鍵の長さ（ビット数）
* @return array 公開鍵と秘密鍵のペア
*/
function generate_rsa_keypair($bits = 512) {
// 大きな素数p, qを生成（簡易版）
$p = gmp_nextprime(gmp_random_bits($bits / 2));
$q = gmp_nextprime(gmp_random_bits($bits / 2));
// n = p * q
$n = gmp_mul($p, $q);
// φ(n) = (p-1)(q-1)
$phi = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));
// 公開指数 e を選ぶ（通常は 65537）
$e = gmp_init(65537);
// e と φ(n) が互いに素であることを確認
while (gmp_cmp(gmp_gcd($e, $phi), 1) !== 0) {
$e = gmp_nextprime($e);
}
// 秘密指数 d を計算: d ≡ e^(-1) (mod φ(n))
$result = gmp_gcdext($e, $phi);
$d = $result['s'];
// d が負の場合、φ(n) を加えて正にする
if (gmp_cmp($d, 0) < 0) {
$d = gmp_add($d, $phi);
}
return [
'public' => [
'n' => gmp_strval($n),
'e' => gmp_strval($e)
],
'private' => [
'n' => gmp_strval($n),
'd' => gmp_strval($d),
'p' => gmp_strval($p),
'q' => gmp_strval($q)
]
];
}
// RSA鍵ペアを生成（低ビット数なので実用的でありません）
$keypair = generate_rsa_keypair(128);
echo "RSA公開鍵:\n";
echo "n = " . $keypair['public']['n'] . "\n";
echo "e = " . $keypair['public']['e'] . "\n\n";
echo "RSA秘密鍵:\n";
echo "d = " . $keypair['private']['d'] . "\n";
// 検証: e*d ≡ 1 (mod φ(n))
$e = gmp_init($keypair['public']['e']);
$d = gmp_init($keypair['private']['d']);
$p = gmp_init($keypair['private']['p']);
$q = gmp_init($keypair['private']['q']);
$phi = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));
$check = gmp_mod(gmp_mul($e, $d), $phi);
echo "\n検証: (e*d) mod φ(n) = " . gmp_strval($check) . " (1であるべき)\n";
?>
GCD関連関数との違い
PHPのGMP拡張モジュールには、GCDに関連するいくつかの関数があります：
- gmp_gcd: 最大公約数のみを計算する。
- gmp_gcdext: 最大公約数とベズー係数も計算する。
- gmp_lcm: 最小公倍数を計算する。
<?php
$a = 35;
$b = 15;
// gmp_gcd: 最大公約数のみ
$gcd = gmp_gcd($a, $b);
echo "gmp_gcd($a, $b) = " . gmp_strval($gcd) . "\n";
// gmp_gcdext: 最大公約数とベズー係数
$gcdext = gmp_gcdext($a, $b);
echo "gmp_gcdext($a, $b) = [g=" . gmp_strval($gcdext['g']) .
", s=" . gmp_strval($gcdext['s']) .
", t=" . gmp_strval($gcdext['t']) . "]\n";
// gmp_lcm: 最小公倍数
$lcm = gmp_lcm($a, $b);
echo "gmp_lcm($a, $b) = " . gmp_strval($lcm) . "\n";
/*
出力:
gmp_gcd(35, 15) = 5
gmp_gcdext(35, 15) = [g=5, s=1, t=-2]
gmp_lcm(35, 15) = 105
*/
?>
注意点
- ゼロとの計算:
gmp_gcdext(a, 0)では、GCD は |a| になり、ベズー係数は s=sign(a), t=0 になります。また、gmp_gcdext(0, b)では、GCD は |b| になり、ベズー係数は s=0, t=sign(b) になります。 - 負の数:
gmp_gcdextは負の数に対しても正しく動作し、適切なベズー係数を計算します。 - ベズー係数の非一意性: ベズー等式を満たす係数の組は無数に存在します。
gmp_gcdextは特定のアルゴリズムに基づいて1つの解を返します。 - GMP 拡張モジュール: この関数を使用するには、PHP に GMP 拡張モジュールがインストールされている必要があります。
まとめ
gmp_gcdext 関数は、PHP で拡張ユークリッドアルゴリズムを効率的に実行するための強力なツールです。最大公約数を求めるだけでなく、ベズー等式の係数も同時に計算できるため、モジュラー逆数の計算や線形ディオファントス方程式の解法、暗号理論のアルゴリズム実装など、様々な高度な数学的応用が可能になります。
特に大きな整数を扱う場面では、GMP 拡張モジュールの多倍長整数演算と組み合わせることで、高精度かつ効率的な計算が実現できます。数論や暗号理論に関連するアプリケーション開発において、gmp_gcdext は非常に価値のある関数と言えるでしょう。
