@node 有限体に関する演算,,, Top
@chapter 有限体に関する演算

@menu
* 有限体の表現および演算::
* 有限体上での 1 変数多項式の演算::
* 有限体上の楕円曲線に関する演算::
* 有限体に関する函数のまとめ::
@end menu

@node 有限体の表現および演算,,, 有限体に関する演算
@section 有限体の表現および演算

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

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

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

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

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

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

また, GF(2^n) の場合いくつかの方法がある. 
@example
[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)
@end example

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

@noindent

@node 有限体上での 1 変数多項式の演算,,, 有限体に関する演算
@section 有限体上での 1 変数多項式の演算

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

いずれも, 結果は [@b{因子}, @b{重複度}] のリストとなるが, 因子は monic 
となり, 入力多項式の主係数は捨てられる.
      
@noindent
無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的な
アルゴリズムを採用している. 

@example
@end example

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

@example
@end example

@node 有限体上の楕円曲線に関する演算,,, 有限体に関する演算
@section 有限体上の楕円曲線に関する演算

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

楕円曲線の指定は, 長さ 2 のベクトル @var{[a b]} で行う. @var{a}, @var{b}
は有限体の元で, 
@code{setmod_ff} で定義されている有限体が素体の場合, @var{y^2=x^3+ax+b},
標数 2 の体の場合 @var{y^2+xy=x^3+ax^2+b} を表す. 

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

@itemize @bullet
@item 無限遠点は 0.
@item それ以外の点は, 長さ 3 のベクトル @var{[x y z]}. ただし, @var{z} は
0 でない. 
@end itemize

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

@node 有限体に関する函数のまとめ,,, 有限体に関する演算
@section 有限体に関する函数のまとめ

@menu
* setmod_ff::
* field_type_ff::
* field_order_ff::
* characteristic_ff::
* extdeg_ff::
* simp_ff::
* random_ff::
* lmptop::
* ntogf2n::
* gf2nton::
* ptogf2n::
* gf2ntop::
* defpoly_mod2::
* fctr_ff::
* irredcheck_ff::
* randpoly_ff::
* ecm_add_ff ecm_sub_ff ecm_chsgn_ff::
* extdeg_ff::
@end menu

@node setmod_ff,,, 有限体に関する函数のまとめ
@subsection @code{setmod_ff}
@findex setmod_ff

@table @t
@item setmod_ff([@var{prime}|@var{poly}])
:: 有限体の設定, 設定されている有限体の法, 定義多項式の表示
@end table

@table @var
@item return
数または多項式
@item prime
素数
@item poly
GF(2) 上既約な 1 変数多項式
@end table

@itemize @bullet
@item
引数が正整数 @var{prime} の時, GF(@var{prime}) を基礎体として設定する. 
@item
引数が多項式 @var{poly} の時, 
GF(2^deg(@var{poly} mod 2)) = GF(2)[t]/(@var{poly}(t) mod2)
を基礎体として設定する.
@item
無引数の時, 設定されている基礎体が GF(@var{prime}) の場合 @var{prime},
GF(2^n) の場合定義多項式を返す. 
@item
GF(2^n) の定義多項式は, GF(2) 上 n 次既約ならなんでも良いが, 効率に
影響するため, @code{defpoly_mod2()} で生成するのがよい. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{defpoly_mod2}
@end table

@node field_type_ff,,, 有限体に関する函数のまとめ
@subsection @code{field_type_ff}
@findex field_type_ff

@table @t
@item field_type_ff()
:: 設定されている基礎体の種類
@end table

@table @var
@item return
数
@end table

@itemize @bullet
@item
設定されている基礎体の種類を返す. 
@item
設定なしなら 0, GF(p) なら 1, GF(2^n) なら 2 を返す. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node field_order_ff,,, 有限体に関する函数のまとめ
@subsection @code{field_order_ff}
@findex field_order_ff

@table @t
@item field_order_ff()
:: 設定されている基礎体の位数
@end table

@table @var
@item return
数
@end table

@itemize @bullet
@item
設定されている基礎体の位数 (元の個数) を返す. 
@item
設定されている体が GF(q) ならば q を返す. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node characteristic_ff,,, 有限体に関する函数のまとめ
@subsection @code{characteristic_ff}
@findex characteristic_ff

@table @t
@item characteristic_ff()
:: 設定されている体の標数
@end table

@table @var
@item return
数
@end table

@itemize @bullet
@item
設定されている体の標数を返す. 
@item
GF(p) の場合 p, GF(2^n) の場合 2 を返す. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node extdeg_ff,,, 有限体に関する函数のまとめ
@subsection @code{extdeg_ff}
@findex extdeg_ff

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

