［PHP］gmp_mod関数完全ガイド：大きな整数の剰余計算を極める

PHP

はじめに

大きな整数を扱うプログラミングにおいて、剰余演算（mod演算）は暗号化、ハッシュ関数、数論アルゴリズムなど、様々な場面で重要な役割を果たします。PHPの標準的な演算子では扱えない大きな整数の剰余計算を可能にするのがgmp_mod関数です。この関数はGMP（GNU Multiple Precision）拡張の一部であり、任意精度の整数演算を提供します。

gmp_mod関数の基本

構文

GMP gmp_mod ( GMP|int|string $n , GMP|int|string $d )

パラメータ

  • $n: 被除数（割られる数）
  • $d: 除数（割る数）

戻り値

  • $n を $d で割った余り（GMP数値）

gmp_mod関数の特徴

gmp_mod関数には以下のような特徴があります：

  1. 任意精度: PHPの整数限界（通常は32ビットまたは64ビット）を超える数値でも精度を失わずに計算できます。
  2. 負の数の処理: 数学的な定義に従い、常に0以上d未満の結果を返します。
  3. 効率性: 大きな数値でも効率的に計算されます。

基本的な使用例

単純な剰余計算

<?php
// 基本的な剰余計算
$remainder1 = gmp_mod(10, 3);  // 1
$remainder2 = gmp_mod(15, 6);  // 3

echo "10 mod 3 = " . gmp_strval($remainder1) . "\n";
echo "15 mod 6 = " . gmp_strval($remainder2) . "\n";
?>

大きな数値での剰余計算

<?php
// 大きな整数での剰余計算
$big_number = "12345678901234567890123456789";
$modulus = "987654321";

$remainder = gmp_mod($big_number, $modulus);
echo "$big_number mod $modulus = " . gmp_strval($remainder) . "\n";
?>

負の数での剰余計算

<?php
// 負の数での剰余計算
$negative_mod1 = gmp_mod(-10, 3);  // 2 (数学的には常に正の剰余を返す)
$negative_mod2 = gmp_mod(-15, 4);  // 1

echo "-10 mod 3 = " . gmp_strval($negative_mod1) . "\n";
echo "-15 mod 4 = " . gmp_strval($negative_mod2) . "\n";
?>

実用的な応用例

1. 暗号化のための剰余計算（RSA暗号の例）

<?php
function simple_rsa_encrypt($message, $e, $n) {
    // 非常に単純化したRSA暗号化の例
    // 実際の実装ではより多くの要素が必要です
    return gmp_powm($message, $e, $n);
}

function simple_rsa_decrypt($cipher, $d, $n) {
    // 非常に単純化したRSA復号化の例
    return gmp_powm($cipher, $d, $n);
}

// 非常に小さなキーペア（実際の実装では大きな素数を使用）
$n = "3233"; // n = p*q (p=61, q=53)
$e = "17";   // 公開指数
$d = "2753"; // 秘密指数

$message = "65";  // 暗号化したいメッセージ（数値）
$cipher = simple_rsa_encrypt($message, $e, $n);
$decrypted = simple_rsa_decrypt($cipher, $d, $n);

echo "元のメッセージ: $message\n";
echo "暗号化された値: " . gmp_strval($cipher) . "\n";
echo "復号化された値: " . gmp_strval($decrypted) . "\n";
?>

2. モジュラ逆数の計算

<?php
function modular_inverse($a, $m) {
    // 拡張ユークリッドアルゴリズムを使用
    $g = gmp_gcdext($a, $m);
    
    if (gmp_strval($g['g']) != '1') {
        return "逆元が存在しません";
    } else {
        // 負の結果を正の値に変換
        $x = gmp_mod($g['s'], $m);
        return $x;
    }
}

$a = 7;
$m = 11;
$inverse = modular_inverse($a, $m);

echo "$a のモジュロ $m における逆元: " . gmp_strval($inverse) . "\n";
?>

3. 合同式の解

<?php
function solve_congruence($a, $b, $m) {
    // ax ≡ b (mod m) を解く
    $gcd = gmp_gcd($a, $m);
    $gcd_val = gmp_strval($gcd);
    
    if (gmp_strval(gmp_mod($b, $gcd)) != '0') {
        return "解が存在しません";
    }
    
    // a, b, m をgcdで割る
    $a = gmp_div($a, $gcd);
    $b = gmp_div($b, $gcd);
    $m = gmp_div($m, $gcd);
    
    // a^(-1) * b mod m を計算
    $a_inv = modular_inverse($a, $m);
    $x0 = gmp_mod(gmp_mul($a_inv, $b), $m);
    
    // 全ての解を生成
    $solutions = [];
    for ($i = 0; $i < $gcd_val; $i++) {
        $solutions[] = gmp_strval(gmp_add($x0, gmp_mul($i, $m)));
    }
    
    return $solutions;
}

