@comment $OpenXM: OpenXM/src/asir-doc/parts/ff.texi,v 1.8 2005/09/08 07:40:49 noro Exp $
\BJP
@node 有限体に関する演算,,, Top
@chapter 有限体に関する演算
\E
\BEG
@node Finite fields,,, Top
@chapter Finite fields
\E

@menu
\BJP
* 有限体の表現および演算::
* 有限体上での 1 変数多項式の演算::
* 小標数有限体上での多項式の演算::
* 有限体上の楕円曲線に関する演算::
* 有限体に関する函数のまとめ::
\E
\BEG
* Representation of finite fields::
* Univariate polynomials on finite fields::
* Polynomials on small finite fields::
* Elliptic curves on finite fields::
* Functions for Finite fields::
\E
@end menu

\BJP
@node 有限体の表現および演算,,, 有限体に関する演算
@section 有限体の表現および演算
\E
\BEG
@node Representation of finite fields,,, Finite fields
@section Representation of finite fields
\E

@noindent
\BJP
@b{Asir} においては, 有限体は, 正標数素体 GF(@var{p}), 標数 2 の有限体 GF(2^@var{n}),
GF(@var{p}) の @var{n} 次拡大 GF(@var{p^n})
が定義できる. これらは全て, @code{setmod_ff()} により定義される. 
\E
\BEG
On @b{Asir} GF(@var{p}), GF(2^@var{n}), GF(@var{p^n}) can be defined, where
GF(@var{p}) is a finite prime field of charateristic @var{p},
GF(2^@var{n}) is a finite field of characteristic 2 and
GF(@var{p^n}) is a finite extension of GF(@var{p}). These are
all defined by @code{setmod_ff()}.
\E

@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
[7] setmod_ff(x^3+x+1,1125899906842679);
[1*x^3+1*x+1,1125899906842679]
[8] field_type_ff();
3
[9] setmod_ff(3,5);
[3,x^5+2*x+1,x]
[10] field_type_ff();
4
@end example
\BJP
@code{setmod_ff()} は, さまざまなタイプの有限体を基礎体としてセットする. 
引数が正整数 @var{p} の場合 GF(@var{p}), @var{n} 次多項式 f(x) の場
合, f(x) mod 2 を定義多項式とする GF(2^@var{n}) をそれぞれ基礎体としてセットす
る. また, 有限素体の有限次拡大も定義できる. 詳しくは @xref{数の型}.
@code{setmod_ff()} においては引数の既約チェックは行わず, 呼び出し側
が責任を持つ.

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

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

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

\BEG
If @var{p} is a positive integer, @code{setmod_ff(@var{p})} sets
GF(@var{p}) as the current base field. 
If @var{f} is a univariate polynomial of degree @var{n},
@code{setmod_ff(@var{f})} sets GF(2^@var{n}) as the current
base field.  GF(2^@var{n}) is represented
as an algebraic extension of GF(2) with the defining polynomial
@var{f mod 2}. Furthermore, finite extensions of prime finite fields
can be defined. @xref{Types of numbers}.
In all cases the primality check of the argument is
not done and the caller is responsible for it.

Correctly speaking there is no actual object corresponding to a 'base field'.
Setting a base field means that operations on elements of finite fields 
are done according to the arithmetics of the base field. Thus, if 
operands of an arithmetic operation are both rational numbers, then the result
is also a rational number. However, if one of the operands is in
a finite field, then the other is automatically regarded as in the
same finite field and the operation is done in the finite field.

A non zero element of a finite field belongs to the number and has object
identifier 1. Its number identifier is 6 if the finite field is GF(@var{p}),
7 if it is GF(2^@var{n}).

There are several methods to input an element of a finite field.
An element of GF(@var{p}) can be input by @code{simp_ff()}.
\E

@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

\JP また, GF(2^@var{n}) の場合いくつかの方法がある. 
\EG In the case of GF(2^@var{n}) the following methods are available.

@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

\BJP
有限体の元は数であり, 体演算が可能である. @code{@@} は
GF(2^@var{n}) の, GF(2) 上の生成元である. 詳しくは @xref{数の型}.
\E
\BEG
Elements of finite fields are numbers and one can apply field arithmetics
to them. @code{@@} is a generator of GF(2^@var{n}) over GF(2).
@xref{Types of numbers}.
\E

@noindent

