有限体に関する演算
*********

有限体の表現および演算
===========

Asir においては, 有限体は, 正標数素体 GF(p), 標数 2 の有限体 GF(2^n) が定義できる. これらは全て, setmod_ff() により定義される.

     [0] P=pari(nextprime,2^50);
     1125899906842679
     [1] setmod_ff(P);
     1125899906842679
     [2] field_type_ff();
     1
     [3] load("fff");
     1
     [4] F=defpoly_mod2(50);
     x^50+x^4+x^3+x^2+1
     [5] setmod_ff(F);
     x^50+x^4+x^3+x^2+1
     [6] field_type_ff();
     2

setmod_ff() は, 引数が正整数 p の場合 GF(p), n 次多項式 f(x) の場合, f(x) mod 2 を定義多項式とする GF(2^n) をそれぞれ基礎体としてセットする. setmod_ff() においては引数の既約チェックは行わず, 呼び出し側が責任を持つ.

基礎体とは, あくまで有限体の元として宣言あるいは定義されたオブジェクトが, セットされた基礎体の演算に従うという意味である. 即ち, 有理数どうしの演算の結果は有理数となる. 但し, 四則演算において一方のオペランドが有限体の元の場合には, 他の元も自動的に同じ有限体の元と見なされ, 演算結果も同様になる.

0 でない有限体の元は, 数オブジェクトであり, 識別子の値は 1 である. さらに, 0 でない有限体の元の数識別子は, GF(p) の場合 6, GF(2^n) の場合 7 となる.

有限体の元の入力方法は, 有限体の種類により様々である. GF(p) の場合, simp_ff() による.

     [0] P=pari(nextprime,2^50);
     1125899906842679
     [1] setmod_ff(P);
     1125899906842679
     [2] A=simp_ff(2^100);
     3025
     [3] ntype(@@);
     6

また, GF(2^n) の場合いくつかの方法がある.

     [0] setmod_ff(x^50+x^4+x^3+x^2+1);
     x^50+x^4+x^3+x^2+1
     [1] A=@;
     (@)
     [2] ptogf2n(x^50+1);
     (@^50+1)
     [3] simp_ff(@@);
     (@^4+@^3+@^2)
     [4] ntogf2n(2^10-1);
     (@^9+@^8+@^7+@^6+@^5+@^4+@^3+@^2+@+1)

有限体の元は数であり, 体演算が可能である. @ は GF(2^n) の, GF(2)上の生成元である. 詳しくは see 数の型.

有限体上での 1 変数多項式の演算
=================

fff では, 有限体上の 1 変数多項式に対し, 無平方分解, DDF, 因数分解, 多項式の既約判定などの関数が定義されている.

いずれも, 結果は [因子, 重複度] のリストとなるが, 因子は monic となり, 入力多項式の主係数は捨てられる.

無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的なアルゴリズムを採用している.

有限体上での因数分解は, DDF の後, 次数別因子の分解の際に, Berlekamp アルゴリズムで零空間を求め, 基底ベクトルの最小多項式を求め, その根を Cantor-Zassenhaus アルゴリズムにより求める, という方法を実装している.

有限体上の楕円曲線に関する演算
===============

有限体上の楕円曲線に関するいくつかの基本的な演算が, 組み込み関数として提供されている.

楕円曲線の指定は, 長さ 2 のベクトル [A B] で行う. A, B は有限体の元で, setmod_ff で定義されている有限体が素体の場合, Y^2=X^3+AX+B, 標数 2 の体の場合 Y^2+XY=X^3+AX^2+B を表す.

楕円曲線上の点は, 無限遠点も込めて加法群をなす. この演算に関して, 加算 (ecm_add_ff()), 減算 (ecm_sub_ff()) および逆元計算のための関数 (ecm_chsgn_ff()) が提供されている. 注意すべきは, 演算の対象となる点の表現が,

  * 無限遠点は 0.

  * それ以外の点は, 長さ 3 のベクトル [X Y Z]. ただし, Z は 0 でない.

という点である. [X Y Z] は斉次座標による表現であり, アフィン座標では [X/Z Y/Z] なる点を表す. よって, アフィン座標 [X Y] で表現された点を演算対象とするには, [X Y 1] なるベクトルを生成する必要がある. 演算結果も斉次座標で得られるが, Z 座標が 1 とは限らないため, アフィン座標を求めるためには X, Y 座標を Z 座標で割る必要がある.

