Math::Prime::Util::GMP
素数生成、判定など
use Math::Prime::Util::GMP ':all';
パッケージをロードして下記の関数をエクスポートする。
Math::Prime::Util, Math::Prime::Util::GMP のどちらを使っても速度が変わらない？？manページ上は
::GMPが推奨されている。
入力オブジェクトは int または Math::BigInt。use bigint を併用すると
bigint も使える。
出力オブジェクトは常に int、または、bigint、以前のバージョンでは64bit以上の整数は
Math::BigIntを返して来たが仕様変更された。
is_prob_prime($n);
ミラー・ラビンテスト、または、Baillie-PSW (BPSW) テストを用いて $n が素数か判定する。
戻り値： 0=合成数、1=恐らく素数、2=素数
miller_rabin_random($n , $k);
$k 回繰り返しを実行するミラー・ラビンテストを用いて $n
が素数蚊判定する。
my $rnd = random_nbit_prime($n);
一様分布する$nビット長の素数を生成する。
少なくとも、2048ビットまでは Math::BigIntオブジェクトではなく、ネイティブの bigintが返ってくる。
$nビット長未満の素数が生成される事はない。
my $rnd = random_strong_prime($n);
一様分布する$nビット長の強い素数pを生成する。
●p
のビット長は128以上（$n < 128はエラー）
●p-1 は大きな素因数rを持つ
●p+1 は大きな素因数sを持つ
●r-1 は大きな素因数tを持つ
生成する素数が、ネイティブ整数のビット数(32 または
64）以下の場合、ネイティブ整数を返し、それより大きい場合、Math::BigIntオブジェクトを返す。
$nビット長未満の素数が生成される事はない。
my $bcd = gcd(@n);
リスト @n の 最大公約数を求める。
my $lcd = lcd(@n);
リスト @n の最小公倍数を求める。
my $x = chinese(@crt);
中国人剰余定理(CRT)を用いて、連立合同方程式の解を求める。
@crt = ([a0,n0],[a1,n1], [a2,n2], …) を入力し、 ai ≡ x mod ni
を満たす x を返す。
my $hw = hammingweight($n);
$n のハミング重みを求める。
my $k = znorder($a, $p);
$p を法とした $n の乗法位数(multiplicative order)を求める。
乗法位数：互いに素な正の整数 p と a で、 a^k ≡ 1 (mod p) が成り立つ最小の k
ORDp(a) (mod p)
と表記する。
my $r = znprimroot($p);
$n を法とした最小原始根(primitive root)を求める。
原始根：ψ(p) を p のオイラー数（p が素数なら p-1）とした時、ORDp(r) (mod p) = ψ(p) となる整数 r
（つまり、乗法位数が p-1 である値 r）。通常、多数の原始根が存在し、この関数は最小の原始根を求める。
my $k = znlog($a, $g, $p);
$p を法、$g を底とした $a の離散対数を求める。
a = g^k
mod p を満たす k であり、離散対数問題を解くのと等価。
my $n_1 =
invmod($n, $p);
$p を法とした $n のモジュラー逆数を求める。
my $sq = sqrtmod($n, $p);
$p を法とした $n のモジュラー平方根を求める。
my $x = addmod($a, $b, $p);
$p を法とした加算剰余 (a + b) mod p を求める。
my $x = mulmod($a, $b, $p);
$p を法とした乗算剰余
(a * b) mod p を求める。
my $x = powmod($a, $b, $p);
$p を法としたべき乗剰余 (a^b) mod p を求める。
my $x = divmod($a, $b, $p);
$p を法とした除算剰余 (a / b) mod p を求める。
my $ep = euler_phi($n);
$n のオイラー数を求める。オイラー関数 ψ(n) である。
正の整数 n に対して、1 から n までの自然数で n と互いに素なものの個数
my @fac = factor($n);
$n を因数分解する。素数に分解されるまで繰り返せば、素因数分解も可能。
諸々の手法を組み合わせて因数分解している。