\BJP
@node 有限体上での 1 変数多項式の演算,,, 有限体に関する演算
@section 有限体上での 1 変数多項式の演算
\E
\BEG
@node Univariate polynomials on finite fields,,, Finite fields
@section Univariate polynomials on finite fields
\E

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

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

有限体上での因数分解は, DDF の後, 次数別因子の分解の際に, Berlekamp
アルゴリズムで零空間を求め, 基底ベクトルの最小多項式を求め, その根
を Cantor-Zassenhaus アルゴリズムにより求める, という方法を実装している. 
\E
\BEG
In @samp{fff} square-free factorization, DDF (distinct degree factorization),
irreducible factorization and primality check are implemented for
univariate polynomials over finite fields.

Factorizers return lists of [@b{factor},@b{multiplicity}]. The factor
part is monic and the information on the leading coefficient of the
input polynomial is abandoned.
      
The algorithm used in square-free factorization is the most primitive one.

The irreducible factorization proceeds as follows.

@enumerate
@item DDF
@item Nullspace computation by Berlekamp algorithm
@item Root finding of minimal polynomials of bases of the nullspace
@item Separation of irreducible factors by the roots
@end enumerate
\E

@noindent

\BJP
@node 小標数有限体上での多項式の演算,,, 有限体に関する演算
@section 小標数有限体上での多項式の演算
\E
\BEG
@node Polynomials on small finite fields,,, Finite fields
@section Polynomials on small finite fields
\E

\BJP
小標数有限体係数の多項式に限り, 多変数多項式の因数分解が
組み込み関数として実装されている. 関数は @code{sffctr()}
である. また, @code{modfctr()} も, 有限素体上で多変数
多項式の因数分解を行うが, 実際には, 内部で十分大きな
拡大体を設定し, @code{sffctr()} を呼び出して, 
最終的に素体上の因子を構成する, という方法で計算している. 
\E

\BEG
A multivariate polynomial over small finite field
set by @code{setmod_ff(p,n)} can be factorized by
using a builtin function @code{sffctr()}. @code{modfctr()}
also factorizes a polynomial over a finite prime field.
Internally, @code{modfctr()} creates a sufficiently large
field extension of the specified ground field, and
it calls @code{sffctr()}, then it constructs irreducible
factors over the ground field from the factors returned by
@code{sffctr()}.
\E

\BJP
@node 有限体上の楕円曲線に関する演算,,, 有限体に関する演算
@section 有限体上の楕円曲線に関する演算
\E
\BEG
@node Elliptic curves on finite fields,,, Finite fields
@section Elliptic curves on finite fields
\E

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

楕円曲線の指定は, 長さ 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} 座標で
割る必要がある. 
\E

\BEG
Several fundamental operations on elliptic curves over finite fields
are provided as built-in functions.

An elliptic curve is specified by a vector [@var{a b}] of length 2,
where @var{a}, @var{b} are elements of finite fields.
If the current base field is a prime field, then [@var{a b}] represents
@var{y^2=x^3+ax+b}. If the current base field is a finite field of
characteristic 2, then [@var{a b}] represents @var{y^2+xy=x^3+ax^2+b}.

Points on an elliptic curve together with the point at infinity
forms an additive group. The addition, the subtraction and the
additive inverse operation are provided as @code{ecm_add_ff()},
@code{ecm_sub_ff()} and @code{ecm_chsgn_ff()} respectively.
Here the representation of points are as follows.

@itemize @bullet
@item 0 denotes the point at infinity.
@item The other points are represented by vectors [@var{x y z}] of
length 3 with non-zero @var{z}.
@end itemize

[@var{x y z}] represents a projective coordinate and
it corresponds to [@var{x/z y/z}] in the affine coordinate.
To apply the above operations to a point [@var{x y}],
[@var{x y 1}] should be used instead as an argument.
The result of an operation is also represented by the projective 
coordinate. As the third coordinate is not always equal to 1,
one has to divide the first and the scond coordinate by the third
one to obtain the affine coordinate.
\E

\BJP
@node 有限体に関する函数のまとめ,,, 有限体に関する演算
@section 有限体に関する函数のまとめ
\E
\BEG
@node Functions for Finite fields,,, Finite fields
@section Functions for Finite fields
\E

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

\JP @node setmod_ff,,, 有限体に関する函数のまとめ
\EG @node setmod_ff,,, Functions for Finite fields
@subsection @code{setmod_ff}
@findex setmod_ff

