［PHP］数論関数「gmp_legendre」完全ガイド：ルジャンドル記号の理解と活用法

はじめに
gmp_legendre関数の基本
1. 基本構文
ルジャンドル記号とは
gmp_jacobi、gmp_kroneckerとの違い
使用例
1. 基本的な使い方
2. 大きな素数での計算
実用的な応用例
パフォーマンスと注意点
1. パフォーマンス
2. 注意点
まとめ

はじめに

数論や暗号理論を扱うプログラマーにとって、PHPのGMP拡張が提供する数学関数は非常に価値のあるツールです。今回は「gmp_legendre」関数に焦点を当て、その機能と実践的な使い方について詳しく解説します。この関数はルジャンドル記号を計算するもので、合同式の解の存在性判定や暗号アルゴリズムにおいて重要な役割を果たします。

gmp_legendre関数の基本

gmp_legendre関数は、PHPのGMP（GNU Multiple Precision）拡張に含まれる関数で、ルジャンドル記号（Legendre symbol）を計算します。

基本構文

int gmp_legendre ( GMP|int|string $a , GMP|int|string $p )

$a: 任意の整数
$p: 素数である必要がある整数

関数は次の3つの値のいずれかを返します：

+1：aはpを法として平方剰余
-1：aはpを法として平方非剰余
0：aはpで割り切れる

ルジャンドル記号とは

ルジャンドル記号は数論において重要な概念で、整数aと素数pに対して、aがpを法とする平方剰余であるか平方非剰余であるかを示します。数学的に次のように定義されます：

(a/p) = +1：xという整数が存在し、x² ≡ a (mod p)が成り立つ（aは平方剰余）
(a/p) = -1：そのようなxが存在しない（aは平方非剰余）
(a/p) = 0：aがpで割り切れる

gmp_jacobi、gmp_kroneckerとの違い

PHP GMPには類似の関数としてgmp_jacobiとgmp_kroneckerがありますが、それぞれ次のような違いがあります：

gmp_legendre: 第2引数は素数である必要があります
gmp_jacobi: 第2引数は奇数の正の整数が可能（素数でなくてもOK）
gmp_kronecker: 第2引数はどんな整数でも可能（偶数や負数、0も可）

これらの関数の関係は次のようになります：

第2引数が素数の場合、3つの関数は全て同じ結果を返します
第2引数が合成数の場合、gmp_legendreは正しい結果を返さない可能性があります

使用例

基本的な使い方

<?php
// 基本的な使用例
$result1 = gmp_legendre(4, 7);  // 1 (4は7を法として平方剰余)
$result2 = gmp_legendre(5, 7);  // -1 (5は7を法として平方非剰余)
$result3 = gmp_legendre(7, 7);  // 0 (7は7で割り切れる)

echo "ルジャンドル記号(4/7) = $result1\n";
echo "ルジャンドル記号(5/7) = $result2\n";
echo "ルジャンドル記号(7/7) = $result3\n";
?>

大きな素数での計算

<?php
// 大きな素数での計算
$large_prime = "1000000007"; // 10億7（素数）
$result4 = gmp_legendre(2, $large_prime);
$result5 = gmp_legendre(3, $large_prime);

echo "ルジャンドル記号(2/$large_prime) = $result4\n";
echo "ルジャンドル記号(3/$large_prime) = $result5\n";
?>

実用的な応用例

1. 平方剰余の判定

整数aが素数pを法として平方剰余かどうかを判定します。

<?php
function is_quadratic_residue($a, $p) {
    // $pは素数を想定
    $result = gmp_legendre($a, $p);
    
    if ($result == 1) {
        return "$a は $p を法として平方剰余です";
    } elseif ($result == -1) {
        return "$a は $p を法として平方非剰余です";
    } else {
        return "$a は $p で割り切れます";
    }
}

$tests = [
    [4, 11],
    [3, 11],
    [11, 11]
];

foreach ($tests as [$a, $p]) {
    echo is_quadratic_residue($a, $p) . "\n";
}
?>

