Next: , Previous: , Up: Top   [Index]


8 基盤関数

本章では,GMPの上位関数群を下支えする基盤関数群を解説します。少しでも計算時間を短縮したい時にも有用なものです。

基盤関数はmpn_から始まる名前になります。

mpn関数は,高速化に特化して作られており,首尾一貫したインターフェースを提供するものではありません。同じような機能を持つ関数が複数提供されているのは,使い回すのが難しいケースに対応しているからです。実際の多倍長計算に有用なものとして機能しており,万人に使いこなせる代物ではありません。

計算元となる引数は,最小有効リムへのポインタと,リムの総数を指定しています。計算結果を格納する先は,ポインタだけで指定します。つまり,基盤関数の使用者が,計算結果の格納先に十分なメモリ領域を確保していることを保証しなければなりません。

このように計算元と計算結果の格納先を規定することで,引数リム数の範囲内(subrange)で計算を実行することができ,計算結果もリム数の範囲内に格納することができるようになります。

全ての基盤関数は,少なくとも計算元には最低1リムの領域が確保されていることだけを要求しています。サイズゼロの場合はゼロと見なします。特に明記されていない限り,同位置(in-place)演算,即ち,計算元と結果の格納先が同じであっても処理が可能になります。但し,一部だけ重なっているようなケースはダメです。

mpn関数はmpz_, mpf_, mpq_関数の実装の基盤となっています。

下記の例は,s1pから始まる自然数と,s2pから始まる自然数の和と求め,destpに格納しています。全ての自然数格納エリアはnリム確保されています。

cy = mpn_add_n (destp, s1p, s2p, n)

mpn関数は,それぞれの引数のどこのリムがゼロであるか,特殊な形態になっているかということは全く感知しません。ランダムなデータに対して,いちいちチェックなぞしていたら時間の無駄です。アプリケーション側でデータの情報が欲しければ,計算途中に確認のためのステップを設ければ済む話です。


以下に述べる基盤関数の解説のうち,計算元の引数は最小有効リムへのポインタとリムの数,例えば {s1p, s1n}というセットで与えます。

Function: mp_limb_t mpn_add_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n}と{s2p, n}を和を求め,和の小さい方のnリム分をrpに書き込みます。桁上がりがあれば返り値は1,なければ0になります。

この関数は加算の土台になっており,大方のCPUに対してアセンブラ言語で記述されていることから,加算を実行する時にはこの関数を使うことをお勧めします。変数そのものに足し込みたい時 (即ちs1ps2pが同じものである時)には,mpn_lshift関数で1bitシフトするだけで済むのでこちらの方が高速に実行できます。

Function: mp_limb_t mpn_add_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)

{s1p, n} とs2limbの和を求め,最小リムの方からnリム分をrpに書き込みます。桁上がりがあれば返り値は1,なければ0になります。

Function: mp_limb_t mpn_add (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t s1n, const mp_limb_t *s2p, mp_size_t s2n)

{s1p, s1n}と{s2p, s2n}の和を求め,s1n個分の最小有効リムをrpに書き込みます。桁上がりがあれば返り値は1,なければ0になります。

演算を実行するには,s1ns2n以上である必要があります。

Function: mp_limb_t mpn_sub_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n}から{s2p, n} を引き,その結果を最小有効リムの方からn個分rpに書き込みます。桁の借り上げがあれば1を,なければ0を返します。

この関数は減算の土台になります。大方のCPU用にアセンブラで記述されていますので,減算を実装する時にはこの関数を使って下さい。

Function: mp_limb_t mpn_sub_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)

{s1p, n}からs2limbを引き,最小有効リムのn個分を rpに書き込みます。桁の借り上げがあれば1を,なければ0を返します。

Function: mp_limb_t mpn_sub (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t s1n, const mp_limb_t *s2p, mp_size_t s2n)

{s1p, s1n}から{s2p, s2n}を引き,その結果を最小有効リムのs1n個分をrpに書き込みます。桁の借り上げがあれば1を,なければ0を返します。

この演算を実行するためには, s1ns1n以上でなければなりません。

Function: mp_limb_t mpn_neg (mp_limb_t *rp, const mp_limb_t *sp, mp_size_t n)

{sp, n}にマイナスをつけて {rp, n}に書き戻します。この関数は,mpn_sub_n関数を用いて, nリム分のゼロから {sp, n}を差し引く演算と同じ結果になります。桁の借り上げがあれば1を,なければ0を返します。

Function: void mpn_mul_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}の積を求め,2*nリム長の積をrpに書き込みます。