@table @t
@item setmod_ff([@var{p}|@var{defpoly2}])
@itemx setmod_ff([@var{defpolyp},@var{p}])
@itemx setmod_ff([@var{p},@var{n}])
\JP :: 有限体の設定, 設定されている有限体の法, 定義多項式の表示
\EG :: Sets/Gets the current base fields.
@end table

@table @var
@item return
\JP 数または多項式
\EG number or polynomial
@item p
\JP 素数
\EG prime
@item defpoly2
\JP GF(2) 上既約な 1 変数多項式
\EG univariate polynomial irreducible over GF(2)
@item defpolyp
\JP GF(@var{p}) 上既約な 1 変数多項式
\EG univariate polynomial irreducible over GF(@var{p})
@item n
\JP 拡大次数
\EG the extension degree
@end table

@itemize @bullet
\BJP
@item
引数が正整数 @var{p} の時, GF(@var{p}) を基礎体として設定する. 
@item
引数が多項式 @var{defpoly2} の時, 
GF(2^deg(@var{defpoly2} mod 2)) = GF(2)[t]/(@var{defpoly2}(t) mod 2)
を基礎体として設定する.
@item
引数が @var{defpolyp} と @var{p} の時, 
GF(@var{p^deg(defpolyp)}) を基礎体として設定する.
@item
引数が @var{p} と @var{n} の時, 
GF(@var{p^n}) を基礎体として設定する. @var{p^n} は @var{2^29} 未満で
なければならない. また, @var{p} が @var{2^14} 以上のとき, 
@var{n} は 1 でなければならない. 
@item
無引数の時, 設定されている基礎体が GF(@var{p})の場合 @var{p},
GF(2^@var{n}) の場合定義多項式を返す. 
基礎体が @code{setmod_ff(@var{defpoly},@var{p})} で定義された
GF(@var{p}^@var{n}) の場合, [@var{defpoly},@var{p}] を返す.
基礎体が @code{setmod_ff(@var{p},@var{n})} で定義された
GF(p^@var{n}) の場合,
[@var{p},@var{defpoly},@var{prim_elem}] を返す. ここで, @var{defpoly}
は, @var{n} 次拡大の定義多項式, @var{prim_elem} は, GF(@var{p^n})の
乗法群の生成元を意味する.
@item
GF(2^@var{n}) の定義多項式は, GF(2) 上 n 次既約ならなんでも良いが, 効率に
影響するため, @code{defpoly_mod2()} で生成するのがよい. 
\E
\BEG
@item
If the argument is a non-negative integer @var{p}, GF(@var{p})
is set as the current base field.
@item
If the argument is a polynomial @var{defpoly2},
GF(2^deg(@var{defpoly2} mod 2)) = GF(2)[t]/(@var{defpoly2}(t) mod2)
is set as the current base field.
@item
If the arguments are a polynomial @var{defpolyp} and a prime @var{p},
GF(@var{p}^deg(@var{defpolyp})) = GF(@var{p})[t]/(@var{defpolyp}(t))
is set as the current base field.
@item
If the arguments are a prime @var{p} and an extension degree @var{n},
GF(@var{p^n}) is set as the current base field. @var{p^n} must be
less than @var{2^29} and if @var{p} is greater than or equal to @var{2^14},
then @var{n} must be equal to 1.
@item
If no argument is specified, the modulus indicating the current base field
is returned. If the current base field is GF(@var{p}), @var{p} is
returned. If it is GF(2^@var{n}), the defining polynomial is returned.
If it is GF(@var{p^n}) defined by @code{setmod_ff(@var{defpoly},@var{p})},
[@var{defpolyp},@var{p}] is returned.
If it is GF(@var{p^n}) defined by @code{setmod_ff(@var{p},@var{n})},
[@var{p},@var{defpoly},@var{prim_elem}] is returned. Here, @var{defpoly}
is the defining polynomial of the @var{n}-th extension,
and @var{prim_elem} is the generator of the multiplicative group
of GF(@var{p^n}).
@item
Any irreducible univariate polynomial over GF(2) is available to
set GF(2^@var{n}). However the use of @code{defpoly_mod2()} is recommended
for efficiency.
\E
@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
[177] setmod_ff(x^4+x+1,547);
[1*x^4+1*x+1,547]
[178] setmod_ff(2,5);
[2,x^5+x^2+1,x]
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{defpoly_mod2}
@end table

\JP @node field_type_ff,,, 有限体に関する函数のまとめ
\EG @node field_type_ff,,, Functions for Finite fields
@subsection @code{field_type_ff}
@findex field_type_ff