有限体に関する函数のまとめ
=============

setmod_ff
---------

setmod_ff([PRIME|POLY])
     :: 有限体の設定, 設定されている有限体の法, 定義多項式の表示

return
     数または多項式

prime
     素数

poly
     GF(2) 上既約な 1 変数多項式

  * 引数が正整数 PRIME の時, GF(PRIME) を基礎体として設定する.

  * 引数が多項式 POLY の時, GF(2^deg(POLY mod 2)) = GF(2)[t]/(POLY(t) mod2) を基礎体として設定する.

  * 無引数の時, 設定されている基礎体が GF(PRIME) の場合 PRIME, GF(2^n) の場合定義多項式を返す.

  * GF(2^n) の定義多項式は, GF(2) 上 n 次既約ならなんでも良いが, 効率に影響するため, defpoly_mod2() で生成するのがよい.

     [174] defpoly_mod2(100);
     x^100+x^15+1
     [175] setmod_ff(@@);
     x^100+x^15+1
     [176] setmod_ff();
     x^100+x^15+1

参照
     defpoly_mod2

field_type_ff
-------------

field_type_ff()
     :: 設定されている基礎体の種類

return
     数

  * 設定されている基礎体の種類を返す.

  * 設定なしなら 0, GF(p) なら 1, GF(2^n) なら 2 を返す.

     [0] field_type_ff();
     0
     [1] setmod_ff(3);
     3
     [2] field_type_ff();
     1
     [3] setmod_ff(x^2+x+1);
     x^2+x+1
     [4] field_type_ff();
     2

参照
     setmod_ff

field_order_ff
--------------

field_order_ff()
     :: 設定されている基礎体の位数

return
     数

  * 設定されている基礎体の位数 (元の個数) を返す.

  * 設定されている体が GF(q) ならば q を返す.

     [0] field_order_ff();
     field_order_ff : current_ff is not set
     return to toplevel
     [0] setmod_ff(3);
     3
     [1] field_order_ff();
     3
     [2] setmod_ff(x^2+x+1);
     x^2+x+1
     [3] field_order_ff();
     4

参照
     setmod_ff

characteristic_ff
-----------------

characteristic_ff()
     :: 設定されている体の標数

return
     数

  * 設定されている体の標数を返す.

  * GF(p) の場合 p, GF(2^n) の場合 2 を返す.

     [0] characteristic_ff();
     characteristic_ff : current_ff is not set
     return to toplevel
     [0] setmod_ff(3);
     3
     [1] characteristic_ff();
     3
     [2] setmod_ff(x^2+x+1);
     x^2+x+1
     [3] characteristic_ff();
     2

参照
     setmod_ff

extdeg_ff
---------

extdeg_ff()
     :: 設定されている基礎体の, 素体に対する拡大次数

return
     数

  * 設定されている基礎体の, 素体に対する拡大次数を返す.

  * GF(p) の場合 1, GF(2^n) の場合 n を返す.

     [0] extdeg_ff();
     extdeg_ff : current_ff is not set
     return to toplevel
     [0] setmod_ff(3);
     3
     [1] extdeg_ff();
     1
     [2] setmod_ff(x^2+x+1);
     x^2+x+1
     [3] extdeg_ff();
     2

参照
     setmod_ff

simp_ff
-------

simp_ff(OBJ)
     :: 数, あるいは多項式の係数を有限体の元に変換

return
     数または多項式

obj
     数または多項式

  * 数, あるいは多項式の係数を有限体の元に変換する.

  * 整数, あるいは整数係数多項式を, 有限体, あるいは有限体係数に変換するために用いる.

  * 有限体の元に対し, 法あるいは定義多項式による reduction を行う場合にも用いる.

     [0] simp_ff((x+1)^10);
     x^10+10*x^9+45*x^8+120*x^7+210*x^6+252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
     [1] setmod_ff(3);
     3
     [2] simp_ff((x+1)^10);
     1*x^10+1*x^9+1*x+1
     [3] ntype(coef(@@,10));
     6

参照
     setmod_ff, lmptop, gf2nton

random_ff
---------

random_ff()
     :: 有限体の元の乱数生成