積を格納する領域には,積の有効リムの多数がゼロであっても,2*nリム分のメモリ領域が不可欠です。この3つの引数のメモリ領域は互いに重複してはいけません。

乗じる2数が同じものである場合は,mpn_sqr関数を使って下さい。

Function: mp_limb_t mpn_mul (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t s1n, const mp_limb_t *s2p, mp_size_t s2n)

{s1p, s1n} と {s2p, s2n}の積を求め,(s1n+s2n)長の積をrpに書き込みます。返り値は積の最大有効リムになります。

積を格納する領域は,積の有効桁数リムの多数がゼロであっても,s1n + s2nリム分のメモリ領域が不可欠です。この3つのメモリ領域は互いに重複してはいけません。

この演算を実行する際には,s1ns2n以上でなければなりません。

Function: void mpn_sqr (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n)

{s1p, n}の2乗を求め, 2*nリム長の結果をrpに書き込みます。

2乗を書き込むメモリ領域には,2乗の有効リムの多数がゼロであっても,2nリム分必要になります。計算元と格納先のメモリ領域は互いに重複してはいけません。

Function: mp_limb_t mpn_mul_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)

{s1p, n} と s2limbの積を求め,積の最小nリム分をrpに書き込みます。返り値は積の最大有効リムです。 {s1p, n} と {rp, n}のメモリ領域は,rp <= s1pであれば重なりがあっても構いません。

この基盤関数は,GMP における他の演算同様,一般的な乗算の土台になります。大部分のコードは大方のCPU向けにアセンブラで記述されています。

s2limbが2のべき乗の場合は,この関数を使わず, s2limbのlogと等しいシフト値を与えてmpn_lshiftを使うとより高速な処理が可能になります。

Function: mp_limb_t mpn_addmul_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)

{s1p, n} と s2limbの積を求め,その積の最小nリム分を{rp, n}に加え,結果をrpに書き戻します。返り値は,積の最大有効リムに加算における桁上がり分が加えられたものです。 {s1p, n}と{rp, n}は,rp <= s1pであれば,同じメモリ位置でも問題ありません。

この基盤関数は,GMP の他の演算同様,乗算を構築するための土台になります。大部分のCPU向けにアセンブラルーチンが提供されています。

Function: mp_limb_t mpn_submul_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n, mp_limb_t s2limb)

{s1p, n} と s2limbの積を求め,その積の最小nリム分を{rp, n}から引き,結果をrpに書き戻します。返り値は,積の最大有効リムに減算における桁借り上げ分が加えられたものです。 {s1p, n}と{rp, n}は,rp <= s1pであれば,同じメモリ位置でも問題ありません。

この基盤関数は,GMP の他の演算同様,乗算と除算を構築するための土台になります。大部分のCPU向けにアセンブラルーチンが提供されています。

Function: void mpn_tdiv_qr (mp_limb_t *qp, mp_limb_t *rp, mp_size_t qxn, const mp_limb_t *np, mp_size_t nn, const mp_limb_t *dp, mp_size_t dn)

{np, nn}を{dp, dn}で割り,商を{qp, nn-dn+1}に,剰余を{rp,dn}に格納します。商は切り捨て(0への丸め)られます。

nprpを除き,他の引数のメモリ領域が重なっていてはいけません。割られる数のリム数nnは,割る数のリム数 dn以上でなければなりません。割る数の最小有効リ)ムは非ゼロでなくてはなりません。qxnはゼロでなければなりません(訳注:不要な引数?)。

Function: mp_limb_t mpn_divrem (mp_limb_t *r1p, mp_size_t qxn, mp_limb_t *rs2p, mp_size_t rs2n, const mp_limb_t *s3p, mp_size_t s3n)

[この関数は廃止予定です。もっと効率の良いmpn_tdiv_qr関数を使って下さい。]

{rs2p, rs2n} を {s3p, s3n}で割り,商をr1pに書き込みますが,最大有効リムは別に扱われ,この関数の返り値になります。剰余はrs2pに上書きされ,s3nリムの長さとなります(即ち,割る数(divisor)と同じリム長となる)。

整数の商に加えてqxn長の小数部のリムが格納されます。大概はqxnはゼロになります。

rs2ns3n以下でなければなりません。また,割る数の最大有効ビットは1でなければなりません。

商が不要であれば,r1pとして rs2p + s3nを渡して下さい。特別な場合を除き,引数のメモリ空間の重複があってはいけません。