@table @t
@item field_type_ff()
\JP :: 設定されている基礎体の種類
\EG :: Type of the current base field.
@end table

@table @var
@item return
\JP 整数
\EG integer
@end table

@itemize @bullet
\BJP
@item
設定されている基礎体の種類を返す. 
@item
設定なしなら 0, GF(@var{p}) なら 1, GF(2^@var{n}) なら 2 を返す. 
\E
\BEG
@item
Returns the type of the current base field.
@item
If no field is set, 0 is returned. If GF(@var{p}) is set, 1 is returned.
If GF(2^@var{n}) is set, 2 is returned.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node field_order_ff,,, 有限体に関する函数のまとめ
\EG @node field_order_ff,,, Functions for Finite fields
@subsection @code{field_order_ff}
@findex field_order_ff

@table @t
@item field_order_ff()
\JP :: 設定されている基礎体の位数
\EG :: Order of the current base field.
@end table

@table @var
@item return
\JP 整数
\EG integer
@end table

@itemize @bullet
\BJP
@item
設定されている基礎体の位数 (元の個数) を返す. 
@item
設定されている体が GF(@var{q}) ならば q を返す. 
\E
\BEG
@item
Returns the order of the current base field.
@item
@var{q} is returned if the current base field is GF(@var{q}).
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node characteristic_ff,,, 有限体に関する函数のまとめ
\EG @node characteristic_ff,,, Functions for Finite fields
@subsection @code{characteristic_ff}
@findex characteristic_ff

@table @t
@item characteristic_ff()
\JP :: 設定されている体の標数
\EG :: Characteristic of the current base field.
@end table

@table @var
@item return
\JP 整数
\EG integer
@end table

@itemize @bullet
\BJP
@item
設定されている体の標数を返す. 
@item
GF(@var{p}) の場合 @var{p}, GF(2^@var{n}) の場合 2 を返す. 
\E
\BEG
@item
Returns the characteristic of the current base field.
@item
@var{p} is returned if GF(@var{p}), where @var{p} is a prime, is set.
@var{2} is returned if GF(2^@var{n}) is set.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node extdeg_ff,,, 有限体に関する函数のまとめ
\EG @node extdeg_ff,,, Functions for Finite fields
@subsection @code{extdeg_ff}
@findex extdeg_ff

@table @t
@item extdeg_ff()
\JP :: 設定されている基礎体の, 素体に対する拡大次数
\EG :: Extension degree of the current base field over the prime field.
@end table

@table @var
@item return
\JP 整数
\EG integer
@end table

@itemize @bullet
\BJP
@item
設定されている基礎体の, 素体に対する拡大次数を返す. 
@item
GF(@var{p}) の場合 1, GF(2^@var{n}) の場合 @var{n} を返す. 
\E
\BEG
@item
Returns the extension degree of the current base field over the prime field.
@item
1 is returned if GF(@var{p}), where @var{p} is a prime, is set.
@var{n} is returned if GF(2^@var{n}) is set.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node simp_ff,,, 有限体に関する函数のまとめ
\EG @node simp_ff,,, Functions for Finite fields
@subsection @code{simp_ff}
@findex simp_ff

@table @t
@item simp_ff(@var{obj})
\JP :: 数, あるいは多項式の係数を有限体の元に変換
\BEG
:: Converts numbers or coefficients of polynomials into elements
in finite fields.
\E
@end table

@table @var
@item return
\JP 数または多項式
\EG number or polynomial
@item obj
\JP 数または多項式
\EG number or polynomial
@end table

@itemize @bullet
\BJP
@item
数, あるいは多項式の係数を有限体の元に変換する. 
@item
整数, あるいは整数係数多項式を, 有限体, あるいは有限体係数に変換するために
用いる. 
@item
有限体の元に対し, 法あるいは定義多項式による reduction を行う場合にも
用いる. 
@item
小標数有限体の元に変換する場合, 一旦素体上に射影してから, 拡大体の
元に変換される. 拡大体の元に直接変換するには @code{ptosfp()} を
用いる. 
\E
\BEG
@item
Converts numbers or coefficients of polynomials into elements in finite
fields.
@item
It is used to convert integers or intrgral polynomials int
elements of finite fields or polynomials over finite fields.
@item
An element of a finite field may not have the reduced representation.
In such case an application of @code{simp_ff} ensures that the output has
the reduced representation.
If a small finite field is set as a ground field,
an integer is projected the finite prime field, then 
it is embedded into the ground field. @code{ptosfp()} 
can be used for direct projection to the ground field.
\E
@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
[4] setmod_ff(2,3);
[2,x^3+x+1,x]
[5] simp_ff(1);
@@_0
[6] simp_ff(2);
0
[7] ptosfp(2);
@@_1
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}, @fref{ptosfp sfptop}
@end table