return
     有限体の元

  * 有限体の元を乱数生成する.

  * GF(p) の場合, 0 以上 p 未満の整数であらわされる GF(p) の元, GF(2^n) の場合, n 次未満の GF(2) 上の多項式で表される GF(2^n) を返す.

  * random(), lrandom() と同じ 32bit 乱数発生器を使用している.

     [0] random_ff();
     random_ff : current_ff is not set
     return to toplevel
     [0] setmod_ff(pari(nextprime,2^40));
     1099511627791
     [1] random_ff();
     561856154357
     [2] random_ff();
     45141628299

参照
     setmod_ff, random, lrandom

lmptop
------

lmptop(OBJ)
     :: GF(p) 係数多項式の係数を整数に変換

return
     整数係数多項式

obj
     GF(p)係数多項式

  * GF(p) 係数多項式の係数を整数に変換する.

  * GF(p) の元は, 0 以上 p 未満の整数で表現されている. 多項式の各係数は, その値を整数オブジェクト(数識別子 0)としたものに変換される.

  * GF(p) の元は, 整数に変換される.

     [0] setmod_ff(pari(nextprime,2^40));
     1099511627791
     [1] F=simp_ff((x-1)^10);
     1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
     +1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
     [2] setmod_ff(547);
     547
     [3] F=simp_ff((x-1)^10);
     1*x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3+45*x^2+537*x+1
     [4] lmptop(F);
     x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3+45*x^2+537*x+1
     [5] lmptop(coef(F,1));
     537
     [6] ntype(@@);
     0

参照
     simp_ff

ntogf2n
-------

ntogf2n(M)
     :: 自然数を GF(2^n) の元に変換

return
     GF(2^n) の元

m
     非負整数

  * 自然数 M の 2 進表現 M=M0+M1*2+...+MK*2^k に対し, GF(2^n)=GF(2)[t]/(g(t)) の元 M0+M1*t+...+MK*t^k mod g(t) を返す.

  * 定義多項式による剰余は自動的には計算されないため, simp_ff() を適用する必要がある.

     [1] setmod_ff(x^30+x+1);
     x^30+x+1
     [2] N=ntogf2n(2^100);
     (@^100)
     [3] simp_ff(N);
     (@^13+@^12+@^11+@^10)

参照
     gf2nton

gf2nton
-------

gf2nton(M)
     :: GF(2^n) の元を自然数に変換

return
     非負整数

m
     GF(2^n) の元

  * gf2nton の逆変換である.

     [1] setmod_ff(x^30+x+1);
     x^30+x+1
     [2] N=gf2nton(2^100);
     (@^100)
     [3] simp_ff(N);
     (@^13+@^12+@^11+@^10)
     [4] gf2nton(N);
     1267650600228229401496703205376
     [5] gf2nton(simp_ff(N));
     15360

参照
     gf2nton

ptogf2n
-------

ptogf2n(POLY)
     :: 一変数多項式を GF(2^n) の元に変換

return
     GF(2^n) の元

poly
     一変数多項式

  * POLY の表す GF(2^n) の元を生成する. 係数は, 2 で割った余りに変換される. POLY の変数に @ を代入した結果と等しい.

     [1] setmod_ff(x^30+x+1);
     x^30+x+1
     [2] ptogf2n(x^100);
     (@^100)

参照
     gf2ntop

gf2ntop
-------

gf2ntop(M[,V])
     :: GF(2^n) の元を多項式に変換

return
     一変数多項式

m
     GF(2^n) の元

v
     不定元

  * M を表す多項式を, 整数係数の多項式オブジェクトとして返す.

  * V の指定がない場合, 直前の ptogf2n() 呼び出しにおける引数の変数 (デフォルトは x), 指定がある場合には指定された不定元を変数とする多項式を返す.

     [1] setmod_ff(x^30+x+1);
     x^30+x+1
     [2] N=simp_ff(gf2ntop(2^100));
     (@^13+@^12+@^11+@^10)
     [5] gf2ntop(N);
     [207] gf2ntop(N);
     x^13+x^12+x^11+x^10
     [208] gf2ntop(N,t);
     t^13+t^12+t^11+t^10

参照
     ptogf2n

defpoly_mod2
------------

defpoly_mod2(D)
     :: GF(2) 上既約な一変数多項式の生成

return
     多項式