返り値は商の最大有効リムになりますので,0か1です。

r1pのエリアは rs2n - s3n + qxnリム長必要です。

Function: mp_limb_t mpn_divrem_1 (mp_limb_t *r1p, mp_size_t qxn, mp_limb_t *s2p, mp_size_t s2n, mp_limb_t s3limb)
マクロ: mp_limb_t mpn_divmod_1 (mp_limb_t *r1p, mp_limb_t *s2p, mp_size_t s2n, mp_limb_t s3limb)

{s2p, s2n} を s3limbで割り,商をr1pに格納し,剰余を返します。

整数の商は{r1p+qxn, s2n}に書き込まれ,小数部qxnが計算されて, {r1p, qxn}に書き込まれます。s2nqxnはゼロでも構いません。大概のケースでは qxnはゼロになります。

mpn_divmod_1が互換性のために残されていますが,これは qxnをゼロと設定した mpn_divrem_1関数のマクロです。

r1ps2pのメモリ領域は,同一か,完ぺきに分離している必要があります。

Function: mp_limb_t mpn_divmod (mp_limb_t *r1p, mp_limb_t *rs2p, mp_size_t rs2n, const mp_limb_t *s3p, mp_size_t s3n)

[この関数は廃止予定です。もっと効率の良いmpn_tdiv_qr関数を使って下さい。]

Function: void mpn_divexact_1 (mp_limb_t * rp, const mp_limb_t * sp, mp_size_t n, mp_limb_t d)

{sp, n}はdで割り切れるという前提の元で除算を実行し,その商を {rp, n}に格納します。dでは割り切れない場合は,{rp, n}に格納される 値は不定です。rpspのメモリ領域は完全に別のところに確保し,重なりがないようにして下さい。

マクロ: mp_limb_t mpn_divexact_by3 (mp_limb_t *rp, mp_limb_t *sp, mp_size_t n)
Function: mp_limb_t mpn_divexact_by3c (mp_limb_t *rp, mp_limb_t *sp, mp_size_t n, mp_limb_t carry)

{sp, n}を3で割り,正確に割り切れれば,その結果を{rp, n}に書き込みます。この場合は返り値はゼロになります。3で割り切れなければ,返り値は非ゼロで,結果は不正確なものになります。

mpn_divexact_by3c関数は初期桁上がり・桁下がりパラメータを持ち,これは前回呼び出し時の返り値を代入できます。それによって,低次桁から高次桁へ,一桁ずつ大きな数の計算ができるようになります。mpn_divexact_by3関数は,mpn_divexact_by3c 関数に桁上がりパラメータをゼロとしたときのマクロ実装です。

これらのルーチン群は逆数との乗算を行っており,高速な乗算と遅い除算を組み合わせているmpn_divrem_1より高速です。

入力値a, 計算結果q, サイズn, 初期桁上がりi,返り値cc*b^n + a-i = 3*qという関係式を満足します。ここでb=2^GMP_NUMB_BITSです。返り値cは0, 1, 2のどれかで,初期桁上がりiも0, 1, 2のどれかになります (後者二つは桁上がりの意)。c=0であれば,明らかにq=(a-i)/3です。c!=0であれば,剰余 (a-i) mod 3は, b ≡ 1 mod 3 なので(mp_bits_per_limbが偶数の場合。現行バージョンでは常に偶数),3-cとなります。

Function: mp_limb_t mpn_mod_1 (const mp_limb_t *s1p, mp_size_t s1n, mp_limb_t s2limb)

{s1p, s1n} を s2limbで割り,剰余を返します。 s1nはゼロでも構いません。

Function: mp_limb_t mpn_lshift (mp_limb_t *rp, const mp_limb_t *sp, mp_size_t n, unsigned int count)

{sp, n}を左方向に count ビット分シフトし,その結果を{rp, n}に書き込みます。左シフトの結果,はみ出た部分,即ち,最小 countビット分が返り値になります(返り値の残りの部分はゼロとなります)。

countは1以上, mp_bits_per_limb-1以下でなければなりません。 {sp, n},{rp, n}のメモリ領域は重なりがあっても,rp >= spであれば問題ありません。

この関数は大方のCPUに対応したアセンブラで記述されています。

Function: mp_limb_t mpn_rshift (mp_limb_t *rp, const mp_limb_t *sp, mp_size_t n, unsigned int count)

{sp, n}を右方向にcountビットシフトし,結果を {rp, n}に書き込みます。右側シフトの結果はみ出た最大countビット分が返り値となります(それ以外の部分はゼロです)。