\JP @node random_ff,,, 有限体に関する函数のまとめ
\EG @node random_ff,,, Functions for Finite fields
@subsection @code{random_ff}
@findex random_ff

@table @t
@item random_ff()
\JP :: 有限体の元の乱数生成
\EG :: Random generation of an element of a finite field.
@end table

@table @var
@item return
\JP 有限体の元
\EG element of a finite field
@end table

@itemize @bullet
\BJP
@item
有限体の元を乱数生成する. 
@item
@code{random()}, @code{lrandom()} と同じ 32bit 乱数発生器を使用している. 
\E
\BEG
@item
Generates an element of the current base field randomly.
@item
The same random generator as in @code{random()}, @code{lrandom()}
is used.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}, @fref{random}, @fref{lrandom}
@end table

\JP @node lmptop,,, 有限体に関する函数のまとめ
\EG @node lmptop,,, Functions for Finite fields
@subsection @code{lmptop}
@findex lmptop

@table @t
@item lmptop(@var{obj})
\JP :: GF(@var{p}) 係数多項式の係数を整数に変換
\EG :: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
@end table

@table @var
@item return
\JP 整数係数多項式
\EG integral polynomial
@item obj
\JP GF(@var{p}) 係数多項式
\EG polynomial over GF(@var{p})
@end table

@itemize @bullet
\BJP
@item
GF(@var{p}) 係数多項式の係数を整数に変換する. 
@item
GF(@var{p}) の元は, 0 以上 p 未満の整数で表現されている. 
多項式の各係数は, その値を整数オブジェクト(数識別子 0)としたものに
変換される. 
\E
\BEG
@item
Converts the coefficients of a polynomial over GF(@var{p}) into integers.
@item
An element of GF(@var{p}) is represented by a non-negative integer @var{r} less than
@var{p}.
Each coefficient of a polynomial is converted into an integer object
whose value is @var{r}.
\E
@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
\JP @item 参照
\EG @item References
@fref{simp_ff}
@end table

\JP @node ntogf2n,,, 有限体に関する函数のまとめ
\EG @node ntogf2n,,, Functions for Finite fields
@subsection @code{ntogf2n}
@findex ntogf2n

@table @t
@item ntogf2n(@var{m})
\JP :: 自然数を GF(2^@var{n}) の元に変換
\EG :: Converts a non-negative integer into an element of GF(2^@var{n}).
@end table

@table @var
@item return
\JP GF(2^@var{n}) の元
\EG element of GF(2^@var{n})
@item m
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
自然数 @var{m} の 2 進表現 @var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k
に対し, GF(2^@var{n})=GF(2)[t]/(g(t)) の元 
@var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) を返す. 
@item
定義多項式による剰余は自動的には計算されないため, @code{simp_ff()} を
適用する必要がある. 
\E
\BEG
@item
Let @var{m} be a non-negative integer.
@var{m} has the binary representation
@var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k.
This function returns an element of  GF(2^@var{n}) = GF(2)[t]/(g(t)),
@var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t).
@item
Apply @code{simp_ff()} to reduce the result.
\E
@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
\JP @item 参照
\EG @item References
@fref{gf2nton}
@end table

\JP @node gf2nton,,, 有限体に関する函数のまとめ
\EG @node gf2nton,,, Functions for Finite fields
@subsection @code{gf2nton}
@findex gf2nton

@table @t
@item gf2nton(@var{m})
\JP :: GF(2^@var{n}) の元を自然数に変換
\EG :: Converts an element of GF(2^@var{n}) into a non-negative integer.
@end table

@table @var
@item return
\JP 非負整数
\EG non-negative integer
@item m
\JP GF(2^@var{n}) の元
\EG element of GF(2^@var{n})
@end table

@itemize @bullet
@item
\JP @code{gf2nton} の逆変換である. 
\EG The inverse of @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
\JP @item 参照
\EG @item References
@fref{gf2nton}
@end table

\JP @node ptogf2n,,, 有限体に関する函数のまとめ
\EG @node ptogf2n,,, Functions for Finite fields
@subsection @code{ptogf2n}
@findex ptogf2n