d
     正整数

  * fff で定義されている.

  * 与えられた次数 D に対し, GF(2) 上 D 次の既約多項式を返す.

  * もし 既約 3 項式が存在すれば, 第 2 項の次数がもっとも小さい 3 項式, もし 既約 3 項式が存在しなければ, 既約 5 項式の中で, 第 2 項の次数がもっとも小さく, その中で第 3 項の次数がもっとも小さく, その中で第 4 項の次数がもっとも小さいものを返す.

参照
     setmod_ff

fctr_ff
-------

fctr_ff(POLY)
     :: 1 変数多項式の有限体上での既約分解

return
     リスト

poly
     有限体上の 1 変数多項式

  * fff で定義されている.

  * 一変数多項式を, 現在設定されている有限体上で既約分解する.

  * 結果は, [[F1,M1],[F2,M2],...] なるリストである. ここで, FI は monic な既約因子, MI はその重複度である.

  * POLY の主係数は捨てられる.

     [178] setmod_ff(2^64-95);
     18446744073709551521
     [179]  fctr_ff(x^5+x+1);
     [[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
     [1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]

参照
     setmod_ff

irredcheck_ff
-------------

irredcheck_ff(POLY)
     :: 1 変数多項式の有限体上での既約判定

return
     0|1

poly
     有限体上の 1 変数多項式

  * fff で定義されている.

  * 有限体上の 1 変数多項式の既約判定を行い, 既約の場合 1, それ以外は 0 を返す.

     [178] setmod_ff(2^64-95);
     18446744073709551521
     [179] ] F=x^10+random_ff();
     x^10+14687973587364016969
     [180] irredcheck_ff(F);
     1

参照
     setmod_ff

randpoly_ff
-----------

randpoly_ff(D,V)
     :: 有限体上の 乱数係数 1 変数多項式の生成

return
     多項式

d
     正整数

v
     不定元

  * fff で定義されている.

  * D 次未満, 変数が V, 係数が現在設定されている有限体に属する 1 変数多項式を生成する. 係数は random_ff() により生成される.

     [178] setmod_ff(2^64-95);
     18446744073709551521
     [179] ] F=x^10+random_ff();
     [180] randpoly_ff(3,x);
     17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
     [181] randpoly_ff(3,x);
     7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
     [182] randpoly_ff(3,x);
     10247781277095450395*x^2+10243690944992524936*x+4063829049268845492

参照
     setmod_ff, random_ff

ecm_add_ff, ecm_sub_ff, ecm_chsgn_ff
------------------------------------

ecm_add_ff(P1,P2,EC)
ecm_sub_ff(P1,P2,EC)
ecm_chsgn_ff(P1,P2,EC)
     :: 楕円曲線上の点の加算, 減算, 逆元

return
     ベクトルまたは 0

p1,p2
     長さ 3 のベクトルまたは 0

ec
     長さ 2 のベクトル

  * 現在設定されている有限体上で,  EC で定義される楕円曲線上の点 P1, P2 の和 P1+P2, 差 P1-P2, 逆元 -P1 を返す.

  * EC は, 設定されている有限体が奇標数素体の場合, Y^2=X^3+EC[0]X+EC[1], 標数 2 の場合 Y^2+XY=X^3+EC[0]X^2+EC[1] を表す.

  * 引数, 結果ともに, 無限遠点は 0 で表される.

  * P1, P2 が長さ 3 のベクトルの場合, 斉次座標による曲線上の点を表す. この場合, 第 3 座標は 0 であってはいけない.

  * 結果が長さ 3 のベクトルの場合, 第 3 座標は 0 でないが, 1 とは限らない. アフィン座標による結果を得るためには, 第 1 座標, 第 2 座標を第 3 座標で割る必要がある.

  * P1, P2 が楕円曲線上の点かどうかのチェックはしない.

     [0] setmod_ff(1125899906842679)$
     [1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
     [2] Pt1=newvect(3,[1,-412127497938252,1])$
     [3] Pt2=newvect(3,[6,-252647084363045,1])$
     [4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
     [ 560137044461222 184453736165476 125 ]
     [5] F=y^2-(x^3+EC[0]*x+EC[1])$
     [6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
     0
     [7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
     0
     [8] D=ecm_sub_ff(Pt3,Pt2,EC);
     [ 886545905133065 119584559149586 886545905133065 ]
     [9] D[0]/D[2]==Pt1[0]/Pt1[2];
     1
     [10] D[1]/D[2]==Pt1[1]/Pt1[2];
     1

参照
     setmod_ff