countは1以上mp_bits_per_limb-1以下でなければなりません。{sp, n} と {rp, n}のメモリ領域は,rp <= spであれば,重なり部分があっても構いません

この関数は大方のCPU向けにアセンブラコードが提供されています。

Function: int mpn_cmp (const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}を比較し,s1 > s2であれば正数を,等しければゼロを,s1 < s2であれば負数を返します。

Function: int mpn_zero_p (const mp_limb_t *sp, mp_size_t n)

{sp, n}を調べ,ゼロの時は1を,それ以外の時は0を返します。

Function: mp_size_t mpn_gcd (mp_limb_t *rp, mp_limb_t *xp, mp_size_t xn, mp_limb_t *yp, mp_size_t yn)

{xp, xn} と{yp, yn}の最大公約数(Greatest Common Divisor, GCD)を求め,{rp, retval}に格納します。GCDは最大 ynリムになりますので,返り値は実際のGCDのリム長となります。2数については上書きされて元の値ではないものになります。

この関数はxn >= yn > 0,かつ,{yp, yn}の最大有効リムが非ゼロでなければ実行できません。{xp, xn} と {yp, yn}のメモリ領域が互いに重なりあってもいけません。

Function: mp_limb_t mpn_gcd_1 (const mp_limb_t *xp, mp_size_t xn, mp_limb_t ylimb)

{xp, xn} と ylimbの最大公約数を返します。2数は非ゼロでなければなりません。

Function: mp_size_t mpn_gcdext (mp_limb_t *gp, mp_limb_t *sp, mp_size_t *sn, mp_limb_t *up, mp_size_t un, mp_limb_t *vp, mp_size_t vn)

Uは{up, un},Vは{vp, vn}であるとします。

この関数はUVのGCDであるGを計算すると共に,G = US + VTを満足するcofactorであるSも求めます。2番目のcofactorであるTは計算されませんが,(G - U*S) / Vが成立するので簡単に求めることができます (割算は正確に行えます)。un >= vn > 0かつ,{vp, vn}の最大有効リムは非ゼロである必要があります。

SS = 1 か,abs(S) < V / (2 G)を満足します。 VUを割り切る時(即ち,G = Vの時)に限り, S = 0となります。

Ggpに格納され,そのリム長は返り値になります。 Sspに格納され,|*sn| がそのリム長になります。Sが負数の時は,*snが負数になります。gpのメモリ空間はvnリム長,spのリム長は vn+1必要になります。

入力引数は破壊されます。

互換性に関する注意:GMP 4.3.0と4.3.1ではSが若干異なっています。これ以前のGMPでは以降のGMP同様,Sは上述のように記述されています。GMP 4.3.0以前では更に余分のメモリスペースが入出力に際して必要でした。正確に言うと,{up, un+1} と {vp, vn+1}のエリアが破壊されます(即ち,余分の1リムが必要であったということ)。gpspが指し示すメモリエリアはun+1リム分必要であったことになります。

Function: mp_size_t mpn_sqrtrem (mp_limb_t *r1p, mp_limb_t *r2p, const mp_limb_t *sp, mp_size_t n)

{sp, n}の平方根を計算し,結果を{r1p, ceil(n/2)}に格納し,余りを{r2p, retval}に格納します。 r2pnリム分必要になります。何リム生成したのかは返り値で分かります。

{sp, n}の最大有効リムは非ゼロでなければなりません。{r1p, ceil(n/2)} と {sp, n} のメモリ空間は完全に分離されていなければなりません。{r2p, n} と {sp, n}は同一のエリアか,完全分離されたものかのどちらかでなければなりません。

剰余が不要であればr2pNULLに設定して下さい。この場合,剰余がゼロか非ゼロかによって返り値もそれにならいます。

返り値がゼロであれば,入力値は完全平方数です。mpn_perfect_square_p関数の解説も参照して下さい。

Function: size_t mpn_sizeinbase (const mp_limb_t *xp, mp_size_t n, int base)

基数baseである時の,{xp,n}の桁数を返します。baseは2以上62以下に設定できます。n > 0 かつxp[n-1] > 0でなければなりません。返り値は正確な桁数か,大きすぎる場合は1になります。baseが2のべき乗である時には,結果は常に正確なものになります。

Function: mp_size_t mpn_get_str (unsigned char *str, int base, mp_limb_t *s1p, mp_size_t s1n)