@table @t
@item ptogf2n(@var{poly})
\JP :: 一変数多項式を GF(2^@var{n}) の元に変換
\EG :: Converts a univariate polynomial into an element of GF(2^@var{n}).
@end table

@table @var
@item return
\JP GF(2^@var{n}) の元
\EG element of GF(2^@var{n})
@item poly
\JP 一変数多項式
\EG univariate polynomial
@end table

@itemize @bullet
@item
\BJP
@var{poly} の表す GF(2^@var{n}) の元を生成する. 係数は, 2 で割った余りに
変換される. 
@var{poly} の変数に @code{@@} を代入した結果と等しい. 
\E
\BEG
Generates an element of GF(2^@var{n}) represented by @var{poly}.
The coefficients are reduced modulo 2.
The output is equal to the result by substituting @code{@@} for
the variable of @var{poly}.
\E
@end itemize

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

@table @t
\JP @item 参照
\EG @item References
@fref{gf2ntop}
@end table

\JP @node gf2ntop,,, 有限体に関する函数のまとめ
\EG @node gf2ntop,,, Functions for Finite fields
@subsection @code{gf2ntop}
@findex gf2ntop

@table @t
@item gf2ntop(@var{m}[,@var{v}])
\JP :: GF(2^@var{n}) の元を多項式に変換
\EG :: Converts an element of GF(2^@var{n}) into a polynomial.
@end table

@table @var
@item return
\JP 一変数多項式
\EG univariate polynomial
@item m
\JP GF(2^@var{n}) の元
\EG an element of GF(2^@var{n})
@item v
\JP 不定元
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
@var{m} を表す多項式を, 整数係数の多項式オブジェクトとして返す. 
@item
@var{v} の指定がない場合, 直前の @code{ptogf2n()} 呼び出し
における引数の変数 (デフォルトは @code{x}), 指定がある場合には
指定された不定元を変数とする多項式を返す. 
\E
\BEG
@item
Returns a polynomial representing @var{m}.
@item
If @var{v} is used as the variable of the output.
If @var{v} is not specified, the variable of the argument
of the latest @code{ptogf2n()} call. The default variable is @code{x}.
\E
@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
\JP @item 参照
\EG @item References
@fref{ptogf2n}
@end table

\JP @node ptosfp sfptop,,, 有限体に関する函数のまとめ
\EG @node ptosfp sfptop,,, Functions for Finite fields
@subsection @code{ptosfp}, @code{sfptop}
@findex ptosfp
@findex sfptop

@table @t
@item ptosfp(@var{p})
@itemx sfptop(@var{p})
\JP :: 小標数有限体への変換, 逆変換
\EG :: Transformation to/from a small finite field
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item p
\JP 多項式
\EG polynomial
@end table

@itemize @bullet
\BJP
@item
@code{ptosfp()} は, 多項式の係数を, 現在設定されている小標数有限体
GF(p^@var{n}) の元に直接変換する. 係数が既に有限体の元の場合は変化しない. 
正整数の場合, まず位数で剰余を計算したあと, 標数 @var{p} により @var{p}
進展開し, @var{p} を x に置き換えた多項式を, 原始元表現に変換する. 
例えば, GF(3^5) は GF(3)[x]/(x^5+2*x+1) として表現され, その各
元は原始元 x に関するべき指数 @var{k} により @var{@@_k} として
表示される. このとき, 例えば @var{23 = 2*3^2+3+2} は, 2*x^2+x+2
と表現され, これは結局 x^17 と法 x^5+2*x+1 で等しいので, 
@var{@@_17} と変換される. 
@item
@code{sfptop()} は @code{ptosfp()} の逆変換である. 
\E
\BEG
@item
@code{ptosfp()} converts coefficients of a polynomial to
elements in a small finite field GF(@var{p^n}) set as a ground field.
If a coefficient is already an element of the field, 
no conversion is done. If a coefficient is a positive integer,
then its residue modulo @var{p^n} is expanded as @var{p}-adic integer,
then @var{p} is substituted by @var{x}, finally the polynomial
is converted to its correspoding logarithmic representation 
with respect to the primitive element.
For example, GF(3^5) is represented as F(3)[@var{x}]/(@var{x^5+2*x+1}),
and each element of the field is represented as @var{@@_k} 
by its exponent @var{k} with respect to the primitive element @var{x}.
@var{23 = 2*3^2+3+2} is represented as @var{2*x^2+x+2} and
it is equivalent to @var{x^17} modulo @var{x^5+2*x+1}.
Therefore an integer @var{23} is conterted to @var{@@_17}.
@item
@code{sfptop()} is the inverse of @code{ptosfp()}.
\E
@end itemize