2. 平方根の存在判定と計算

素数pを法としたときに、aの平方根が存在するかを判定し、存在する場合は平方根を計算します。

<?php
function modular_sqrt($a, $p) {
    if (gmp_legendre($a, $p) != 1) {
        return "平方根は存在しません";
    }
    
    // pが4k+3形式の素数の場合の特殊な計算法
    if (gmp_mod($p, 4) == 3) {
        $exp = gmp_add(gmp_div($p, 4), 1);
        $sqrt = gmp_powm($a, $exp, $p);
        return "$a mod $p の平方根は " . gmp_strval($sqrt) . " または " . gmp_strval(gmp_sub($p, $sqrt));
    }
    
    // ※注意：一般的な素数に対するTonelli-Shanksアルゴリズムの実装は省略
    return "この素数形式にはより複雑なアルゴリズムが必要です";
}

echo modular_sqrt(2, 7) . "\n";  // 不存在
echo modular_sqrt(4, 7) . "\n";  // 存在する (4 mod 7 の平方根は 2 または 5)
?>

3. 疑似乱数生成（二次剰余に基づく）

ルジャンドル記号の性質を利用した簡易的な疑似乱数生成器の例です。

<?php
function legendre_prng($seed, $p, $length) {
    $sequence = [];
    $x = $seed;
    
    for ($i = 0; $i < $length; $i++) {
        $x = ($x * $x + 1) % $p;
        $bit = (gmp_legendre($x, $p) + 1) / 2; // 0または1に変換
        $sequence[] = $bit;
    }
    
    return $sequence;
}

$prime = 1000003; // 適当な大きな素数
$random_bits = legendre_prng(12345, $prime, 20);
echo "生成されたビット列: " . implode('', $random_bits) . "\n";
?>

4. 二次剰余を利用した簡易暗号

ルジャンドル記号の性質を利用した非常に単純な暗号化の例です（実用性はありません）。

<?php
function simple_legendre_encrypt($message, $p) {
    $encrypted = [];
    $message_bytes = unpack('C*', $message);
    
    foreach ($message_bytes as $byte) {
        // バイトを二次剰余または非剰余となる数に変換
        $encrypted_byte = $byte;
        while (gmp_legendre($encrypted_byte, $p) != 1) {
            $encrypted_byte = ($encrypted_byte + 1) % 256;
        }
        $encrypted[] = $encrypted_byte;
    }
    
    return $encrypted;
}

function simple_legendre_decrypt($encrypted, $p) {
    $decrypted = [];
    
    foreach ($encrypted as $value) {
        // すべての平方剰余は暗号化前のバイト値か、その変形後の値
        // 実際の復号化はより複雑になります
        $decrypted[] = $value;
    }
    
    return pack('C*', ...$decrypted);
}

$prime = 1000003;
$message = "Hello";
$encrypted = simple_legendre_encrypt($message, $prime);
echo "暗号化: " . implode(' ', $encrypted) . "\n";
// 注：この単純な例では復号化は正確ではありません
?>

パフォーマンスと注意点

パフォーマンス

gmp_legendre関数はGMP拡張の一部であり、効率的なC言語の実装によって高速に計算されます。二次剰余の判定を行う際には、総当たりで解を探すよりも遥かに効率的です。

注意点

GMP拡張が必要：この関数を使用するには、PHPサーバーにGMP拡張がインストールされている必要があります。
第2引数は素数である必要があります：素数でない場合、結果は不正確になる可能性があります。

<?php
// 注意：第2引数が素数でない場合
$result_warning = gmp_legendre(2, 9); // 9は素数ではないので結果は信頼できない
echo "警告！ルジャンドル記号(2/9) = $result_warning (9は素数ではないため、この結果は信頼できません)\n";

// 比較のために、素数の場合と同じ値での計算を示す
$result_correct = gmp_legendre(2, 11); // 11は素数なので結果は正確
echo "ルジャンドル記号(2/11) = $result_correct (11は素数なので結果は信頼できます)\n";
?>