PHPのgmp_powm()関数とは？冪乗の剰余を高速に計算する方法

PHPのGMP拡張モジュールには、大きな整数を扱うためのさまざまな数学関数が用意されています。その中でもgmp_powm()は、「べき乗の剰余」を効率的に計算できる便利な関数です。この記事では、gmp_powm()関数の基本的な使い方から、パラメータの意味、実際のコード例までわかりやすく解説します。

gmp_powm()関数とは

gmp_powm()関数は、指定した基数（base）を指数（pow）で累乗した結果を、法（mod）で割った余りをGMP数値として返します。

つまり、次のような計算を行います。

(base ^ pow) mod mod

巨大な数をそのまま累乗すると桁が爆発的に増えてしまいますが、gmp_powm()は中間結果を圧縮しながら計算するため、非常に大きな数でも高速かつ省メモリで処理できます。この性質により、RSA暗号などの公開鍵暗号処理や、モジュロ演算を多用するアルゴリズムの実装によく使われています。

構文

gmp_powm($base, $pow, $mod)

パラメータ

• $base: 累乗の対象となる基数。GMPリソースオブジェクト、数値、または数値文字列を指定します。

• $pow: 基数に対して掛け合わせる指数。負の値を指定した場合は、modの逆元が存在するときのみ計算可能です。

• $mod: 法（モジュラス）。累乗した結果をこの値で割った余りが求められます。

戻り値

base を pow 乗した結果を mod で割った余りに相当する GMP数値 を返します。

使用例

以下は、3の2乗を5で割った余りを求めるサンプルコードです。

<?php
   $base = "3";
   $pow = "2";
   $mod = "5";

   $powm = gmp_powm($base, $pow, $mod);

   echo gmp_strval($powm);
?>

このコードでは、まず基数「3」、指数「2」、法「5」をそれぞれ変数に代入し、gmp_powm()関数で「3 の 2 乗 ÷ 5 の余り」を計算しています。結果を出力する際は、gmp_strval()を使ってGMP数値を文字列に変換している点に注意してください。

出力結果

上記コードの実行結果は次のとおりです。

4

これは、3の2乗＝9、9÷5＝1余り4 という計算結果と一致しています。

まとめ

gmp_powm()関数を使えば、PHPでも巨大な整数の冪乗剰余を簡単かつ高速に計算できます。通常の累乗演算では扱いきれないような大きな数値が必要になる暗号処理などの場面で、ぜひ活用してみてください。