@example
[196] setmod_ff(3,5);
[3,x^5+2*x+1,x]
[197] A = ptosfp(23);
@@_17
[198] 9*2+3+2;
23
[199] x^17-(2*x^2+x+2); 
x^17-2*x^2-x-2
[200] sremm(@@,x^5+2*x+1,3);
0
[201] sfptop(A);
23
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{setmod_ff}, @fref{simp_ff}
@end table
\JP @node defpoly_mod2,,, 有限体に関する函数のまとめ
\EG @node defpoly_mod2,,, Functions for Finite fields
@subsection @code{defpoly_mod2}
@findex defpoly_mod2

@table @t
@item defpoly_mod2(@var{d})
\JP :: GF(2) 上既約な一変数多項式の生成
\EG :: Generates an irreducible univariate polynomial over GF(2).
@end table

@table @var
@item return
\JP 多項式
\EG univariate polynomial
@item d
\JP 正整数
\EG positive integer
@end table

@itemize @bullet
\BJP
@item
@samp{fff} で定義されている. 
@item
与えられた次数 @var{d} に対し, GF(2) 上 @var{d} 次の既約多項式を返す. 
@item
もし 既約 3 項式が存在すれば, 第 2 項の次数がもっとも小さい 3 項式, もし 既約 
3 項式が存在しなければ, 既約 5 項式の中で, 第 2 項の次数がもっとも小さく, 
その中で第 3 項の次数がもっとも小さく, その中で第 4 項の次数がもっとも
小さいものを返す. 
\E
\BEG
@item
Defined in @samp{fff}.
@item
An irreducible univariate polynomial of degree @var{d} is returned.
@item
If an irreducible trinomial @var{x^d+x^m+1} exists, then the one
with the smallest @var{m} is returned.
Otherwise, an irreducible pentanomial @var{x^d+x^m1+x^m2+x^m3+1} 
(@var{m1>m2>m3} is returned. 
@var{m1}, @var{m2} and @var{m3} are determined as follows:
Fix @var{m1} as small as possible. Then fix @var{m2} as small as possible.
Then fix @var{m3} as small as possible.
\E
@end itemize

@example
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node sffctr,,, 有限体に関する函数のまとめ
\EG @node sffctr,,, Functions for Finite fields
@subsection @code{sffctr}
@findex sffctr

@table @t
@item sffctr(@var{poly})
\JP :: 多項式の小標数有限体上での既約分解
\EG :: Irreducible factorization over a small finite field.
@end table

@table @var
@item return
\JP リスト
\EG list
@item poly
\JP 有限体上の 多項式
\EG polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
多項式を, 現在設定されている小標数有限体上で既約分解する. 
@item
結果は, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] なる
リストである. ここで, @var{fi} は monic な既約因子, @var{mi} はその
重複度である. 
\E
\BEG
@item
Factorize @var{poly} into irreducible factors over 
a small finite field currently set.
@item
The result is a list [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...],
where @var{fi} is a monic irreducible factor and @var{mi} is its
multiplicity.
\E
@end itemize

@example
[0] setmod_ff(2,10);
[2,x^10+x^3+1,x]
[1] sffctr((z*y^3+z*y)*x^3+(y^5+y^3+z*y^2+z)*x^2+z^11*y*x+z^10*y^3+z^11);
[[@@_0,1],[@@_0*z*y*x+@@_0*y^3+@@_0*z,1],[(@@_0*y+@@_0)*x+@@_0*z^5,2]]
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{setmod_ff},
@fref{modfctr}
@end table

\JP @node fctr_ff,,, 有限体に関する函数のまとめ
\EG @node fctr_ff,,, Functions for Finite fields
@subsection @code{fctr_ff}
@findex fctr_ff

@table @t
@item fctr_ff(@var{poly})
\JP :: 1 変数多項式の有限体上での既約分解
\EG :: Irreducible univariate factorization over a finite field.
@end table

