1. 導入：なぜgmp_gcdextが重要なのか
PHPで大規模な数値計算や暗号アルゴリズムの実装を行う際、標準の整数型（int）の範囲を超える数値や、数学的な解法が必要になるケースがあります。特に「線形不定方程式（ax + by = c）」を解く際、手動で実装すると非常に複雑になりますが、PHPのGMP（GNU Multiple Precision）拡張に含まれるgmp_gcdext関数を使えば、効率的かつ正確に解を求めることができます。この関数は、単なる最大公約数（GCD）の算出だけでなく、拡張ユークリッドの互除法を適用することで、数学的なロジックをシンプルにコード化するのに役立ちます。
2. 基礎知識：拡張ユークリッドの互除法とは
通常の最大公約数（GCD）は「2つの数の公約数の中で最大の数」ですが、拡張ユークリッドの互除法は、さらに「as + bt = gcd(a, b)」を満たす整数sとtを求める手法です。
gmp_gcdext関数は、このsとtを計算して返します。暗号理論におけるモジュロ逆元の算出や、周期的なスケジューリング、資源配分アルゴリズムなど、エンジニアの実務において「計算の整合性を保証する」ために非常に強力なツールとなります。
3. 実装のポイント
gmp_gcdextは、引数として2つの数値（int, string, GMPオブジェクト）を受け取り、結果として「g（最大公約数）」「s」「t」の3つの要素を持つ配列を返します。
注意点として、返される値はGMPオブジェクトであるため、そのまま計算に使う場合はgmp_addやgmp_mulといったGMP専用関数を用いる必要があります。また、結果として出力される「s」や「t」は負の値になる可能性があるため、状況に応じて絶対値を取るなどの調整が必要です。
4. サンプルプログラム
以下のコードは、拡張ユークリッドの互除法を用いて、指定した数値の最大公約数と、方程式の解を求める実例です。
最大公約数, ‘s’ => 係数1, ‘t’ => 係数2]
$result = gmp_gcdext($num1, $num2);
// 計算結果の確認: as + bt = g
$calc = gmp_add(
gmp_mul($num1, $result[‘s’]),
gmp_mul($num2, $result[‘t’])
);
// 結果を表示（GMPオブジェクトは文字列変換が必要）
echo “最大公約数 (g): ” . gmp_strval($result[‘g’]) . PHP_EOL;
echo “係数 (s): ” . gmp_strval($result[‘s’]) . PHP_EOL;
echo “係数 (t): ” . gmp_strval($result[‘t’]) . PHP_EOL;
// 検算結果
echo “検証結果 (as + bt): ” . gmp_strval($calc) . PHP_EOL;
/
出力例:
最大公約数 (g): 3
係数 (s): 2
係数 (t): -1
検証結果 (as + bt): 3
/
?>
5. 応用・注意点
実務における重要な応用例として「モジュロ逆元」の計算があります。
gcd(a, b) = 1 のとき、as + bt = 1 となるため、これはモジュロ演算において as ≡ 1 (mod b) を意味します。つまり、sは「bを法とするaの逆元」となります。
注意点：
・GMP関数は処理速度が非常に速いですが、大規模なループ内で使用する場合はリソース管理に注意してください。
・gmp_gcdextは、負の入力値に対しても数学的に正しい結果を返しますが、アプリケーションの要件に応じて、結果の符号を正規化（正の数に変換）する処理を別途挟むのが一般的です。
・PHPの環境でGMP拡張がインストールされているか（php -m で確認）、事前に確認してください。多くのLinux環境ではデフォルトで有効ですが、Dockerコンテナ等ではパッケージの追加が必要な場合があります。