{s1p, s1n}をunsigned charの配列であるstrに,基数baseの文字列に変換して格納します。返り値は生成された文字列の長さです。文字列の先頭部分はゼロで埋められます。文字列はASCIIコードではないので,表示するためには‘0’ もしくは ‘A’を加えてASCIIコード化する必要があります。加えるべき値は基数によります。基数baseは2以上62以下で指定可能です。

入力引数{s1p, s1n}の最大有効リムは非ゼロである必要があります。 baseが2のべき乗であれば入力値{s1p, s1n}はそのままですが,それ以外の場合はぶち壊されます。

strのメモリ空間は s1n長のリム配列で表現でき,1字分の余分エリアを加えて,最大の数を格納できるだけの広さが必要です。

Function: mp_size_t mpn_set_str (mp_limb_t *rp, const unsigned char *str, size_t strsize, int base)

baseを基数とする{str,strsize}バイト列を,rpのリムに変換します。

str[0]は入力値の最大有効バイト, str[strsize-1]は最小有効バイトです。配列の各バイトは0以上base-1以下の整数値で,ASCIIコードは受け付けません。基数baseは2以上256以下です。

変換される値は,{rp,rn}となり,rnが返り値になります。最大有効バイト str[0]が非ゼロであれば,rp[rn-1]が非ゼロになるか,rp[rn-1]以下の複数リムがゼロになる可能性があります。

rpのメモリ空間は, 指定基数での最大桁数の数に余分の1リムを加えた分を格納できるstrsizeでなければなりません。

入力値は最小でも1バイトなければならず,{str,strsize} と結果を格納するrpのメモリ領域に重複があってはいけません。

Function: mp_bitcnt_t mpn_scan0 (const mp_limb_t *s1p, mp_bitcnt_t bit)

bitビット目からs1pを調べ,次の"0"ビットを見つけます。

この関数は,値を返すために,s1pの範囲内か,bit以降の位置に"0"ビットが見つかることを前提としています。

Function: mp_bitcnt_t mpn_scan1 (const mp_limb_t *s1p, mp_bitcnt_t bit)

bitビットからs1pを調べ,次の"1"を見つけます。

この関数は,s1pの範囲内か,bit以降のエリアに"1"が見つかることを前提としています。

Function: void mpn_random (mp_limb_t *r1p, mp_size_t r1n)
Function: void mpn_random2 (mp_limb_t *r1p, mp_size_t r1n)

r1nリムの長さの乱数を生成し, r1pに格納します。この乱数の最大有効リムは常に非ゼロになります。 mpn_random関数は一様分布リムデータを生成し,mpn_random2関数は,ランダムに0と1が並んだ長い2進表現列を生成します。

mpn_random2関数は,mpn関数の処理の正しさを確認するために作られました。

Function: mp_bitcnt_t mpn_popcount (const mp_limb_t *s1p, mp_size_t n)

{s1p, n}における"1"のビット数を数えます。

Function: mp_bitcnt_t mpn_hamdist (const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}のハミング距離を計算します。ハミング距離とは,2数の2進表現におけるビット単位の差異の数です。

Function: int mpn_perfect_square_p (const mp_limb_t *s1p, mp_size_t n)

{s1p, n} が完全平方数である時のみ,非ゼロを返します。入力引数{s1p, n}の最大有効リムは非ゼロでなければなりません。

Function: void mpn_and_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p,n}のビット単位の論理積を求め,その結果を{rp, n}に書き込みます。

Function: void mpn_ior_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}のビット単位の論理和を求め,その結果を{rp, n}に書き込みます。

Function: void mpn_xor_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}のビット単位の排他的論理和を求め,その結果を{rp, n}に書き込みます。

Function: void mpn_andn_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と{s2p, n}の補数のビット単位の論理積を求め,その結果を{rp, n}に書き込みます。

Function: void mpn_iorn_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}の補数のビット単位の論理和を求め,その結果を {rp, n}に書き込みます。

Function: void mpn_nand_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}のビット単位の論理積を求め,その結果の補数を {rp, n}に書き込みます。

Function: void mpn_nior_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n}と{s2p, n}のビット単位の論理和を求め,その結果の補数を{rp, n}に書き込みます。

