多倍長整数演算ライブラリ (GNU MP)
概要
GNUプロジェクトから多倍長精度演算ライブラリ(GNU Multiple Precision Arithmetic Library)が提供されています(http://gmplib.org/).以下,GNU MPと呼びます. GNU MPは,多倍長精度の符号付整数(signed integer)だけではなく,有理数(rational number),浮動小数点数(floating point number)も扱うことができそれらを対象とする算術関数を豊富に持っています.
なお,GMP から分岐したプロジェクトに MPIR (Multiple Precision Integers and Ratinals)(http://mpir.org/) があります.GMP と互換性があり,Windows環境もサポートされています.
GNU MPには以下の6種類の関数群があります.
- 符号付整数関数
符号付整数に対する関数の関数名は mpz_
で始まり,そのデータ型は mpz _t です.
- 有理数関数
有理数に対する関数の関数名は mpq_
で始まり,そのデータ型は mpq_t です.
- 浮動小数点関数
浮動小数点数に対する関数の関数名は mpf_
で始まり,そのデータ型は mpf_t です.
- Berkeley MP互換関数
itom
,madd
および mult
のようなBerkeley MP互換関数で,そのデータ型は MINT です.
- 低レベル関数
自然数に対する高速であるが低レベルの関数です.前記の関数グループの関数から呼ばれますが,直接呼ぶこともできます. 関数名は mpn_
で始まります.
- 雑関数
乱数生成関数などのユーティリティ関数があります.
ここでは,暗号で使われる多倍長整数に関連した関数について解説します.
GNU MPを使った典型的なプログラム例を示します.
#include <stdio.h>
/* ヘッダファイルgmp.hのインクルード */
#include "gmp.h"
int main(int argc, char **argv)
{
/* 符号付整数型の変数a,b,cの宣言 */
mpz_t a, b, c;
/* 変数a,cの初期化と,aの初期値の設定 */
mpz_init(a);
mpz_init(c);
mpz_set_str(a, argv[1], 10);
/* 変数bの初期化と値割り当て */
mpz_init_set_str(b ,"1234567890",10);
/* 変数aと変数bの積を変数cに設定 */
mpz_mul(c, a, b);
/* 変数cの内容をストリームに出力 */
mpz_out_str(stdout, 10, c);
/* 変数領域の解放 */
mpz_clear(a);
mpz_clear(b);
mpz_clear(c);
}
GNU MPでは,計算機の1語で表わされる多倍長整数の処理単位を limb と呼びます.多くの場合, limb は32または64ビットで構成されます.すなわち,多倍長整数はその大きさに応じた複数個のlimbで構成されます.C言語における limb のデータ型は mp_limb_t です.
一般的規則として,すべての関数は出力用の引数が入力用の引数より前にきます.また,入力引数と出力引数に同じ変数を指定できます.
以下,符号付整数演算関数の主な関数を機能別に分類して示します.関数のパラメータで rop は出力用パラメータ,op は入力用パラメータを表します.また,base は数値の基数を表します.
初期化と代入
- 初期化と解放
- void mpz_init (mpz_t x)
変数 x を初期化し,値を 0 にする.
- void mpz_clear (mpz_t x)
変数 x の使用していたメモリ領域を解放する.
- 代入
- void mpz_set (mpz_t rop, mpz_t op)
- void mpz_set_ui (mpz_t rop, unsigned long int op)
- void mpz_set_si (mpz_t rop, signed long int op)
- void mpz_set_d (mpz_t rop, double op)
rop に op の値を設定する.
- int mpz_set_str (mpz_t rop, char *str, int base)
rop に 文字列 str の値を基数を base として設定する.base は 2 ~ 62 である.先頭文字は,16進数の場合 0x または 0X,2進数の場合 0b または 0B,8進数の場合 0 から始まる.
- 初期化と代入
- void mpz_init_set (mpz_t rop, mpz_t op)
- void mpz_init_set_ui (mpz_t rop, unsigned long int op)
- void mpz_init_set_si (mpz_t rop, signed long int op)
- void mpz_init_set_d (mpz_t rop, double op)
変数 rop を初期化し, op の値を設定する.既に初期化されている変数に用いてはいけない.
- int mpz_init_set_str (mpz_t rop, char *str, int base)
変数 rop を初期化し,文字列 str の値を基数を base として設定する.
変換処理
- 形式変換
- unsigned long int mpz_get_ui (mpz_t op)
unsigned long として op の値を返す.
- signed long int mpz_get_si (mpz_t op)
signed long として op の値を返す.
- double mpz_get_d (mpz_t op)
double として op の値を返す.
- char * mpz_get_str (char *str, int base, mpz_t op)
op を基数 base の数字列(文字列) に変換する.str が NULL ならば,必要なメモリ領域が確保される.結果の文字列へのポインタが返る.
- 入出力処理
標準入出力ストリームからの入力を処理し,標準入出力ストリームへ出力する関数です.
stream 引数にNULLを指定することは,stdio からの読み込み,または stdout への書き込みを意味します.
- size_t mpz_out_str (FILE *stream, int base, mpz_t op)
op を基数 base の数字列(文字列)として stream に出力する.
- size_t mpz_inp_str (mpz_t rop, FILE *stream, int base)
基数 base の数字列(文字列)を stream から読み込み,rop に設定する.
- size_t mpz_out_raw (FILE *stream, mpz_t op)
op をバイナリ形式で stream に出力する.書き込まれたバイト数が返る.
- size_t mpz_inp_raw (mpz_t rop, FILE *stream)
mpz_out_raw で書かれたデータを stream から読み込み,rop に設定する.読み込まれたバイト数が返る.
算術演算
- 加減算
- void mpz_add (mpz_t rop, mpz_t op1, mpz_t op2)
- void mpz_add_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
rop = op1 + op2.
- void mpz_sub (mpz_t rop, mpz_t op1, mpz_t op2)
- void mpz_sub_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
rop = op1 - op2.
- void mpz_neg (mpz_t rop, mpz_t op)
rop = - op.
- void mpz_abs (mpz_t rop, mpz_t op)
rop = |op|.
- void mpz_fac_ui (mpz_t rop, unsigned long int op)
rop = op!.(階乗)
- 乗算
- void mpz_mul (mpz_t rop, mpz_t op1, mpz_t op2)
- void mpz_mul_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
rop = op1 x op2.
- void mpz_mul_2exp (mpz_t rop, mpz_t op1, unsigned long int op2)
rop = op1 x 2op2.
- べき乗演算
- void mpz_powm (mpz_t rop, mpz_t base, mpz_t exp, mpz_t mod)
- void mpz_powm_ui (mpz_t rop, mpz_t base, unsigned long int exp, mpz_t mod)
rop = baseexp mod mod.
- void mpz_pow_ui (mpz_t rop, mpz_t base, unsigned long int exp)
- void mpz_ui_pow_ui (mpz_t rop, unsigned long int base, unsigned long int exp)
rop = baseexp.
- 除算
除算関数は次の 3 つのグループに分けられます.
- 商を 0 に向かって切り捨てる関数で,関数名は
mpz_tdiv
で始まります.関数名の t
は trancate
を表わします.
- 商をマイナスの無限大に向かって丸める関数で,関数名は
mpz_fdiv
で始まります.関数名の f
は floor
を表わします.
- 商をプラスの無限大に向かって丸める関数で,関数名は
mpz_cdiv
で始まります.関数名の c
は ceil
を表わします.
また,関数名に q
が付くものは商を計算するもの,r
が付くものは剰余を計算するもの,qr
が付くものは商と剰余の両方を計算するものを表わします.
- void mpz_tdiv_q (mpz_t q, mpz_t n, mpz_t d)
- void mpz_tdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_tdiv_r (mpz_t r, mpz_t n, mpz_t d)
- void mpz_tdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
- void mpz_tdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
- void mpz_tdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
- void mpz_fdiv_q (mpz_t q, mpz_t n, mpz_t d)
- void mpz_fdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_fdiv_r (mpz_t r, mpz_t n, mpz_t d)
- unsigned long int mpz_fdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
- void mpz_fdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
- unsigned long int mpz_fdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
- unsigned long int mpz_fdiv_ui (mpz_t n, unsigned long int d)
- void mpz_cdiv_q (mpz_t q, mpz_t n, mpz_t d)
- void mpz_cdiv_q_ui (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_cdiv_r (mpz_t r, mpz_t n, mpz_t d)
- unsigned long int mpz_cdiv_r_ui (mpz_t r, mpz_t n, unsigned long int d)
- void mpz_cdiv_qr (mpz_t q, mpz_t r, mpz_t n, mpz_t d)
- unsigned long int mpz_cdiv_qr_ui (mpz_t q, mpz_t r, mpz_t n, unsigned long int d)
- unsigned long int mpz_cdiv_ui (mpz_t n, unsigned long int d)
- void mpz_tdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_tdiv_r_2exp (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_fdiv_q_2exp (mpz_t q, mpz_t n, unsigned long int d)
- void mpz_fdiv_r_2exp (mpz_t q, mpz_t n, unsigned long int d)
n を d で割り,商 を q に,余りを r に設定する.
- void mpz_mod (mpz_t r, mpz_t n, mpz_t d)
- unsigned long int mpz_mod_ui (mpz_t r, mpz_t n, unsigned long int d)
rop = r mod d.
- void mpz_divexact (mpz_t q, mpz_t n, mpz_t d)
q = n / d.
- 平方根演算
- void mpz_sqrt (mpz_t rop, mpz_t op)
op の平方根の整数部分を rop に設定する.
- void mpz_sqrtrem (mpz_t rop1, mpz_t rop2, mpz_t op)
op の平方根の整数部分を rop1 に設定し,rop2 に op - rop1*rop1 を設定する.
- int mpz_perfect_square_p (mpz_t op)
op が完全平方数 (op の平方根が整数) ならば非ゼロを返す.
- 数論関数
- int mpz_probab_prime_p (mpz_t op, int REPS)
n が素数か否かを判定する.n が確定的素数の場合 2,確率的素数の場合 1,合成数の場合 0 が返る.REPS は,素数の判定法である Miller-Rabin法のパラメータである (5~25 程度以上の値:大きい程誤判定の確率が小さい).
- void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2)
rop = GCD(op1, op2).
- unsigned long int mpz_gcd_ui (mpz_t rop, mpz_t op1, unsigned long int op2)
rop = GCD(op1, op2).
結果が unsigned long の範囲の値の場合,戻り値として最大公約数が返る.そうでない場合 0 が返る.
- void mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, mpz_t a, mpz_t b)
g = GCD(a, b) および a*s + b*t = g なる s,t を求める (拡張ユークリッド互助法).
- int mpz_invert (mpz_t rop, mpz_t op1, mpz_t op2)
op1 の法 op2 での逆元を求め,rop に設定する.逆元が存在する場合戻り値は非ゼロ,存在しない場合 0 である.
- int mpz_jacobi (mpz_t a, mpz_t p)
Jacobi 記号 (a / p) を計算する.
- int mpz_legendre (mpz_t a, mpz_t p)
Legendre 記号 (a / p) を計算する.
- 比較
- int mpz_cmp (mpz_t op1, mpz_t op2)
- int mpz_cmp_ui (mp_t op1, unsigned long int op2)
- int mpz_cmp_si (mpz_t op1, signed long int op2)
op1 と op2 を比較する. op1 > op2 のとき 正の値,op1 = op2 のとき 0,op1 < op2 のとき 負の値が返る.
- int mpz_sgn (mpz_t op)
op > 0 のとき +1, op = 0 のとき 0,op < 0 のとき -1 が返る.
- 論理演算とビット処理
- void mpz_and (mpz_t rop, mpz_t op1, mpz_t op2)
op1 と op2 のビット毎の AND を rop に設定する.
- void mpz_ior (mpz_t rop, mpz_t op1, mpz_t op2)
op1 と op2 のビット毎の OR を rop に設定する.
- void mpz_xor (mpz_t rop, mpz_t op1, mpz_t op2)
op1 と op2 のビット毎の XOR(排他的論理和) を rop に設定する.
- void mpz_com (mpz_t rop, mpz_t op)
op の 1 の補数を rop に設定する.
- unsigned long int mpz_popcount (mpz_t op)
op の 2進表現における 1 の数を返す.
- unsigned long int mpz_hamdist (mpz_t op1, mpz_t op2)
op1 と op2 のハミング距離を返す.
- unsigned long int mp_scan0 (mpz_t op, unsigned long int start_bit)
- unsigned long int mpz_scan1 (mpz_t op, unsigned long int start_bit)
ビット位置 start_bit から op を上位ビットの方にスキャンし,最初の 0 (scan0) または 1 (scan1) が見つかるビット位置を返す.
- void mpz_setbit (mpz_t rop, unsigned long int bit_index)
rop のビット位置 bit_index にビットをセットする.
- void mpz_clrbit (mpz_t rop, unsigned long int bit_index)
rop のビット位置 bit_index のビットをクリアする.
その他
- サイズ
- size_t mpz_size (mpz_t op)
limbs の数で測った op の大きさを返す.op が 0 ならば,0 が返る.
- size_t mpz_sizeinbase (mpz_t op, int base)
基数 base での op の数字の数を返す.基数 base は,2 ~ 62 である.
- 乱数
- void mpz_urandomm (mpz_t rop, gmp_randstate_t state, mpz_t n)
0 から n - 1 の範囲の一様乱数を生成する.
- void mpz_urandomb (mpz_t rop, gmp_randstate_t state, mp_bitcnt_t n)
0 から 2n-1 の範囲の一様乱数を生成する.
- void gmp_randinit_default (gmp_randstate_t state)
デフォルトアルゴリズムで state を初期化する.
- void gmp_randseed (gmp_randstate_t state, mpz_t seed)
- void gmp_randseed_ui (gmp_randstate_t state, unsigned long int seed)
state に初期乱数種を seed を設定する.