@table @var
@item return
数
@end table

@itemize @bullet
@item
設定されている基礎体の, 素体に対する拡大次数を返す. 
@item
GF(p) の場合 1, GF(2^n) の場合 n を返す. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node simp_ff,,, 有限体に関する函数のまとめ
@subsection @code{simp_ff}
@findex simp_ff

@table @t
@item simp_ff(@var{obj})
:: 数, あるいは多項式の係数を有限体の元に変換
@end table

@table @var
@item return
数または多項式
@item obj
数または多項式
@end table

@itemize @bullet
@item
数, あるいは多項式の係数を有限体の元に変換する. 
@item
整数, あるいは整数係数多項式を, 有限体, あるいは有限体係数に変換するために
用いる. 
@item
有限体の元に対し, 法あるいは定義多項式による reduction を行う場合にも
用いる. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}
@end table

@node random_ff,,, 有限体に関する函数のまとめ
@subsection @code{random_ff}
@findex random_ff

@table @t
@item random_ff()
:: 有限体の元の乱数生成
@end table

@table @var
@item return
有限体の元
@end table

@itemize @bullet
@item
有限体の元を乱数生成する. 
@item
GF(p) の場合, 0 以上 p 未満の整数であらわされる GF(p) の元, 
GF(2^n) の場合, n 次未満の GF(2) 上の多項式で表される GF(2^n) を
返す. 
@item
@code{random()}, @code{lrandom()} と同じ 32bit 乱数発生器を使用している. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}, @fref{random}, @fref{lrandom}
@end table

@node lmptop,,, 有限体に関する函数のまとめ
@subsection @code{lmptop}
@findex lmptop

@table @t
@item lmptop(@var{obj})
:: GF(p) 係数多項式の係数を整数に変換
@end table

@table @var
@item return
整数係数多項式
@item obj
GF(p)係数多項式
@end table

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

@example
[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
@end example

@table @t
@item 参照
@fref{simp_ff}
@end table

@node ntogf2n,,, 有限体に関する函数のまとめ
@subsection @code{ntogf2n}
@findex ntogf2n

@table @t
@item ntogf2n(@var{m})
:: 自然数を GF(2^n) の元に変換
@end table

@table @var
@item return
GF(2^n) の元
@item m
非負整数
@end table

@itemize @bullet
@item
自然数 @var{m} の 2 進表現 @var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k
に対し, GF(2^n)=GF(2)[t]/(g(t)) の元 
@var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) を返す. 
@item
定義多項式による剰余は自動的には計算されないため, @code{simp_ff()} を
適用する必要がある. 
@end itemize

@example
[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)
@end example

@table @t
@item 参照
@fref{gf2nton}
@end table

@node gf2nton,,, 有限体に関する函数のまとめ
@subsection @code{gf2nton}
@findex gf2nton

@table @t
@item gf2nton(@var{m})
:: GF(2^n) の元を自然数に変換
@end table

@table @var
@item return
非負整数
@item m
GF(2^n) の元
@end table

@itemize @bullet
@item
@code{gf2nton} の逆変換である. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{gf2nton}
@end table

@node ptogf2n,,, 有限体に関する函数のまとめ
@subsection @code{ptogf2n}
@findex ptogf2n

@table @t
@item ptogf2n(@var{poly})
:: 一変数多項式を GF(2^n) の元に変換
@end table

@table @var
@item return
GF(2^n) の元
@item poly
一変数多項式
@end table

@itemize @bullet
@item
@var{poly} の表す GF(2^n) の元を生成する. 係数は, 2 で割った余りに
変換される. 
@var{poly} の変数に @code{@@} を代入した結果と等しい. 
@end itemize

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

@table @t
@item 参照
@fref{gf2ntop}
@end table

@node gf2ntop,,, 有限体に関する函数のまとめ
@subsection @code{gf2ntop}
@findex gf2ntop

@table @t
@item gf2ntop(@var{m}[,@var{v}])
:: GF(2^n) の元を多項式に変換
@end table

@table @var
@item return
一変数多項式
@item m
GF(2^n) の元
@item v
不定元
@end table

@itemize @bullet
@item
@var{m} を表す多項式を, 整数係数の多項式オブジェクトとして返す. 
@item @var{v} の指定がない場合, 直前の @code{ptogf2n()} 呼び出し
における引数の変数 (デフォルトは @code{x}), 指定がある場合には
指定された不定元を変数とする多項式を返す. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{ptogf2n}
@end table

@node defpoly_mod2,,, 有限体に関する函数のまとめ
@subsection @code{defpoly_mod2}
@findex defpoly_mod2