// 3x ≡ 4 (mod 7) を解く
$a = 3;
$b = 4;
$m = 7;
$solutions = solve_congruence($a, $b, $m);

echo "{$a}x ≡ {$b} (mod {$m}) の解:\n";
if (is_array($solutions)) {
    echo implode(", ", $solutions) . "\n";
} else {
    echo $solutions . "\n";
}
?>

4. 周期性を利用した大きな冪剰余の計算

<?php
function efficient_power_mod($base, $exponent, $modulus) {
    // フェルマーの小定理を使用して計算を最適化
    if (gmp_prob_prime($modulus, 10) && gmp_cmp($exponent, $modulus) > 0) {
        // pが素数の場合、a^p ≡ a (mod p)が成り立つ
        // よって a^e ≡ a^(e mod (p-1)) (mod p) が成り立つ
        $reduced_exp = gmp_mod($exponent, gmp_sub($modulus, 1));
        return gmp_powm($base, $reduced_exp, $modulus);
    } else {
        // 一般的なケース
        return gmp_powm($base, $exponent, $modulus);
    }
}

$base = 7;
$exponent = "12345678901234567890";
$modulus = 17; // 素数

$result = efficient_power_mod($base, $exponent, $modulus);
echo "$base^$exponent mod $modulus = " . gmp_strval($result) . "\n";
?>

5. 中国剰余定理の実装

<?php
function chinese_remainder_theorem($remainders, $moduli) {
    if (count($remainders) != count($moduli)) {
        return "残りと法の配列の長さが一致しません";
    }
    
    // 全ての法の積を計算
    $prod = gmp_init(1);
    foreach ($moduli as $mod) {
        $prod = gmp_mul($prod, $mod);
    }
    
    $result = gmp_init(0);
    for ($i = 0; $i < count($remainders); $i++) {
        $p = gmp_div($prod, $moduli[$i]);
        $inverse = modular_inverse($p, $moduli[$i]);
        $result = gmp_add($result, gmp_mul(gmp_mul($remainders[$i], $p), $inverse));
    }
    
    return gmp_mod($result, $prod);
}

// x ≡ 2 (mod 3)
// x ≡ 3 (mod 5)
// x ≡ 2 (mod 7)
$remainders = [2, 3, 2];
$moduli = [3, 5, 7];

$result = chinese_remainder_theorem($remainders, $moduli);
echo "中国剰余定理による解: " . gmp_strval($result) . "\n";
?>

パフォーマンスと注意点

パフォーマンス

GMPの実装は高度に最適化されており、大きな数値でも効率的に計算が行われます。特に、以下のような特徴があります：

  1. ビット単位の最適化: 内部的には効率的なビット操作が使われています。
  2. 高速なアルゴリズム: 大きな数値に対する特殊な除算アルゴリズムが実装されています。

注意点

  1. GMP拡張が必要: この関数を使用するには、PHPにGMP拡張がインストールされている必要があります。
<?php
if (!extension_loaded('gmp')) {
    echo "GMP拡張がインストールされていません。\n";
    exit;
}
?>
  1. 0による除算: 除数が0の場合、エラーが発生します。
<?php
try {
    $result = gmp_mod(10, 0); // これはエラーになります
} catch (Error $e) {
    echo "エラー: " . $e->getMessage() . "\n";
}
?>
  1. 戻り値の型: 結果はGMP数値型で返されるため、通常のPHP整数として使用するには変換が必要です。
<?php
$remainder = gmp_mod(10, 3);
// GMP数値として直接使用
$result1 = gmp_add($remainder, 5);
// 文字列に変換
$remainder_str = gmp_strval($remainder);
// 整数に変換
$remainder_int = intval($remainder_str);
?>

PHP組み込みの剰余演算子との比較

PHPの通常の剰余演算子（%）とgmp_mod関数の主な違いは以下の通りです：

  1. 精度: %演算子はPHPの整数限界（通常は32ビットまたは64ビット）に制限されますが、gmp_modは任意精度です。
  2. 負の数の扱い: %演算子は被除数の符号に合わせた剰余を返しますが、gmp_modは常に正の剰余（0以上d未満）を返します。
<?php
// PHP標準の%演算子と比較
$php_mod = -10 % 3;  // -1
$gmp_mod = gmp_strval(gmp_mod(-10, 3));  // 2

echo "PHP (-10 % 3) = $php_mod\n";
echo "GMP (gmp_mod(-10, 3)) = $gmp_mod\n";
?>

まとめ

gmp_mod関数は、PHPで大きな整数の剰余計算を行うための強力なツールです。暗号理論や数論アルゴリズムを実装する際に特に役立ちます。標準の演算子では扱えない大きな数値でも正確な計算が可能で、特に負の数の扱いが数学的な定義に従っている点が特徴です。

GMP拡張の他の関数と組み合わせることで、高度な数学的アルゴリズムを効率的に実装できます。大きな整数を扱う必要がある場合には、ぜひGMP拡張とgmp_mod関数を活用してみてください。

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