Return to ff.texi CVS log

Up to [local] / OpenXM / src / asir-doc / parts

Added description on setmod_ff(defpoly,p).

@comment $OpenXM: OpenXM/src/asir-doc/parts/ff.texi,v 1.8 2005/09/08 07:40:49 noro Exp $
\BJP
@node $BM-8BBN$K4X$9$k1i;;(B,,, Top
@chapter $BM-8BBN$K4X$9$k1i;;(B
\E
\BEG
@node Finite fields,,, Top
@chapter Finite fields
\E

@menu
\BJP
* $BM-8BBN$NI=8=$*$h$S1i;;(B::
* $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
* $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B::
* $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B::
* $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B::
\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 $BM-8BBN$NI=8=$*$h$S1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $BM-8BBN$NI=8=$*$h$S1i;;(B
\E
\BEG
@node Representation of finite fields,,, Finite fields
@section Representation of finite fields
\E

@noindent
\BJP
@b{Asir} $B$K$*$$$F$O(B, $BM-8BBN$O(B, $B@5I8?tAGBN(B GF(@var{p}), $BI8?t(B 2 $B$NM-8BBN(B GF(2^@var{n}),
GF(@var{p}) $B$N(B @var{n} $B<!3HBg(B GF(@var{p^n})
$B$,Dj5A$G$-$k(B. $B$3$l$i$OA4$F(B, @code{setmod_ff()} $B$K$h$jDj5A$5$l$k(B. 
\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()} $B$O(B, $B$5$^$6$^$J%?%$%W$NM-8BBN$r4pACBN$H$7$F%;%C%H$9$k(B. 
$B0z?t$,@5@0?t(B @var{p} $B$N>l9g(B GF(@var{p}), @var{n} $B<!B?9`<0(B f(x) $B$N>l(B
$B9g(B, f(x) mod 2 $B$rDj5AB?9`<0$H$9$k(B GF(2^@var{n}) $B$r$=$l$>$l4pACBN$H$7$F%;%C%H$9(B
$B$k(B. $B$^$?(B, $BM-8BAGBN$NM-8B<!3HBg$bDj5A$G$-$k(B. $B>\$7$/$O(B @xref{$B?t$N7?(B}.
@code{setmod_ff()} $B$K$*$$$F$O0z?t$N4{Ls%A%'%C%/$O9T$o$:(B, $B8F$S=P$7B&(B
$B$,@UG$$r;}$D(B.

$B4pACBN$H$O(B, $B$"$/$^$GM-8BBN$N85$H$7$F@k8@$"$k$$$ODj5A$5$l$?%*%V%8%'%/%H$,(B, 
$B%;%C%H$5$l$?4pACBN$N1i;;$K=>$&$H$$$&0UL#$G$"$k(B. $BB($A(B, $BM-M}?t$I$&$7$N1i;;(B
$B$N7k2L$OM-M}?t$H$J$k(B. $BC"$7(B, $B;MB'1i;;$K$*$$$F0lJ}$N%*%Z%i%s%I$,M-8BBN$N85(B
$B$N>l9g$K$O(B, $BB>$N85$b<+F0E*$KF1$8M-8BBN$N85$H8+$J$5$l(B, $B1i;;7k2L$bF1MM$K$J(B
$B$k(B.

0 $B$G$J$$M-8BBN$N85$O(B, $B?t%*%V%8%'%/%H$G$"$j(B, $B<1JL;R$NCM$O(B 1 $B$G$"$k(B. 
$B$5$i$K(B, 0 $B$G$J$$M-8BBN$N85$N?t<1JL;R$O(B, GF(@var{p}) $B$N>l9g(B 6, GF(2^@var{n}) $B$N>l9g(B 7
$B$H$J$k(B. 

$BM-8BBN$N85$NF~NOJ}K!$O(B, $BM-8BBN$N<oN`$K$h$jMM!9$G$"$k(B. GF(@var{p}) $B$N>l9g(B, 
@code{simp_ff()} $B$K$h$k(B. 
\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 $B$^$?(B, GF(2^@var{n}) $B$N>l9g$$$/$D$+$NJ}K!$,$"$k(B. 
\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
$BM-8BBN$N85$O?t$G$"$j(B, $BBN1i;;$,2DG=$G$"$k(B. @code{@@} $B$O(B
GF(2^@var{n}) $B$N(B, GF(2) $B>e$N@8@.85$G$"$k(B. $B>\$7$/$O(B @xref{$B?t$N7?(B}.
\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 $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
\E
\BEG
@node Univariate polynomials on finite fields,,, Finite fields
@section Univariate polynomials on finite fields
\E

@noindent
\BJP
@samp{fff} $B$G$O(B, $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0$KBP$7(B, $BL5J?J}J,2r(B, DDF, $B0x?tJ,2r(B, 
$BB?9`<0$N4{LsH=Dj$J$I$N4X?t$,Dj5A$5$l$F$$$k(B. 

$B$$$:$l$b(B, $B7k2L$O(B [@b{$B0x;R(B}, @b{$B=EJ#EY(B}] $B$N%j%9%H$H$J$k$,(B, $B0x;R$O(B monic 
$B$H$J$j(B, $BF~NOB?9`<0$N<g78?t$O<N$F$i$l$k(B.
      
$BL5J?J}J,2r$O(B, $BB?9`<0$H$=$NHyJ,$H$N(B GCD $B$N7W;;$+$i;O$^$k$b$C$H$b0lHLE*$J(B
$B%"%k%4%j%:%`$r:NMQ$7$F$$$k(B. 

$BM-8BBN>e$G$N0x?tJ,2r$O(B, DDF $B$N8e(B, $B<!?tJL0x;R$NJ,2r$N:]$K(B, Berlekamp
$B%"%k%4%j%:%`$GNm6u4V$r5a$a(B, $B4pDl%Y%/%H%k$N:G>.B?9`<0$r5a$a(B, $B$=$N:,(B
$B$r(B Cantor-Zassenhaus $B%"%k%4%j%:%`$K$h$j5a$a$k(B, $B$H$$$&J}K!$r<BAu$7$F$$$k(B. 
\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 $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B
\E
\BEG
@node Polynomials on small finite fields,,, Finite fields
@section Polynomials on small finite fields
\E

\BJP
$B>.I8?tM-8BBN78?t$NB?9`<0$K8B$j(B, $BB?JQ?tB?9`<0$N0x?tJ,2r$,(B
$BAH$_9~$_4X?t$H$7$F<BAu$5$l$F$$$k(B. $B4X?t$O(B @code{sffctr()}
$B$G$"$k(B. $B$^$?(B, @code{modfctr()} $B$b(B, $BM-8BAGBN>e$GB?JQ?t(B
$BB?9`<0$N0x?tJ,2r$r9T$&$,(B, $B<B:]$K$O(B, $BFbIt$G==J,Bg$-$J(B
$B3HBgBN$r@_Dj$7(B, @code{sffctr()} $B$r8F$S=P$7$F(B, 
$B:G=*E*$KAGBN>e$N0x;R$r9=@.$9$k(B, $B$H$$$&J}K!$G7W;;$7$F$$$k(B. 
\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 $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B
\E
\BEG
@node Elliptic curves on finite fields,,, Finite fields
@section Elliptic curves on finite fields
\E

\BJP
$BM-8BBN>e$NBJ1_6J@~$K4X$9$k$$$/$D$+$N4pK\E*$J1i;;$,(B, $BAH$_9~$_4X?t$H$7$F(B
$BDs6!$5$l$F$$$k(B. 

$BBJ1_6J@~$N;XDj$O(B, $BD9$5(B 2 $B$N%Y%/%H%k(B [@var{a b}] $B$G9T$&(B. @var{a}, @var{b}
$B$OM-8BBN$N85$G(B, 
@code{setmod_ff} $B$GDj5A$5$l$F$$$kM-8BBN$,AGBN$N>l9g(B, @var{y^2=x^3+ax+b},
$BI8?t(B 2 $B$NBN$N>l9g(B @var{y^2+xy=x^3+ax^2+b} $B$rI=$9(B. 

$BBJ1_6J@~>e$NE@$O(B, $BL58B1sE@$b9~$a$F2CK!72$r$J$9(B. $B$3$N1i;;$K4X$7$F(B, $B2C;;(B 
(@code{ecm_add_ff()}), $B8:;;(B (@code{ecm_sub_ff()}) $B$*$h$S5U857W;;$N$?$a$N(B
$B4X?t(B (@code{ecm_chsgn_ff()}) $B$,Ds6!$5$l$F$$$k(B. $BCm0U$9$Y$-$O(B, $B1i;;$NBP>](B
$B$H$J$kE@$NI=8=$,(B,

@itemize @bullet
@item $BL58B1sE@$O(B 0.
@item $B$=$l0J30$NE@$O(B, $BD9$5(B 3 $B$N%Y%/%H%k(B [@var{x y z}]. $B$?$@$7(B, @var{z} $B$O(B
0 $B$G$J$$(B. 
@end itemize

$B$H$$$&E@$G$"$k(B. [@var{x y z}] $B$O@F<!:BI8$K$h$kI=8=$G$"$j(B, $B%"%U%#%s:BI8(B
$B$G$O(B [@var{x/z y/z}] $B$J$kE@$rI=$9(B. $B$h$C$F(B, $B%"%U%#%s:BI8(B [@var{x y}] $B$G(B
$BI=8=$5$l$?E@$r1i;;BP>]$H$9$k$K$O(B, [@var{x y 1}] $B$J$k%Y%/%H%k$r(B
$B@8@.$9$kI,MW$,$"$k(B. 
$B1i;;7k2L$b@F<!:BI8$GF@$i$l$k$,(B, @var{z} $B:BI8$,(B 1 $B$H$O8B$i$J$$$?$a(B, 
$B%"%U%#%s:BI8$r5a$a$k$?$a$K$O(B @var{x}, @var{y} $B:BI8$r(B @var{z} $B:BI8$G(B
$B3d$kI,MW$,$"$k(B. 
\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 $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $BM-8BBN$N@_Dj(B, $B@_Dj$5$l$F$$$kM-8BBN$NK!(B, $BDj5AB?9`<0$NI=<((B
\EG :: Sets/Gets the current base fields.
@end table

@table @var
@item return
\JP $B?t$^$?$OB?9`<0(B
\EG number or polynomial
@item p
\JP $BAG?t(B
\EG prime
@item defpoly2
\JP GF(2) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
\EG univariate polynomial irreducible over GF(2)
@item defpolyp
\JP GF(@var{p}) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
\EG univariate polynomial irreducible over GF(@var{p})
@item n
\JP $B3HBg<!?t(B
\EG the extension degree
@end table

@itemize @bullet
\BJP
@item
$B0z?t$,@5@0?t(B @var{p} $B$N;~(B, GF(@var{p}) $B$r4pACBN$H$7$F@_Dj$9$k(B. 
@item
$B0z?t$,B?9`<0(B @var{defpoly2} $B$N;~(B, 
GF(2^deg(@var{defpoly2} mod 2)) = GF(2)[t]/(@var{defpoly2}(t) mod 2)
$B$r4pACBN$H$7$F@_Dj$9$k(B.
@item
$B0z?t$,(B @var{defpolyp} $B$H(B @var{p} $B$N;~(B, 
GF(@var{p^deg(defpolyp)}) $B$r4pACBN$H$7$F@_Dj$9$k(B.
@item
$B0z?t$,(B @var{p} $B$H(B @var{n} $B$N;~(B, 
GF(@var{p^n}) $B$r4pACBN$H$7$F@_Dj$9$k(B. @var{p^n} $B$O(B @var{2^29} $BL$K~$G(B
$B$J$1$l$P$J$i$J$$(B. $B$^$?(B, @var{p} $B$,(B @var{2^14} $B0J>e$N$H$-(B, 
@var{n} $B$O(B 1 $B$G$J$1$l$P$J$i$J$$(B. 
@item
$BL50z?t$N;~(B, $B@_Dj$5$l$F$$$k4pACBN$,(B GF(@var{p})$B$N>l9g(B @var{p},
GF(2^@var{n}) $B$N>l9gDj5AB?9`<0$rJV$9(B. 
$B4pACBN$,(B @code{setmod_ff(@var{defpoly},@var{p})} $B$GDj5A$5$l$?(B
GF(@var{p}^@var{n}) $B$N>l9g(B, [@var{defpoly},@var{p}] $B$rJV$9(B.
$B4pACBN$,(B @code{setmod_ff(@var{p},@var{n})} $B$GDj5A$5$l$?(B
GF(p^@var{n}) $B$N>l9g(B,
[@var{p},@var{defpoly},@var{prim_elem}] $B$rJV$9(B. $B$3$3$G(B, @var{defpoly}
$B$O(B, @var{n} $B<!3HBg$NDj5AB?9`<0(B, @var{prim_elem} $B$O(B, GF(@var{p^n})$B$N(B
$B>hK!72$N@8@.85$r0UL#$9$k(B.
@item
GF(2^@var{n}) $B$NDj5AB?9`<0$O(B, GF(2) $B>e(B n $B<!4{Ls$J$i$J$s$G$bNI$$$,(B, $B8zN($K(B
$B1F6A$9$k$?$a(B, @code{defpoly_mod2()} $B$G@8@.$9$k$N$,$h$$(B. 
\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 $B;2>H(B
\EG @item References
@fref{defpoly_mod2}
@end table

\JP @node field_type_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $B@_Dj$5$l$F$$$k4pACBN$N<oN`(B
\EG :: Type of the current base field.
@end table

@table @var
@item return
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
$B@_Dj$5$l$F$$$k4pACBN$N<oN`$rJV$9(B. 
@item
$B@_Dj$J$7$J$i(B 0, GF(@var{p}) $B$J$i(B 1, GF(2^@var{n}) $B$J$i(B 2 $B$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node field_order_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B
\EG :: Order of the current base field.
@end table

@table @var
@item return
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
$B@_Dj$5$l$F$$$k4pACBN$N0L?t(B ($B85$N8D?t(B) $B$rJV$9(B. 
@item
$B@_Dj$5$l$F$$$kBN$,(B GF(@var{q}) $B$J$i$P(B q $B$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node characteristic_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node characteristic_ff,,, Functions for Finite fields
@subsection @code{characteristic_ff}
@findex characteristic_ff

@table @t
@item characteristic_ff()
\JP :: $B@_Dj$5$l$F$$$kBN$NI8?t(B
\EG :: Characteristic of the current base field.
@end table

@table @var
@item return
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
$B@_Dj$5$l$F$$$kBN$NI8?t$rJV$9(B. 
@item
GF(@var{p}) $B$N>l9g(B @var{p}, GF(2^@var{n}) $B$N>l9g(B 2 $B$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node extdeg_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node extdeg_ff,,, Functions for Finite fields
@subsection @code{extdeg_ff}
@findex extdeg_ff

@table @t
@item extdeg_ff()
\JP :: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t(B
\EG :: Extension degree of the current base field over the prime field.
@end table

@table @var
@item return
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
\BJP
@item
$B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t$rJV$9(B. 
@item
GF(@var{p}) $B$N>l9g(B 1, GF(2^@var{n}) $B$N>l9g(B @var{n} $B$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node simp_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node simp_ff,,, Functions for Finite fields
@subsection @code{simp_ff}
@findex simp_ff

@table @t
@item simp_ff(@var{obj})
\JP :: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49(B
\BEG
:: Converts numbers or coefficients of polynomials into elements
in finite fields.
\E
@end table

@table @var
@item return
\JP $B?t$^$?$OB?9`<0(B
\EG number or polynomial
@item obj
\JP $B?t$^$?$OB?9`<0(B
\EG number or polynomial
@end table

@itemize @bullet
\BJP
@item
$B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49$9$k(B. 
@item
$B@0?t(B, $B$"$k$$$O@0?t78?tB?9`<0$r(B, $BM-8BBN(B, $B$"$k$$$OM-8BBN78?t$KJQ49$9$k$?$a$K(B
$BMQ$$$k(B. 
@item
$BM-8BBN$N85$KBP$7(B, $BK!$"$k$$$ODj5AB?9`<0$K$h$k(B reduction $B$r9T$&>l9g$K$b(B
$BMQ$$$k(B. 
@item
$B>.I8?tM-8BBN$N85$KJQ49$9$k>l9g(B, $B0lC6AGBN>e$K<M1F$7$F$+$i(B, $B3HBgBN$N(B
$B85$KJQ49$5$l$k(B. $B3HBgBN$N85$KD>@\JQ49$9$k$K$O(B @code{ptosfp()} $B$r(B
$BMQ$$$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}, @fref{ptosfp sfptop}
@end table

\JP @node random_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node random_ff,,, Functions for Finite fields
@subsection @code{random_ff}
@findex random_ff

@table @t
@item random_ff()
\JP :: $BM-8BBN$N85$NMp?t@8@.(B
\EG :: Random generation of an element of a finite field.
@end table

@table @var
@item return
\JP $BM-8BBN$N85(B
\EG element of a finite field
@end table

@itemize @bullet
\BJP
@item
$BM-8BBN$N85$rMp?t@8@.$9$k(B. 
@item
@code{random()}, @code{lrandom()} $B$HF1$8(B 32bit $BMp?tH/@84o$r;HMQ$7$F$$$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}, @fref{random}, @fref{lrandom}
@end table

\JP @node lmptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node lmptop,,, Functions for Finite fields
@subsection @code{lmptop}
@findex lmptop

@table @t
@item lmptop(@var{obj})
\JP :: GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49(B
\EG :: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
@end table

@table @var
@item return
\JP $B@0?t78?tB?9`<0(B
\EG integral polynomial
@item obj
\JP GF(@var{p}) $B78?tB?9`<0(B
\EG polynomial over GF(@var{p})
@end table

@itemize @bullet
\BJP
@item
GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49$9$k(B. 
@item
GF(@var{p}) $B$N85$O(B, 0 $B0J>e(B p $BL$K~$N@0?t$GI=8=$5$l$F$$$k(B. 
$BB?9`<0$N3F78?t$O(B, $B$=$NCM$r@0?t%*%V%8%'%/%H(B($B?t<1JL;R(B 0)$B$H$7$?$b$N$K(B
$BJQ49$5$l$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{simp_ff}
@end table

\JP @node ntogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node ntogf2n,,, Functions for Finite fields
@subsection @code{ntogf2n}
@findex ntogf2n

@table @t
@item ntogf2n(@var{m})
\JP :: $B<+A3?t$r(B GF(2^@var{n}) $B$N85$KJQ49(B
\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}) $B$N85(B
\EG element of GF(2^@var{n})
@item m
\JP $BHsIi@0?t(B
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
$B<+A3?t(B @var{m} $B$N(B 2 $B?JI=8=(B @var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k
$B$KBP$7(B, GF(2^@var{n})=GF(2)[t]/(g(t)) $B$N85(B 
@var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) $B$rJV$9(B. 
@item
$BDj5AB?9`<0$K$h$k>jM>$O<+F0E*$K$O7W;;$5$l$J$$$?$a(B, @code{simp_ff()} $B$r(B
$BE,MQ$9$kI,MW$,$"$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{gf2nton}
@end table

\JP @node gf2nton,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node gf2nton,,, Functions for Finite fields
@subsection @code{gf2nton}
@findex gf2nton

@table @t
@item gf2nton(@var{m})
\JP :: GF(2^@var{n}) $B$N85$r<+A3?t$KJQ49(B
\EG :: Converts an element of GF(2^@var{n}) into a non-negative integer.
@end table

@table @var
@item return
\JP $BHsIi@0?t(B
\EG non-negative integer
@item m
\JP GF(2^@var{n}) $B$N85(B
\EG element of GF(2^@var{n})
@end table

@itemize @bullet
@item
\JP @code{gf2nton} $B$N5UJQ49$G$"$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{gf2nton}
@end table

\JP @node ptogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node ptogf2n,,, Functions for Finite fields
@subsection @code{ptogf2n}
@findex ptogf2n

@table @t
@item ptogf2n(@var{poly})
\JP :: $B0lJQ?tB?9`<0$r(B GF(2^@var{n}) $B$N85$KJQ49(B
\EG :: Converts a univariate polynomial into an element of GF(2^@var{n}).
@end table

@table @var
@item return
\JP GF(2^@var{n}) $B$N85(B
\EG element of GF(2^@var{n})
@item poly
\JP $B0lJQ?tB?9`<0(B
\EG univariate polynomial
@end table

@itemize @bullet
@item
\BJP
@var{poly} $B$NI=$9(B GF(2^@var{n}) $B$N85$r@8@.$9$k(B. $B78?t$O(B, 2 $B$G3d$C$?M>$j$K(B
$BJQ49$5$l$k(B. 
@var{poly} $B$NJQ?t$K(B @code{@@} $B$rBeF~$7$?7k2L$HEy$7$$(B. 
\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 $B;2>H(B
\EG @item References
@fref{gf2ntop}
@end table

\JP @node gf2ntop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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}) $B$N85$rB?9`<0$KJQ49(B
\EG :: Converts an element of GF(2^@var{n}) into a polynomial.
@end table

@table @var
@item return
\JP $B0lJQ?tB?9`<0(B
\EG univariate polynomial
@item m
\JP GF(2^@var{n}) $B$N85(B
\EG an element of GF(2^@var{n})
@item v
\JP $BITDj85(B
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
@var{m} $B$rI=$9B?9`<0$r(B, $B@0?t78?t$NB?9`<0%*%V%8%'%/%H$H$7$FJV$9(B. 
@item
@var{v} $B$N;XDj$,$J$$>l9g(B, $BD>A0$N(B @code{ptogf2n()} $B8F$S=P$7(B
$B$K$*$1$k0z?t$NJQ?t(B ($B%G%U%)%k%H$O(B @code{x}), $B;XDj$,$"$k>l9g$K$O(B
$B;XDj$5$l$?ITDj85$rJQ?t$H$9$kB?9`<0$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{ptogf2n}
@end table

\JP @node ptosfp sfptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $B>.I8?tM-8BBN$X$NJQ49(B, $B5UJQ49(B
\EG :: Transformation to/from a small finite field
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item p
\JP $BB?9`<0(B
\EG polynomial
@end table

@itemize @bullet
\BJP
@item
@code{ptosfp()} $B$O(B, $BB?9`<0$N78?t$r(B, $B8=:_@_Dj$5$l$F$$$k>.I8?tM-8BBN(B
GF(p^@var{n}) $B$N85$KD>@\JQ49$9$k(B. $B78?t$,4{$KM-8BBN$N85$N>l9g$OJQ2=$7$J$$(B. 
$B@5@0?t$N>l9g(B, $B$^$:0L?t$G>jM>$r7W;;$7$?$"$H(B, $BI8?t(B @var{p} $B$K$h$j(B @var{p}
$B?JE83+$7(B, @var{p} $B$r(B x $B$KCV$-49$($?B?9`<0$r(B, $B86;O85I=8=$KJQ49$9$k(B. 
$BNc$($P(B, GF(3^5) $B$O(B GF(3)[x]/(x^5+2*x+1) $B$H$7$FI=8=$5$l(B, $B$=$N3F(B
$B85$O86;O85(B x $B$K4X$9$k$Y$-;X?t(B @var{k} $B$K$h$j(B @var{@@_k} $B$H$7$F(B
$BI=<($5$l$k(B. $B$3$N$H$-(B, $BNc$($P(B @var{23 = 2*3^2+3+2} $B$O(B, 2*x^2+x+2
$B$HI=8=$5$l(B, $B$3$l$O7k6I(B x^17 $B$HK!(B x^5+2*x+1 $B$GEy$7$$$N$G(B, 
@var{@@_17} $B$HJQ49$5$l$k(B. 
@item
@code{sfptop()} $B$O(B @code{ptosfp()} $B$N5UJQ49$G$"$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}, @fref{simp_ff}
@end table
\JP @node defpoly_mod2,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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) $B>e4{Ls$J0lJQ?tB?9`<0$N@8@.(B
\EG :: Generates an irreducible univariate polynomial over GF(2).
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG univariate polynomial
@item d
\JP $B@5@0?t(B
\EG positive integer
@end table

@itemize @bullet
\BJP
@item
@samp{fff} $B$GDj5A$5$l$F$$$k(B. 
@item
$BM?$($i$l$?<!?t(B @var{d} $B$KBP$7(B, GF(2) $B>e(B @var{d} $B<!$N4{LsB?9`<0$rJV$9(B. 
@item
$B$b$7(B $B4{Ls(B 3 $B9`<0$,B8:_$9$l$P(B, $BBh(B 2 $B9`$N<!?t$,$b$C$H$b>.$5$$(B 3 $B9`<0(B, $B$b$7(B $B4{Ls(B 
3 $B9`<0$,B8:_$7$J$1$l$P(B, $B4{Ls(B 5 $B9`<0$NCf$G(B, $BBh(B 2 $B9`$N<!?t$,$b$C$H$b>.$5$/(B, 
$B$=$NCf$GBh(B 3 $B9`$N<!?t$,$b$C$H$b>.$5$/(B, $B$=$NCf$GBh(B 4 $B9`$N<!?t$,$b$C$H$b(B
$B>.$5$$$b$N$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node sffctr,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node sffctr,,, Functions for Finite fields
@subsection @code{sffctr}
@findex sffctr

@table @t
@item sffctr(@var{poly})
\JP :: $BB?9`<0$N>.I8?tM-8BBN>e$G$N4{LsJ,2r(B
\EG :: Irreducible factorization over a small finite field.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BM-8BBN>e$N(B $BB?9`<0(B
\EG polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
$BB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$k>.I8?tM-8BBN>e$G4{LsJ,2r$9$k(B. 
@item
$B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
$B%j%9%H$G$"$k(B. $B$3$3$G(B, @var{fi} $B$O(B monic $B$J4{Ls0x;R(B, @var{mi} $B$O$=$N(B
$B=EJ#EY$G$"$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff},
@fref{modfctr}
@end table

\JP @node fctr_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node fctr_ff,,, Functions for Finite fields
@subsection @code{fctr_ff}
@findex fctr_ff

@table @t
@item fctr_ff(@var{poly})
\JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsJ,2r(B
\EG :: Irreducible univariate factorization over a finite field.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
\EG univariate polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
@samp{fff} $B$GDj5A$5$l$F$$$k(B. 
@item
$B0lJQ?tB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G4{LsJ,2r$9$k(B. 
@item
$B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
$B%j%9%H$G$"$k(B. $B$3$3$G(B, @var{fi} $B$O(B monic $B$J4{Ls0x;R(B, @var{mi} $B$O$=$N(B
$B=EJ#EY$G$"$k(B. 
@item
@var{poly} $B$N<g78?t$O<N$F$i$l$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node irredcheck_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\EG @node irredcheck_ff,,, Functions for Finite fields
@subsection @code{irredcheck_ff}
@findex irredcheck_ff

@table @t
@item irredcheck_ff(@var{poly})
\JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsH=Dj(B
\EG :: Primality check of a univariate polynomial over a finite field.
@end table

@table @var
@item return
0|1
@item poly
\JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
\EG univariate polynomial over a finite field
@end table

@itemize @bullet
\BJP
@item
@samp{fff} $B$GDj5A$5$l$F$$$k(B. 
@item
$BM-8BBN>e$N(B 1 $BJQ?tB?9`<0$N4{LsH=Dj$r9T$$(B, $B4{Ls$N>l9g(B 1, $B$=$l0J30$O(B 0 $B$rJV$9(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table

\JP @node randpoly_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $BM-8BBN>e$N(B $BMp?t78?t(B 1 $BJQ?tB?9`<0$N@8@.(B
\EG :: Generation of a random univariate polynomial over a finite field.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item d
\JP $B@5@0?t(B
\EG positive integer
@item v
\JP $BITDj85(B
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
@samp{fff} $B$GDj5A$5$l$F$$$k(B. 
@item
@var{d} $B<!L$K~(B, $BJQ?t$,(B @var{v}, $B78?t$,8=:_@_Dj$5$l$F$$$kM-8BBN$KB0$9$k(B
1 $BJQ?tB?9`<0$r@8@.$9$k(B. $B78?t$O(B @code{random_ff()} $B$K$h$j@8@.$5$l$k(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}, @fref{random_ff}
@end table

\JP @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
\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 :: $BBJ1_6J@~>e$NE@$N2C;;(B, $B8:;;(B, $B5U85(B
\EG :: Addition, Subtraction and additive inverse for points on an elliptic curve.
@end table

@table @var
@item return
\JP $B%Y%/%H%k$^$?$O(B 0
\EG vector or 0
@item p1 p2
\JP $BD9$5(B 3 $B$N%Y%/%H%k$^$?$O(B 0
\EG vector of length 3 or 0
@item ec
\JP $BD9$5(B 2 $B$N%Y%/%H%k(B        
\EG vector of length 2
@end table

@itemize @bullet
\BJP
@item
$B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G(B,  @var{ec} $B$GDj5A$5$l$kBJ1_6J@~>e$N(B
$BE@(B @var{p1}, @var{p2} $B$NOB(B @var{p1+p2}, $B:9(B @var{p1-p2}, $B5U85(B @var{-p1} $B$rJV$9(B. 
@item
@var{ec} $B$O(B, $B@_Dj$5$l$F$$$kM-8BBN$,4qI8?tAGBN$N>l9g(B, 
y^2=x^3+ec[0]x+ec[1], $BI8?t(B 2 $B$N>l9g(B y^2+xy=x^3+ec[0]x^2+ec[1] 
$B$rI=$9(B. 
@item
$B0z?t(B, $B7k2L$H$b$K(B, $BL58B1sE@$O(B 0 $B$GI=$5$l$k(B. 
@item
@var{p1}, @var{p2} $B$,D9$5(B 3 $B$N%Y%/%H%k$N>l9g(B, $B@F<!:BI8$K$h$k6J@~>e$N(B
$BE@$rI=$9(B. $B$3$N>l9g(B, $BBh(B 3 $B:BI8$O(B 0 $B$G$"$C$F$O$$$1$J$$(B. 
@item
$B7k2L$,D9$5(B 3 $B$N%Y%/%H%k$N>l9g(B, $BBh(B 3 $B:BI8$O(B 0 $B$G$J$$$,(B, 1 $B$H$O8B$i$J$$(B. 
$B%"%U%#%s:BI8$K$h$k7k2L$rF@$k$?$a$K$O(B, $BBh(B 1 $B:BI8(B, $BBh(B 2 $B:BI8$rBh(B 3 $B:BI8(B
$B$G3d$kI,MW$,$"$k(B. 
@item
@var{p1}, @var{p2} $B$,BJ1_6J@~>e$NE@$+$I$&$+$N%A%'%C%/$O$7$J$$(B. 
\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 $B;2>H(B
\EG @item References
@fref{setmod_ff}
@end table