@table @t
@item defpoly_mod2(@var{d})
:: GF(2) 上既約な一変数多項式の生成
@end table

@table @var
@item return
多項式
@item d
正整数
@end table

@itemize @bullet
@item
@samp{fff} で定義されている. 
@item
与えられた次数 @var{d} に対し, GF(2) 上 @var{d} 次の既約多項式を返す. 
@item
もし 既約 3 項式が存在すれば, 第 2 項の次数がもっとも小さい 3 項式, もし 既約 
3 項式が存在しなければ, 既約 5 項式の中で, 第 2 項の次数がもっとも小さく, 
その中で第 3 項の次数がもっとも小さく, その中で第 4 項の次数がもっとも
小さいものを返す. 
@end itemize

@example
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node fctr_ff,,, 有限体に関する函数のまとめ
@subsection @code{fctr_ff}
@findex fctr_ff

@table @t
@item fctr_ff(@var{poly})
:: 1 変数多項式の有限体上での既約分解
@end table

@table @var
@item return
リスト
@item poly
有限体上の 1 変数多項式
@end table

@itemize @bullet
@item
@samp{fff} で定義されている. 
@item
一変数多項式を, 現在設定されている有限体上で既約分解する. 
@item
結果は, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] なる
リストである. ここで, @var{fi} は monic な既約因子, @var{mi} はその
重複度である. 
@item
@var{poly} の主係数は捨てられる. 
@end itemize

@example
[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]]
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node irredcheck_ff,,, 有限体に関する函数のまとめ
@subsection @code{irredcheck_ff}
@findex irredcheck_ff

@table @t
@item irredcheck_ff(@var{poly})
:: 1 変数多項式の有限体上での既約判定
@end table

@table @var
@item return
0|1
@item poly
有限体上の 1 変数多項式
@end table

@itemize @bullet
@item
@samp{fff} で定義されている. 
@item
有限体上の 1 変数多項式の既約判定を行い, 既約の場合 1, それ以外は 0 を返す. 
@end itemize

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

@table @t
@item 参照
@fref{setmod_ff}
@end table

@node randpoly_ff,,, 有限体に関する函数のまとめ
@subsection @code{randpoly_ff}
@findex randpoly_ff

@table @t
@item randpoly_ff(@var{d},@var{v})
:: 有限体上の 乱数係数 1 変数多項式の生成
@end table

@table @var
@item return
多項式
@item d
正整数
@item v
不定元
@end table

@itemize @bullet
@item
@samp{fff} で定義されている. 
@item
@var{d} 次未満, 変数が @var{v}, 係数が現在設定されている有限体に属する
1 変数多項式を生成する. 係数は @code{random_ff()} により生成される. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}, @fref{random_ff}
@end table

@node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, 有限体に関する函数のまとめ
@subsection @code{ecm_add_ff}, @code{ecm_sub_ff}, @code{ecm_chsgn_ff}
@findex ecm_add_ff
@findex ecm_sub_ff
@findex ecm_chsgn_ff

@table @t
@item ecm_add_ff(@var{p1},@var{p2},@var{ec})
@itemx ecm_sub_ff(@var{p1},@var{p2},@var{ec})
@itemx ecm_chsgn_ff(@var{p1},@var{p2},@var{ec})
:: 楕円曲線上の点の加算, 減算, 逆元
@end table

@table @var
@item return
ベクトルまたは 0
@item p1,p2
長さ 3 のベクトルまたは 0
@item ec
長さ 2 のベクトル        
@end table

@itemize @bullet
@item
現在設定されている有限体上で,  @var{ec} で定義される楕円曲線上の
点 @var{p1}, @var{p2} の和 @var{p1+p2}, 差 @var{p1-p2}, 逆元 @var{-p1} を返す. 
@item
@var{ec} は, 設定されている有限体が奇標数素体の場合, 
@var{y^2=x^3+ec[0]x+ec[1]}, 標数 2 の場合 @var{y^2+xy=x^3+ec[0]x^2+ec[1]} 
を表す. 
@item
引数, 結果ともに, 無限遠点は 0 で表される. 
@item
@var{p1}, @var{p2} が長さ 3 のベクトルの場合, 斉次座標による曲線上の
点を表す. この場合, 第 3 座標は 0 であってはいけない. 
@item
結果が長さ 3 のベクトルの場合, 第 3 座標は 0 でないが, 1 とは限らない. 
アフィン座標による結果を得るためには, 第 1 座標, 第 2 座標を第 3 座標
で割る必要がある. 
@item
@var{p1}, @var{p2} が楕円曲線上の点かどうかのチェックはしない. 
@end itemize

@example
[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
@end example

@table @t
@item 参照
@fref{setmod_ff}
@end table