5.9 数論関数

Function: int mpz_probab_prime_p (const mpz_t n, int reps)

nが素数かどうかを決定します。返り値が2の場合はnは確実に素数，1の場合はnは確率的に素数（確定的ではない），0の時は確実に非素数であることを意味します。

この関数は複数の除算を伴う，Miller-Rabin確率的素数テストを行います。高次のreps値を 使うことで，非素数（合成数）を「確率的素数」と認識してしまう率を下げることができ，その誤認識率は 4^(-reps)以下です。適当なrepsは大体15～50です。

Function: void mpz_nextprime (mpz_t rop, const mpz_t op)

opより次に大きい素数をropに格納します。

この関数は素数判定に確率的アルゴリズムを使用します。実用的には十分で，合成数を選んでしまう可能性は非常に小さいと思われます。

Function: void mpz_gcd (mpz_t rop, const mpz_t op1, const mpz_t op2)

op1 と op2のGCD（Greatest Common Divisor, 最大公約数)を求めてropに格納します。入力値に負の値が入っていても，結果は常に正数になります。どちらもゼロであれば，gcd(0,0) = 0となります。

Function: unsigned long int mpz_gcd_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

op1 と op2のGCDを計算します。ropがNULLでなければ，結果はここに格納されます。

GCDがunsigned long intの範囲に収まるものであれば，これが返り値になります。収まらないようであれば0が返り値となり，結果は op1に格納されます。 op2がゼロでなければ，この計算結果は常にunsigned long intに収まる筈です。

Function: void mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, const mpz_t a, const mpz_t b)

aとbの最大公約数を求めてgに格納し，更にa*s + b*t = gを満足する係数sとtを求めて格納します。 gは常に正数で，aとbが負数であっても関係ありません（両方ゼロならばゼロになります)。sと tの値は通常， abs(s) < abs(b) / (2 g) かつ abs(t) < abs(a) / (2 g)を満足するように定まり，結果としてsとtは一意になります。但し，下記の例外があります。

abs(a) = abs(b)の時は，s = 0，t = sgn(b)となります。

それ以外では， b = 0 もしくはabs(b) = 2 gの時は s = sgn(a) ，a = 0 もしくは abs(a) = 2 gの時はt = sgn(b)となります。 g = abs(b)，即ち，b が aを割り切ったり，a = b = 0となる時には，必ず s = 0となります。

tがNULLの時はtの計算を行いません。

Function: void mpz_lcm (mpz_t rop, const mpz_t op1, const mpz_t op2)

Function: void mpz_lcm_ui (mpz_t rop, const mpz_t op1, unsigned long op2)

op1 とop2のLCM(Least Common Multiple，最小公倍数)を計算し，ropに格納します。op1とop2の符号とは無関係に，ropは常に正の値になります。op1かop2のどちらかがゼロの場合は，ropもゼロになります。

Function: int mpz_invert (mpz_t rop, const mpz_t op1, const mpz_t op2)

op1のモジュロop2演算の逆数を求め，ropに格納します。逆数が存在していれば非ゼロを返し， ropは0 <= rop < abs(op2) (abs(op2) = 1の時はrop = 0となる，つまりゼロ環に退化）を満たすように決まります。 逆数が存在していない時にはゼロを返し，ropは不定になります。op2がゼロの時のことはこの関数では考慮していません。

Function: int mpz_jacobi (const mpz_t a, const mpz_t b)

Jacobi記号(a/b)の計算を行います。これはbが奇数の時のみ定義された値です。

Function: int mpz_legendre (const mpz_t a, const mpz_t p)

Legendre記号 (a/p)の計算を行います。 pが正の素数である時のみ定義されており，Jacobi記号と同じ値になります。

Function: int mpz_kronecker (const mpz_t a, const mpz_t b)

Function: int mpz_kronecker_si (const mpz_t a, long b)

Function: int mpz_kronecker_ui (const mpz_t a, unsigned long b)

Function: int mpz_si_kronecker (long a, const mpz_t b)

Function: int mpz_ui_kronecker (unsigned long a, const mpz_t b)

Kronecker拡大付きのJacobi記号(a/b)の計算を行います。aが奇数の時は(a/2)=(2/a)，偶数の時は(a/2)=0になります。

bが奇数の時は，Jacobi記号とKronecker記号は同じものになります。mpz_kronecker_ui以下の関数はJacobi記号の混合精度計算に利用できます。

詳細についてはHenri Cohenのテキストの1.4.2節(see References)か，数論のテキストをご覧ください。mpz_kronecker_ui関数を使ったサンプルプログラムdemos/qcn.cも参照して下さい。

Function: mp_bitcnt_t mpz_remove (mpz_t rop, const mpz_t op, const mpz_t f)

opから因数fを全て抜き取り，その結果をropに格納します。返り値は，取り除かれた回数です。

Function: void mpz_fac_ui (mpz_t rop, unsigned long int n)

Function: void mpz_2fac_ui (mpz_t rop, unsigned long int n)

Function: void mpz_mfac_uiui (mpz_t rop, unsigned long int n, unsigned long int m)

nの階数を求め，ropに格納します。mpz_fac_ui関数は階数n!を， mpz_2fac_ui関数は2重階数n!!を，mpz_mfac_uiuiは m重階数n!^(m)を計算します。

Function: void mpz_primorial_ui (mpz_t rop, unsigned long int n)

nの素数階乗，即ちn以下の全ての正の素数の積を求め，ropに格納します。

Function: void mpz_bin_ui (mpz_t rop, const mpz_t n, unsigned long int k)

Function: void mpz_bin_uiui (mpz_t rop, unsigned long int n, unsigned long int k)

2項係数n over kを求め，ropに格納します。nが負数の時は bin(-n,k) = (-1)^k * bin(n+k-1,k)を計算します。Knuth本のvolume 1，1.2.6節のpart Gを参照して下さい。

Function: void mpz_fib_ui (mpz_t fn, unsigned long int n)

Function: void mpz_fib2_ui (mpz_t fn, mpz_t fnsub1, unsigned long int n)

mpz_fib_ui関数はfnにF[n]，即ち，n項目のFibonacci数を計算して格納します。 mpz_fib2_ui関数はfnにF[n]を，fnsub1に F[n-1]を計算して格納します。

これらの関数は，単独のFibonacci数列の値を計算するためのものです。数列全体を欲しい時には，mpz_fib2_ui関数から出発し，それ以降はF[n+1]=F[n]+F[n-1]を繰り返し実行すると高速に数列全体が得られます。

Function: void mpz_lucnum_ui (mpz_t ln, unsigned long int n)

Function: void mpz_lucnum2_ui (mpz_t ln, mpz_t lnsub1, unsigned long int n)

mpz_lucnum_ui関数はlnにL[n]，即ち，Lucas数のn番目の値を求めて格納します。mpz_lucnum2_ui関数はlnにL[n]を，lnsub1に L[n-1]を求めて格納します。

これらの関数は単独のLucus数を計算するためのものです。数列全体を欲しい時には，mpz_lucnum2_ui関数から出発し，それ以降はL[n+1]=L[n]+L[n-1]を繰り返し実行すると高速に数列全体が得られます。

Fibonacci数やLucas数は漸化式で定義されていますので，mpz_fib2_ui関数とmpz_lucnum2_ui関数を一度に呼び出す必要はありません。Fibonacci数からLucas数への変換を行う方法はLucas Numbers Algorithmに書いておきました。その逆の変換は自明です。