@table @var
@item return
\JP リスト
\EG list
@item poly
\JP 有限体上の 1 変数多項式
\EG univariate polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
@samp{fff} で定義されている. 
@item
一変数多項式を, 現在設定されている有限体上で既約分解する. 
@item
結果は, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] なる
リストである. ここで, @var{fi} は monic な既約因子, @var{mi} はその
重複度である. 
@item
@var{poly} の主係数は捨てられる. 
\E
\BEG
@item
Defined in @samp{fff}.
@item
Factorize @var{poly} into irreducible factors over the current base field.
@item
The result is a list [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...],
where @var{fi} is a monic irreducible factor and @var{mi} is its
multiplicity.
@item
The leading coefficient of @var{poly} is abandoned.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node irredcheck_ff,,, 有限体に関する函数のまとめ
\EG @node irredcheck_ff,,, Functions for Finite fields
@subsection @code{irredcheck_ff}
@findex irredcheck_ff

@table @t
@item irredcheck_ff(@var{poly})
\JP :: 1 変数多項式の有限体上での既約判定
\EG :: Primality check of a univariate polynomial over a finite field.
@end table

@table @var
@item return
0|1
@item poly
\JP 有限体上の 1 変数多項式
\EG univariate polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
@samp{fff} で定義されている. 
@item
有限体上の 1 変数多項式の既約判定を行い, 既約の場合 1, それ以外は 0 を返す. 
\E
\BEG
@item
Defined in @samp{fff}.
@item
Returns 1 if @var{poly} is irreducible over the current base field.
Returns 0 otherwise.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table

\JP @node randpoly_ff,,, 有限体に関する函数のまとめ
\EG @node randpoly_ff,,, Functions for Finite fields
@subsection @code{randpoly_ff}
@findex randpoly_ff

@table @t
@item randpoly_ff(@var{d},@var{v})
\JP :: 有限体上の 乱数係数 1 変数多項式の生成
\EG :: Generation of a random univariate polynomial over a finite field.
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item d
\JP 正整数
\EG positive integer
@item v
\JP 不定元
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
@samp{fff} で定義されている. 
@item
@var{d} 次未満, 変数が @var{v}, 係数が現在設定されている有限体に属する
1 変数多項式を生成する. 係数は @code{random_ff()} により生成される. 
\E
\BEG
@item
Defined in @samp{fff}.
@item
Generates a polynomial of @var{v} such that the degree is less than @var{d}
and the coefficients are in the current base field.
The coefficients are generated by @code{random_ff()}.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}, @fref{random_ff}
@end table

\JP @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, 有限体に関する函数のまとめ
\EG @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, Functions for Finite fields
@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})
\JP :: 楕円曲線上の点の加算, 減算, 逆元
\EG :: Addition, Subtraction and additive inverse for points on an elliptic curve.
@end table

@table @var
@item return
\JP ベクトルまたは 0
\EG vector or 0
@item p1 p2
\JP 長さ 3 のベクトルまたは 0
\EG vector of length 3 or 0
@item ec
\JP 長さ 2 のベクトル        
\EG vector of length 2
@end table

@itemize @bullet
\BJP
@item
現在設定されている有限体上で,  @var{ec} で定義される楕円曲線上の
点 @var{p1}, @var{p2} の和 @var{p1+p2}, 差 @var{p1-p2}, 逆元 @var{-p1} を返す. 
@item
@var{ec} は, 設定されている有限体が奇標数素体の場合, 
y^2=x^3+ec[0]x+ec[1], 標数 2 の場合 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} が楕円曲線上の点かどうかのチェックはしない. 
\E
\BEG
@item
Let @var{p1}, @var{p2} be points on the elliptic curve represented by
@var{ec} over the current base field.
ecm_add_ff(@var{p1},@var{p2},@var{ec}), ecm_sub_ff(@var{p1},@var{p2},@var{ec})
and ecm_chsgn_ff(@var{p1}) returns
@var{p1+p2}, @var{p1-p2} and @var{-p1} respectively.
@item
If the current base field is a prime field of odd order, then
@var{ec} represents y^2=x^3+ec[0]x+ec[1].
If the characteristic of the current base field is 2,
then @var{ec} represents y^2+xy=x^3+ec[0]x^2+ec[1].
@item
The point at infinity is represented by 0.
@item
If an argument denoting a point is a vector of length 3,
then it is the projective coordinate. In such a case
the third coordinate must not be 0.
@item
If the result is a vector of length 3, then the third coordinate
is not equal to 0 but not necessarily 1. To get the result by
the affine coordinate, the first and the second coordinates should
be divided by the third coordinate.
@item
The check whether the arguments are on the curve is omitted.
\E
@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
\JP @item 参照
\EG @item References
@fref{setmod_ff}
@end table