暗号技術や数論の世界では「モジュラー逆数」という概念が非常に重要な役割を果たします。PHPのGMP拡張機能には、この計算を簡単に行うための強力な関数「gmp_invert」が用意されています。今回はこの関数について、基礎から応用まで詳しく解説します。
gmp_invert関数の基本
gmp_invert関数は、モジュラー逆数（modular multiplicative inverse）を計算するための関数です。
GMP|false gmp_invert(GMP|string|int $num, GMP|string|int $modulo)パラメータ
- $num: 逆数を求めたい数値
- $modulo: 法となる数値（モジュロ）
戻り値
- $numのモジュラー逆数を表すGMP数値オブジェクトを返します
- 逆数が存在しない場合は
falseを返します
モジュラー逆数とは？
モジュラー逆数とは、次の条件を満たす数値$x$のことです：
$a \cdot x \equiv 1 \pmod{m}$
つまり、ある数$a$に対して、$m$を法（modulo）とする乗法逆元です。これは「$a$と$x$をかけた結果を$m$で割った余りが1になる」という意味です。
モジュラー逆数が存在するための条件は、$a$と$m$が互いに素（最大公約数が1）であることです。
基本的な使用例
<?php
// 5のmod 11における逆数
$a = gmp_init(5);
$m = gmp_init(11);
$inverse = gmp_invert($a, $m);
if ($inverse !== false) {
echo "5のmod 11における逆数: " . gmp_strval($inverse) . "\n";
// 検証: a * inverse ≡ 1 (mod m)
$product = gmp_mul($a, $inverse);
$remainder = gmp_mod($product, $m);
echo "検証: 5 × " . gmp_strval($inverse) . " ≡ " . gmp_strval($remainder) . " (mod 11)\n";
} else {
echo "逆数が存在しません\n";
}
?>逆数が存在しない場合
$a$と$m$が互いに素でない場合、モジュラー逆数は存在しません。
<?php
// 4のmod 8における逆数を計算
$a = gmp_init(4);
$m = gmp_init(8);
$inverse = gmp_invert($a, $m);
if ($inverse !== false) {
echo "4のmod 8における逆数: " . gmp_strval($inverse) . "\n";
} else {
echo "4のmod 8における逆数は存在しません\n";
// 理由を示す
$gcd = gmp_gcd($a, $m);
echo "理由: gcd(4, 8) = " . gmp_strval($gcd) . " > 1\n";
}
?>実用的な応用例
1. RSA暗号での秘密鍵の計算
RSA暗号では、公開鍵$e$に対する秘密鍵$d$は、$\phi(n)$を法とする$e$のモジュラー逆数として定義されます。
<?php
// シンプルなRSA鍵生成の例
function simple_rsa_key_generation($p, $q, $e) {
// p, qは素数
$p = gmp_init($p);
$q = gmp_init($q);
$e = gmp_init($e);
// n = p * q
$n = gmp_mul($p, $q);
// φ(n) = (p-1)(q-1)
$phi_n = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));
// eとφ(n)が互いに素か確認
$gcd = gmp_gcd($e, $phi_n);
if (gmp_cmp($gcd, 1) != 0) {
return "エラー: eとφ(n)が互いに素ではありません";
}
// 秘密鍵d = e^(-1) mod φ(n)
$d = gmp_invert($e, $phi_n);
return [
'public_key' => [gmp_strval($n), gmp_strval($e)],
'private_key' => gmp_strval($d)
];
}
// 例：小さな素数でRSA鍵生成
$keys = simple_rsa_key_generation(61, 53, 17);
echo "公開鍵(n, e): (" . $keys['public_key'][0] . ", " . $keys['public_key'][1] . ")\n";
echo "秘密鍵d: " . $keys['private_key'] . "\n";
// 検証: e * d ≡ 1 (mod φ(n))
$e = gmp_init(17);
$d = gmp_init($keys['private_key']);
$phi_n = gmp_mul(gmp_sub(61, 1), gmp_sub(53, 1));
$result = gmp_mod(gmp_mul($e, $d), $phi_n);
echo "検証: e * d ≡ " . gmp_strval($result) . " (mod φ(n))\n";
?>2. 合同式の解法
線形合同式 $ax \equiv b \pmod{m}$ を解くために使用できます。
<?php
// 線形合同式 ax ≡ b (mod m) を解く関数
function solve_linear_congruence($a, $b, $m) {
$a = gmp_init($a);
$b = gmp_init($b);
$m = gmp_init($m);
// aとmの最大公約数を求める
$g = gmp_gcd($a, $m);
// bがgで割り切れない場合、解は存在しない
if (gmp_cmp(gmp_mod($b, $g), 0) != 0) {
return "解なし";
}
// 方程式を簡略化
$a = gmp_div($a, $g);
$b = gmp_div($b, $g);
$m = gmp_div($m, $g);
// a^(-1) mod m を計算
$a_inv = gmp_invert($a, $m);
// x ≡ a^(-1) * b (mod m)
$x = gmp_mod(gmp_mul($a_inv, $b), $m);
// すべての解を計算
$solutions = [];
for ($i = 0; gmp_cmp($i, $g) < 0; $i = gmp_add($i, 1)) {
$solution = gmp_add($x, gmp_mul($i, $m));
$solutions[] = gmp_strval($solution);
}
return $solutions;
}
// 例: 3x ≡ 4 (mod 11) を解く
$a = 3;
$b = 4;
$m = 11;
$solutions = solve_linear_congruence($a, $b, $m);
echo "$a" . "x ≡ $b (mod $m) の解:\n";
if (is_array($solutions)) {
echo "x ≡ " . implode(" または x ≡ ", $solutions) . " (mod $m)\n";
} else {
echo $solutions . "\n";
}
// 検証
if (is_array($solutions)) {
foreach ($solutions as $solution) {
$check = ($a * $solution) % $m;
echo "検証: $a × $solution ≡ $check (mod $m)\n";
}
}
?>3. モジュラー除算
通常の除算のように、$(a \div b) \bmod m$ を計算したい場合、実はこれは $(a \times b^{-1}) \bmod m$ と同じです。
<?php
// モジュラー除算: (a / b) mod m = a * b^(-1) mod m
function modular_division($a, $b, $m) {
$a = gmp_init($a);
$b = gmp_init($b);
$m = gmp_init($m);
// bとmが互いに素か確認
$gcd = gmp_gcd($b, $m);
if (gmp_cmp($gcd, 1) != 0) {
return "エラー: bとmが互いに素ではありません";
}
// b^(-1) mod m を計算
$b_inv = gmp_invert($b, $m);
// 結果: (a * b^(-1)) mod m
$result = gmp_mod(gmp_mul($a, $b_inv), $m);
return gmp_strval($result);
}
// 例: (8 / 3) mod 13 を計算
$a = 8;
$b = 3;
$m = 13;
$result = modular_division($a, $b, $m);
echo "($a / $b) mod $m = $result\n";
// 検証: result * b ≡ a (mod m)
$verification = (gmp_intval(gmp_init($result)) * $b) % $m;
echo "検証: $result × $b ≡ $verification (mod $m)\n";
?>実用的な暗号アルゴリズムでの使用例
ElGamal暗号の例
ElGamal暗号は公開鍵暗号方式の一つで、復号時にモジュラー逆数が使われます。
<?php
// 非常に簡略化したElGamal暗号の例
function simple_elgamal_example() {
// 公開パラメータ
$p = gmp_init(23); // 素数
$g = gmp_init(5); // 原始根
// 秘密鍵と公開鍵
$private_key = gmp_init(6); // 秘密鍵
$public_key = gmp_powm($g, $private_key, $p); // y = g^x mod p
echo "公開パラメータ: p=" . gmp_strval($p) . ", g=" . gmp_strval($g) . "\n";
echo "公開鍵: " . gmp_strval($public_key) . "\n";
echo "秘密鍵: " . gmp_strval($private_key) . "\n";
// メッセージ暗号化
$m = gmp_init(7); // 暗号化したいメッセージ
echo "平文: " . gmp_strval($m) . "\n";
// エフェメラル鍵
$k = gmp_init(3);
// 暗号化: (c1, c2) = (g^k mod p, m * y^k mod p)
$c1 = gmp_powm($g, $k, $p);
$c2 = gmp_mod(gmp_mul($m, gmp_powm($public_key, $k, $p)), $p);
echo "暗号文: (c1=" . gmp_strval($c1) . ", c2=" . gmp_strval($c2) . ")\n";
// 復号: m = c2 * (c1^x)^(-1) mod p
$s = gmp_powm($c1, $private_key, $p);
$s_inv = gmp_invert($s, $p);
$decrypted = gmp_mod(gmp_mul($c2, $s_inv), $p);
echo "復号結果: " . gmp_strval($decrypted) . "\n";
}
// ElGamal暗号の例を実行
simple_elgamal_example();
?>アルゴリズムの内部動作
gmp_invert関数は内部的に拡張ユークリッドアルゴリズムを使用しています。このアルゴリズムは最大公約数を求めるだけでなく、ベズー恒等式のための係数も計算できます。
PHP自体で同様のアルゴリズムを実装すると、以下のようになります：
<?php
// 拡張ユークリッドアルゴリズムを使ったモジュラー逆数の計算
function extended_gcd($a, $b) {
$a = gmp_init($a);
$b = gmp_init($b);
if (gmp_cmp($a, 0) == 0) {
return [gmp_init($b), gmp_init(0), gmp_init(1)];
}
list($gcd, $x1, $y1) = extended_gcd(gmp_mod($b, $a), $a);
$x = gmp_sub($y1, gmp_mul(gmp_div($b, $a), $x1));
$y = $x1;
return [$gcd, $x, $y];
}
function my_gmp_invert($a, $m) {
$a = gmp_init($a);
$m = gmp_init($m);
// aを正の値に正規化
$a = gmp_mod($a, $m);
list($g, $x, $y) = extended_gcd($a, $m);
if (gmp_cmp($g, 1) != 0) {
// aとmが互いに素でない場合、逆数は存在しない
return false;
} else {
// 結果を0からm-1の範囲に正規化
return gmp_mod($x, $m);
}
}
// gmp_invertと自作関数の比較
$a = 7;
$m = 26;
$result1 = gmp_invert(gmp_init($a), gmp_init($m));
$result2 = my_gmp_invert($a, $m);
echo "$a のmod $m における逆数 (gmp_invert): " . gmp_strval($result1) . "\n";
echo "$a のmod $m における逆数 (自作関数): " . gmp_strval($result2) . "\n";
// 検証
$check = (gmp_intval($result1) * $a) % $m;
echo "検証: " . gmp_strval($result1) . " × $a ≡ $check (mod $m)\n";
?>パフォーマンスの考察
GMPライブラリの実装は最適化されているため、自作の実装よりもはるかに高速です。特に大きな数値を扱う場合、その差は顕著になります。
<?php
// パフォーマンス比較
// テスト用の中程度の大きさの数値
$a = "12345678901234567890";
$m = "98765432109876543211"; // 素数に近い値
// GMPライブラリの時間計測
$start = microtime(true);
$result1 = gmp_invert(gmp_init($a), gmp_init($m));
$gmp_time = microtime(true) - $start;
// 自作関数の時間計測
$start = microtime(true);
$result2 = my_gmp_invert($a, $m);
$custom_time = microtime(true) - $start;
echo "GMP時間: " . ($gmp_time * 1000) . "ミリ秒\n";
echo "自作関数時間: " . ($custom_time * 1000) . "ミリ秒\n";
echo "速度差: " . round($custom_time / $gmp_time, 2) . "倍\n";
// 結果が一致するか確認
if (gmp_cmp($result1, $result2) == 0) {
echo "結果は一致しています\n";
} else {
echo "結果が一致しません！\n";
}
?>使用時の注意点
1. モジュラー逆数の存在条件
$a$と$m$が互いに素でない場合、モジュラー逆数は存在しません。必ず事前にチェックするか、戻り値がfalseの場合の処理を用意しましょう。
<?php
function safe_invert($a, $m) {
$a = gmp_init($a);
$m = gmp_init($m);
// 互いに素かチェック
$gcd = gmp_gcd($a, $m);
if (gmp_cmp($gcd, 1) != 0) {
return ["exists" => false, "gcd" => gmp_strval($gcd)];
}
$inverse = gmp_invert($a, $m);
return ["exists" => true, "inverse" => gmp_strval($inverse)];
}
// 例
$tests = [
[35, 15], // gcd(35, 15) = 5
[7, 15], // gcd(7, 15) = 1
];
foreach ($tests as $test) {
list($a, $m) = $test;
$result = safe_invert($a, $m);
echo "$a のmod $m における逆数: ";
if ($result["exists"]) {
echo $result["inverse"] . "\n";
} else {
echo "存在しません (gcd = " . $result["gcd"] . ")\n";
}
}
?>2. 負の数の扱い
GMPでは負の数も適切に処理されますが、結果は必ず$0$から$m-1$の範囲になります。
<?php
// 負の数のモジュラー逆数
$tests = [
[3, 11],
[-3, 11],
[3, -11]
];
foreach ($tests as $test) {
list($a, $m) = $test;
$a_gmp = gmp_init($a);
$m_gmp = gmp_init($m);
// |m|を使用
$abs_m = gmp_abs($m_gmp);
// aをmod mで正規化
$norm_a = gmp_mod($a_gmp, $abs_m);
$inverse = gmp_invert($norm_a, $abs_m);
echo "$a のmod $m における逆数: " . ($inverse ? gmp_strval($inverse) : "存在しない") . "\n";
if ($inverse) {
// 検証
$check = gmp_mod(gmp_mul($norm_a, $inverse), $abs_m);
echo "検証: " . gmp_strval($norm_a) . " × " . gmp_strval($inverse) . " ≡ " . gmp_strval($check) . " (mod " . gmp_strval($abs_m) . ")\n";
}
}
?>まとめ
gmp_invert関数は、モジュラー算術における逆数計算を簡単かつ効率的に行うための強力なツールです。この関数を理解し活用することで：
- 暗号技術の実装：RSA、ElGamalなどの暗号アルゴリズムの鍵生成や復号処理
- 数論問題の解決：線形合同式の解法や、モジュラー除算
- 高度な数学計算：様々なモジュラー演算を使った科学技術計算
などを実装することができます。
ただし、使用時には逆数が存在するかどうかの条件（互いに素であること）を常に意識し、存在しない場合の処理も考慮しておくことが重要です。
PHP-GMPの他の関数と組み合わせることで、非常に大きな整数に対しても効率的に計算を行うことができ、暗号化や科学計算など幅広い分野で活用できます。