Function: void mpn_xnor_n (mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

{s1p, n} と {s2p, n}のビット単位の排他的論理和を求め,更にその結果の補数を{rp, n}に書き込みます。

Function: void mpn_com (mp_limb_t *rp, const mp_limb_t *sp, mp_size_t n)

{sp, n}のビット単位の補数を取り(訳注:ビット反転?),その結果を{rp, n}に書き戻します。

Function: void mpn_copyi (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n)

{s1p, n} から {rp, n}へ,高次リム方向からコピーします。

Function: void mpn_copyd (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n)

{s1p, n}から{rp, n}へ,低次リム方向からコピーします。

Function: void mpn_zero (mp_limb_t *rp, mp_size_t n)

{rp, n}をゼロにします。


8.1 暗号処理のための基盤関数

mpn_sec_mpn_cnd_という名前で始まる基盤関数群は,二つの同じサイズの引数に対して,同じ基盤処理を実行し,同じキャッシュアクセスパターンが生じるように実装されたもので,同じ位置に引数が存在し,マシンの状態が監修の処理開始時から変化しないという前提の元に構築されています。というのも,この関数群は暗号処理を目的としており,サイドチャンネル攻撃(side-channel attack)を防御できるように設計してあるからです。

ここで述べる暗号処理用関数群は,同じ機能を持つ「リークしやすい」関数群よりパフォーマンスが劣り,同じサイズの引数で暗号化しようとすると,15%~100%程度,遅くなってしまいます。より大きなサイズの引数に対してはもっと不利になり,漸近的に初等的なアルゴリズムの演算量に引きずられていってしまいます。

ここで述べる関数群は,明示的なメモリ割り当てを行わず,中間処理のためのメモリ空間を要求する関数はそれに当たる引数をを受け付けます。これによって,あらかじめ指定されたメモリ領域でデータ処理が行えるようになります。しかしながら,コンパイラが,指定メモリ領域にあるはずのスカラー値があふれた時にはスタック領域も確保し,結果としてそこで注意すべきデータを扱ってしまう可能性があることは留意しておいて下さい。

暗号処理用基盤関数以外にも,サイドチャネル攻撃防御が可能な基盤関数群も存在します。mpn_add_n, mpn_sub_n, mpn_lshift, mpn_rshift, mpn_zero, mpn_copyi, mpn_copyd, mpn_com, 基盤論理関数(mpn_and_n等)がそれにあたります。

但し,サイドチャネル攻撃防御性に関してはいくつかの例外があります。(1) mpn_lshift関数のアセンブラ実装の中には,shift-by-one(1によるシフト)が特殊ケースとして処理していることがあり,シフト値が注意すべきデータである時に限り,問題が発生します。(2)64ビットリムを用いるAlpha ev6とPentium4実装では,mpn_add_n関数とmpn_sub_n関数に「リークしやすい」問題があります。(3) Alpha ev6の実装では,mpn_mul_1関数もリークしやすく,結果として mpn_sec_mul関数が影響を受けてこのシステムの安全性を損なっています。

Function: mp_limb_t mpn_cnd_add_n (mp_limb_t cnd, mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)
Function: mp_limb_t mpn_cnd_sub_n (mp_limb_t cnd, mp_limb_t *rp, const mp_limb_t *s1p, const mp_limb_t *s2p, mp_size_t n)

この2つの関数は,条件付き加算と減算を実行します。cndが非ゼロであれば,mpn_add_n 関数やmpn_sub_n関数と同じ演算を実行します。 cndがゼロであれば,{s1p,n}を結果の格納先にコピーし,ゼロを返します。この関数は,条件値cndとは独立に,データエリアの位置やサイズにのみ依存した計算時間やメモリアクセスパターンを持つように設計されています。大概のマシン上ではmpn_add_n関数やmpn_sub_n関数は,計算時間も実際のリムの値とは独立に決まります。

Function: mp_limb_t mpn_sec_add_1 (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n, mp_limb_t b, mp_limb_t *tp)
Function: mp_limb_t mpn_sec_sub_1 (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n, mp_limb_t b, mp_limb_t *tp)

RA + b および A - bを格納しますs。ここでR = {rp,n}, A = {ap,n}で,bは1リムです。返り値は桁上がり・桁下がりとなります。

リークしやすいmpn_add_1関数が平均O(1)であるのに対し,これらの関数は O(N)かかります。また,スクラッチスペースとしてmpn_sec_add_1_itch(n)リム長,mpn_sec_sub_1_itch(n)リム長必要になり,これらを tpに渡す必要があります。スクラッチスペースはnリム長あることが必須で,引数の長さに比例して増やせるようにしておかなければいけません。

Function: void mpn_cnd_swap (mp_limb_t cnd, volatile mp_limb_t *ap, volatile mp_limb_t *bp, mp_size_t n)

cndが非ゼロの時は,{ap,n}と {bp,n}の値を交換します。cndがゼロの時は何もしません。 リム上の論理演算を用いて実装されており,cndの値とは無関係に,同じメモリアクセスだけを使用しています。

Function: void mpn_sec_mul (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t an, const mp_limb_t *bp, mp_size_t bn, mp_limb_t *tp)
Function: mp_size_t mpn_sec_mul_itch (mp_size_t an, mp_size_t bn)

A * Bを計算し,Rに格納します。ここでA = {ap,an}, B = {bp,bn}, R = {rp,an+bn}です。

この関数を実行するにはan >= bn > 0でなければなりません。

Rと入力引数とメモリ空間に重複があってはいけません。 A = Bの場合は,mpn_sec_sqr関数の方が高速に実行できます。

この関数はmpn_sec_mul_itch(an, bn)リム長のスクラッチスペースが必要で,tpに渡します。このスクラッチスペースは,入力値の長さに単調に比例して長く確保しなければなりません。

Function: void mpn_sec_sqr (mp_limb_t *rp, const mp_limb_t *ap, mp_size_t an, mp_limb_t *tp)
Function: mp_size_t mpn_sec_sqr_itch (mp_size_t an)

A^2を計算してRに格納します。ここでA = {ap,an}, R = {rp,2an}です。

この関数を実行するにはan > 0でなければなりません。

Rと入力値に重複があってはいけません。

この関数はmpn_sec_sqr_itch(an)リム長のスクラッチスペースが必要で,tpに渡します。このスクラッチスペースのは,入力値の長さに単調に比例して長く確保しなければなりません。

Function: void mpn_sec_powm (mp_limb_t *rp, const mp_limb_t *bp, mp_size_t bn, const mp_limb_t *ep, mp_bitcnt_t enb, const mp_limb_t *mp, mp_size_t n, mp_limb_t *tp)
Function: mp_size_t mpn_sec_powm_itch (mp_size_t bn, mp_bitcnt_t enb, size_t n)

(B raised to E) modulo Mを求めてRに格納します。ここでR = {rp,n}, M = {mp,n}, E = {ep,ceil(enb / GMP\_NUMB\_BITS)}です。

この関数を実行するには B > 0であり, M > 0が奇数であり,E < 2^enbである必要があります。

Rと入力値とのメモリ空間における重複があってはいけません。

この関数はmpn_sec_powm_itch(bn, enb, n)リム長のスクラッチスペースが必要で,tpに渡します。このスクラッチスペースは,入力値の長さに単調に比例して長く取らなければなりません。

Function: void mpn_sec_tabselect (mp_limb_t *rp, const mp_limb_t *tab, mp_size_t n, mp_size_t nents, mp_size_t which)

tabテーブルからwhichエントリを抜き出します。このテーブルはnents個のエントリがあり,それぞれnリム長あります。抜き出されたエントリはrpに格納されますs。

この関数はエントリテーブルを読み込み,サイドチャネル情報の漏えいを防止します。

Function: mp_limb_t mpn_sec_div_qr (mp_limb_t *qp, mp_limb_t *np, mp_size_t nn, const mp_limb_t *dp, mp_size_t dn, mp_limb_t *tp)
Function: mp_size_t mpn_sec_div_qr_itch (mp_size_t nn, mp_size_t dn)

the truncated quotient N / DR to N modulo Dを求め,それぞれQRに格納します。ここでN = {np,nn}, D = {dp,dn}です。Qの最大有効リムが返り値となり,残りのリムは {qp,nn-dn}, と R = {np,dn}になります。

この関数を実行するに際しては,nn >= dn >= 1であり,かつ dp[dn-1] != 0でなければなりません。Nはゼロが詰まっている可能性があるので,この条件はN >= Dであることを意味しません。

NRに重複があっても構いません。他の引数との重複はダメです。N のスペースは全部上書きされます。

この関数はmpn_sec_div_qr_itch(nn, dn)リム長のスクラッチスペースが必要で,tpに渡します。

Function: void mpn_sec_div_r (mp_limb_t *np, mp_size_t nn, const mp_limb_t *dp, mp_size_t dn, mp_limb_t *tp)
Function: mp_size_t mpn_sec_div_r_itch (mp_size_t nn, mp_size_t dn)

N modulo Dを計算し,Rに格納します。ここで N = {np,nn}, D = {dp,dn}, R ={np,dn}です。

この関数を実行するに際しては,nn >= dn >= 1かつ,dp[dn-1] != 0でなければなりません。Nはゼロが詰まっている可能性があるので,この条件はN >= Dであることを意味しません。

NRに重複があっても構いません。他の引数との重複はダメです。N のスペースは全部上書きされます。

この関数はmpn_sec_div_r_itch(nn, dn)リム長のスクラッチスペースが必要で,tpに渡します。

Function: int mpn_sec_invert (mp_limb_t *rp, mp_limb_t *ap, const mp_limb_t *mp, mp_size_t n, mp_bitcnt_t nbcnt, mp_limb_t *tp)
Function: mp_size_t mpn_sec_invert_itch (mp_size_t n)

Rthe inverse of A modulo Mを格納します。ここでR = {rp,n}, A = {ap,n}かつ M = {mp,n}です。 この関数の引数は原始的なものです。

逆数が存在していれば返り値は1,存在していなければ0で,この場合はRは不定になります。どちらの場合でも,入力値Aは破壊されます。

Mは奇数,かつnbcnt >= ceil(\log(A+1)) + ceil(\log(M+1))でなければなりません。. 安全策はnbcnt = 2 * n * GMP_NUMB_BITSですが,MAの先頭ビットに0が並ぶような場合は,小さい値を使うことでパフォーマンスが向上します。

この関数は,tpパラメータに渡すために,あらかじめmpn_sec_invert_itch(n)分のメモリが必要になります。


8.2 ネイル

この節で述べていることは全て実験的なもので,将来のGMPのバージョンにおいては消去されるか,互換性を保持しない変更が行われる可能性があります。

ネイル(nails)とは,リム(mp_limb_t)ごとに置かれる,使用しない先頭部分の数ビットのことです。ネイルを置くことで,プロセッサによっては,桁上がり・桁下がりの操作を劇的に改善することができるようになります。

基盤mpn関数は全てリムデータを受け取り,ネイルビットにゼロがあると仮定します。さすれば,返す値も同様にネイルビットゼロの値を返します。リムの配列にも,単独リムでも同様にネイルビットを適用します。

ネイルは‘--enable-nails’オプション付きで設定すると使用できるようになります。デフォルトでは,プロセッサごとにネイルビット長を規定していますが,特定の長さにしたければ‘--enable-nails=N’オプションで長さを指定します。

mpn関数レベルでは,ネイルビットをオンにしたビルドはソースレベルでもバイナリレベルでもネイルビット無の関数とは非互換になりますが,mpn関数を使ってリムを処理するプログラムレベルでは,ネイルビットの有無は関係なく同じ動作を行います。本節で述べる下記の定義を使うことで,プログラムのソースレベルでの互換性を維持することができるようになります。

mpz等の高レベルの関数では,ネイルビット有の場合でも,ネイルビット無の場合との互換性は維持するようにしなくてはなりません。

Macro: GMP_NAIL_BITS
Macro: GMP_NUMB_BITS
Macro: GMP_LIMB_BITS

GMP_NAIL_BITSはネイルビット長を表わします。0の場合はネイルビットを使用しません。GMP_NUMB_BITSはリムのビット長を表わします。GMP_LIMB_BITSmp_limb_t型の全体のビット長を表わします。つまり下記のような関係式が成り立ちます。

GMP_LIMB_BITS == GMP_NAIL_BITS + GMP_NUMB_BITS
Macro: GMP_NAIL_MASK
Macro: GMP_NUMB_MASK

前者がリムのマスク長,後者がリムの残り部分のマスク長と表わします。GMP_NAIL_MASKがゼロの時はネイルを使用しません。

GMP_NAIL_MASKの使用頻度は高くありません。ネイル部分はx >> GMP_NUMB_BITSで取り出すことができ,これはさほど大きくない定数になるからです。RISCチップに対しては有効かもしれません。

Macro: GMP_NUMB_MAX

リム部分に格納できる最大の数を表わします。GMP_NUMB_MASKと同じものになりますが,ビット単位の操作よりも比較時に分かりやすくなります。

ネイル(nail)という用語は,指の爪に由来します。つまり,リム(腕や足)の先っぽ,ということです。“numb"は数(number)の短縮形ですが,長時間,このような扱いづらい名前を見つけようとした後に開発者がどう感じるか(マヒする,凍える = numb)という意味も込めています。

将来(多分当分先)は,非ゼロのネイルを使うようになり,リム配列として表現する数には様々なネイルが入り込むことになるでしょう。さすれば,ベクトルプロセッサでは,桁上がり・桁下がりの操作を1ないし2リムだけで完結するようにできるからです。


Next: , Previous: , Up: Top   [Index]