Return to ff.texi CVS log

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

Imported OpenXM/src/asir-doc. 

@node $BM-8BBN$K4X$9$k1i;;(B,,, Top
@chapter $BM-8BBN$K4X$9$k1i;;(B

@menu
* $BM-8BBN$NI=8=$*$h$S1i;;(B::
* $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
* $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B::
* $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B::
@end menu

@node $BM-8BBN$NI=8=$*$h$S1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
@section $BM-8BBN$NI=8=$*$h$S1i;;(B

@noindent
@b{Asir} $B$K$*$$$F$O(B, $BM-8BBN$O(B, $B@5I8?tAGBN(B GF(p), $BI8?t(B 2 $B$NM-8BBN(B GF(2^n)
$B$,Dj5A$G$-$k(B. $B$3$l$i$OA4$F(B, @code{setmod_ff()} $B$K$h$jDj5A$5$l$k(B. 

@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()} $B$O(B, $B0z?t$,@5@0?t(B p $B$N>l9g(B GF(p), 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^n) $B$r$=$l$>$l4pACBN$H$7$F%;%C%H$9(B
$B$k(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(p) $B$N>l9g(B 6, GF(2^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(p) $B$N>l9g(B, 
@code{simp_ff()} $B$K$h$k(B. 

@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

$B$^$?(B, GF(2^n) $B$N>l9g$$$/$D$+$NJ}K!$,$"$k(B. 
@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

$BM-8BBN$N85$O?t$G$"$j(B, $BBN1i;;$,2DG=$G$"$k(B. @code{@@} $B$O(B
GF(2^n) $B$N(B, GF(2)$B>e$N@8@.85$G$"$k(B. $B>\$7$/$O(B @xref{$B?t$N7?(B}.

@noindent

@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

@noindent
@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.
      
@noindent
$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. 

@example
@end example

@noindent
$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. 

@example
@end example

@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

$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. 

@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

@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,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{setmod_ff}
@findex setmod_ff

@table @t
@item setmod_ff([@var{prime}|@var{poly}])
:: $BM-8BBN$N@_Dj(B, $B@_Dj$5$l$F$$$kM-8BBN$NK!(B, $BDj5AB?9`<0$NI=<((B
@end table

@table @var
@item return
$B?t$^$?$OB?9`<0(B
@item prime
$BAG?t(B
@item poly
GF(2) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
@end table

@itemize @bullet
@item
$B0z?t$,@5@0?t(B @var{prime} $B$N;~(B, GF(@var{prime}) $B$r4pACBN$H$7$F@_Dj$9$k(B. 
@item
$B0z?t$,B?9`<0(B @var{poly} $B$N;~(B, 
GF(2^deg(@var{poly} mod 2)) = GF(2)[t]/(@var{poly}(t) mod2)
$B$r4pACBN$H$7$F@_Dj$9$k(B.
@item
$BL50z?t$N;~(B, $B@_Dj$5$l$F$$$k4pACBN$,(B GF(@var{prime}) $B$N>l9g(B @var{prime},
GF(2^n) $B$N>l9gDj5AB?9`<0$rJV$9(B. 
@item
GF(2^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. 
@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 $B;2>H(B
@fref{defpoly_mod2}
@end table

@node field_type_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{field_type_ff}
@findex field_type_ff

@table @t
@item field_type_ff()
:: $B@_Dj$5$l$F$$$k4pACBN$N<oN`(B
@end table

@table @var
@item return
$B?t(B
@end table

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

@node field_order_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{field_order_ff}
@findex field_order_ff

@table @t
@item field_order_ff()
:: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B
@end table

@table @var
@item return
$B?t(B
@end table

@itemize @bullet
@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(q) $B$J$i$P(B q $B$rJV$9(B. 
@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 $B;2>H(B
@fref{setmod_ff}
@end table

@node characteristic_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{characteristic_ff}
@findex characteristic_ff

@table @t
@item characteristic_ff()
:: $B@_Dj$5$l$F$$$kBN$NI8?t(B
@end table

@table @var
@item return
$B?t(B
@end table

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

@node extdeg_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{extdeg_ff}
@findex extdeg_ff

@table @t
@item extdeg_ff()
:: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t(B
@end table

@table @var
@item return
$B?t(B
@end table

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

@node simp_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{simp_ff}
@findex simp_ff

@table @t
@item simp_ff(@var{obj})
:: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49(B
@end table

@table @var
@item return
$B?t$^$?$OB?9`<0(B
@item obj
$B?t$^$?$OB?9`<0(B
@end table

@itemize @bullet
@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. 
@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 $B;2>H(B
@fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}
@end table

@node random_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{random_ff}
@findex random_ff

@table @t
@item random_ff()
:: $BM-8BBN$N85$NMp?t@8@.(B
@end table

@table @var
@item return
$BM-8BBN$N85(B
@end table

@itemize @bullet
@item
$BM-8BBN$N85$rMp?t@8@.$9$k(B. 
@item
GF(p) $B$N>l9g(B, 0 $B0J>e(B p $BL$K~$N@0?t$G$"$i$o$5$l$k(B GF(p) $B$N85(B, 
GF(2^n) $B$N>l9g(B, n $B<!L$K~$N(B GF(2) $B>e$NB?9`<0$GI=$5$l$k(B GF(2^n) $B$r(B
$BJV$9(B. 
@item
@code{random()}, @code{lrandom()} $B$HF1$8(B 32bit $BMp?tH/@84o$r;HMQ$7$F$$$k(B. 
@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 $B;2>H(B
@fref{setmod_ff}, @fref{random}, @fref{lrandom}
@end table

@node lmptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{lmptop}
@findex lmptop

@table @t
@item lmptop(@var{obj})
:: GF(p) $B78?tB?9`<0$N78?t$r@0?t$KJQ49(B
@end table

@table @var
@item return
$B@0?t78?tB?9`<0(B
@item obj
GF(p)$B78?tB?9`<0(B
@end table

@itemize @bullet
@item
GF(p) $B78?tB?9`<0$N78?t$r@0?t$KJQ49$9$k(B. 
@item
GF(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. 
@item
GF(p) $B$N85$O(B, $B@0?t$KJQ49$5$l$k(B. 
@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 $B;2>H(B
@fref{simp_ff}
@end table

@node ntogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{ntogf2n}
@findex ntogf2n

@table @t
@item ntogf2n(@var{m})
:: $B<+A3?t$r(B GF(2^n) $B$N85$KJQ49(B
@end table

@table @var
@item return
GF(2^n) $B$N85(B
@item m
$BHsIi@0?t(B
@end table

@itemize @bullet
@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^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. 
@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 $B;2>H(B
@fref{gf2nton}
@end table

@node gf2nton,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{gf2nton}
@findex gf2nton

@table @t
@item gf2nton(@var{m})
:: GF(2^n) $B$N85$r<+A3?t$KJQ49(B
@end table

@table @var
@item return
$BHsIi@0?t(B
@item m
GF(2^n) $B$N85(B
@end table

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

@node ptogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{ptogf2n}
@findex ptogf2n

@table @t
@item ptogf2n(@var{poly})
:: $B0lJQ?tB?9`<0$r(B GF(2^n) $B$N85$KJQ49(B
@end table

@table @var
@item return
GF(2^n) $B$N85(B
@item poly
$B0lJQ?tB?9`<0(B
@end table

@itemize @bullet
@item
@var{poly} $B$NI=$9(B GF(2^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. 
@end itemize

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

@table @t
@item $B;2>H(B
@fref{gf2ntop}
@end table

@node gf2ntop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{gf2ntop}
@findex gf2ntop

@table @t
@item gf2ntop(@var{m}[,@var{v}])
:: GF(2^n) $B$N85$rB?9`<0$KJQ49(B
@end table

@table @var
@item return
$B0lJQ?tB?9`<0(B
@item m
GF(2^n) $B$N85(B
@item v
$BITDj85(B
@end table

@itemize @bullet
@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. 
@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 $B;2>H(B
@fref{ptogf2n}
@end table

@node defpoly_mod2,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{defpoly_mod2}
@findex defpoly_mod2

@table @t
@item defpoly_mod2(@var{d})
:: GF(2) $B>e4{Ls$J0lJQ?tB?9`<0$N@8@.(B
@end table

@table @var
@item return
$BB?9`<0(B
@item d
$B@5@0?t(B
@end table

@itemize @bullet
@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. 
@end itemize

@example
@end example

@table @t
@item $B;2>H(B
@fref{setmod_ff}
@end table

@node fctr_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{fctr_ff}
@findex fctr_ff

@table @t
@item fctr_ff(@var{poly})
:: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsJ,2r(B
@end table

@table @var
@item return
$B%j%9%H(B
@item poly
$BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
@end table

@itemize @bullet
@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. 
@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 $B;2>H(B
@fref{setmod_ff}
@end table

@node irredcheck_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{irredcheck_ff}
@findex irredcheck_ff

@table @t
@item irredcheck_ff(@var{poly})
:: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsH=Dj(B
@end table

@table @var
@item return
0|1
@item poly
$BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
@end table

@itemize @bullet
@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. 
@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 $B;2>H(B
@fref{setmod_ff}
@end table

@node randpoly_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@subsection @code{randpoly_ff}
@findex randpoly_ff

@table @t
@item randpoly_ff(@var{d},@var{v})
:: $BM-8BBN>e$N(B $BMp?t78?t(B 1 $BJQ?tB?9`<0$N@8@.(B
@end table

@table @var
@item return
$BB?9`<0(B
@item d
$B@5@0?t(B
@item v
$BITDj85(B
@end table

@itemize @bullet
@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. 
@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 $B;2>H(B
@fref{setmod_ff}, @fref{random_ff}
@end table

@node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
@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})
:: $BBJ1_6J@~>e$NE@$N2C;;(B, $B8:;;(B, $B5U85(B
@end table

@table @var
@item return
$B%Y%/%H%k$^$?$O(B 0
@item p1,p2
$BD9$5(B 3 $B$N%Y%/%H%k$^$?$O(B 0
@item ec
$BD9$5(B 2 $B$N%Y%/%H%k(B        
@end table

@itemize @bullet
@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, 
@var{y^2=x^3+ec[0]x+ec[1]}, $BI8?t(B 2 $B$N>l9g(B @var{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. 
@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 $B;2>H(B
@fref{setmod_ff}
@end table