Return to ff.texi CVS log

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

Annotation of OpenXM/src/asir-doc/parts/ff.texi, Revision 1.1

1.1     ! noro        1: @node $BM-8BBN$K4X$9$k1i;;(B,,, Top
        !             2: @chapter $BM-8BBN$K4X$9$k1i;;(B
        !             3:
        !             4: @menu
        !             5: * $BM-8BBN$NI=8=$*$h$S1i;;(B::
        !             6: * $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
        !             7: * $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B::
        !             8: * $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B::
        !             9: @end menu
        !            10:
        !            11: @node $BM-8BBN$NI=8=$*$h$S1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
        !            12: @section $BM-8BBN$NI=8=$*$h$S1i;;(B
        !            13:
        !            14: @noindent
        !            15: @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)
        !            16: $B$,Dj5A$G$-$k(B. $B$3$l$i$OA4$F(B, @code{setmod_ff()} $B$K$h$jDj5A$5$l$k(B.
        !            17:
        !            18: @example
        !            19: [0] P=pari(nextprime,2^50);
        !            20: 1125899906842679
        !            21: [1] setmod_ff(P);
        !            22: 1125899906842679
        !            23: [2] field_type_ff();
        !            24: 1
        !            25: [3] load("fff");
        !            26: 1
        !            27: [4] F=defpoly_mod2(50);
        !            28: x^50+x^4+x^3+x^2+1
        !            29: [5] setmod_ff(F);
        !            30: x^50+x^4+x^3+x^2+1
        !            31: [6] field_type_ff();
        !            32: 2
        !            33: @end example
        !            34: @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
        !            35: $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
        !            36: $B$k(B. @code{setmod_ff()} $B$K$*$$$F$O0z?t$N4{Ls%A%'%C%/$O9T$o$:(B, $B8F$S=P$7B&(B
        !            37: $B$,@UG$$r;}$D(B.
        !            38:
        !            39: $B4pACBN$H$O(B, $B$"$/$^$GM-8BBN$N85$H$7$F@k8@$"$k$$$ODj5A$5$l$?%*%V%8%'%/%H$,(B,
        !            40: $B%;%C%H$5$l$?4pACBN$N1i;;$K=>$&$H$$$&0UL#$G$"$k(B. $BB($A(B, $BM-M}?t$I$&$7$N1i;;(B
        !            41: $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
        !            42: $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
        !            43: $B$k(B.
        !            44:
        !            45: 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.
        !            46: $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
        !            47: $B$H$J$k(B.
        !            48:
        !            49: $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,
        !            50: @code{simp_ff()} $B$K$h$k(B.
        !            51:
        !            52: @example
        !            53: [0] P=pari(nextprime,2^50);
        !            54: 1125899906842679
        !            55: [1] setmod_ff(P);
        !            56: 1125899906842679
        !            57: [2] A=simp_ff(2^100);
        !            58: 3025
        !            59: [3] ntype(@@@@);
        !            60: 6
        !            61: @end example
        !            62:
        !            63: $B$^$?(B, GF(2^n) $B$N>l9g$$$/$D$+$NJ}K!$,$"$k(B.
        !            64: @example
        !            65: [0] setmod_ff(x^50+x^4+x^3+x^2+1);
        !            66: x^50+x^4+x^3+x^2+1
        !            67: [1] A=@@;
        !            68: (@@)
        !            69: [2] ptogf2n(x^50+1);
        !            70: (@@^50+1)
        !            71: [3] simp_ff(@@@@);
        !            72: (@@^4+@@^3+@@^2)
        !            73: [4] ntogf2n(2^10-1);
        !            74: (@@^9+@@^8+@@^7+@@^6+@@^5+@@^4+@@^3+@@^2+@@+1)
        !            75: @end example
        !            76:
        !            77: $BM-8BBN$N85$O?t$G$"$j(B, $BBN1i;;$,2DG=$G$"$k(B. @code{@@} $B$O(B
        !            78: 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}.
        !            79:
        !            80: @noindent
        !            81:
        !            82: @node $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
        !            83: @section $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
        !            84:
        !            85: @noindent
        !            86: @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,
        !            87: $BB?9`<0$N4{LsH=Dj$J$I$N4X?t$,Dj5A$5$l$F$$$k(B.
        !            88:
        !            89: $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
        !            90: $B$H$J$j(B, $BF~NOB?9`<0$N<g78?t$O<N$F$i$l$k(B.
        !            91:
        !            92: @noindent
        !            93: $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
        !            94: $B%"%k%4%j%:%`$r:NMQ$7$F$$$k(B.
        !            95:
        !            96: @example
        !            97: @end example
        !            98:
        !            99: @noindent
        !           100: $BM-8BBN>e$G$N0x?tJ,2r$O(B, DDF $B$N8e(B, $B<!?tJL0x;R$NJ,2r$N:]$K(B, Berlekamp
        !           101: $B%"%k%4%j%:%`$GNm6u4V$r5a$a(B, $B4pDl%Y%/%H%k$N:G>.B?9`<0$r5a$a(B, $B$=$N:,(B
        !           102: $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.
        !           103:
        !           104: @example
        !           105: @end example
        !           106:
        !           107: @node $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
        !           108: @section $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B
        !           109:
        !           110: $BM-8BBN>e$NBJ1_6J@~$K4X$9$k$$$/$D$+$N4pK\E*$J1i;;$,(B, $BAH$_9~$_4X?t$H$7$F(B
        !           111: $BDs6!$5$l$F$$$k(B.
        !           112:
        !           113: $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}
        !           114: $B$OM-8BBN$N85$G(B,
        !           115: @code{setmod_ff} $B$GDj5A$5$l$F$$$kM-8BBN$,AGBN$N>l9g(B, @var{y^2=x^3+ax+b},
        !           116: $BI8?t(B 2 $B$NBN$N>l9g(B @var{y^2+xy=x^3+ax^2+b} $B$rI=$9(B.
        !           117:
        !           118: $BBJ1_6J@~>e$NE@$O(B, $BL58B1sE@$b9~$a$F2CK!72$r$J$9(B. $B$3$N1i;;$K4X$7$F(B, $B2C;;(B
        !           119: (@code{ecm_add_ff()}), $B8:;;(B (@code{ecm_sub_ff()}) $B$*$h$S5U857W;;$N$?$a$N(B
        !           120: $B4X?t(B (@code{ecm_chsgn_ff()}) $B$,Ds6!$5$l$F$$$k(B. $BCm0U$9$Y$-$O(B, $B1i;;$NBP>](B
        !           121: $B$H$J$kE@$NI=8=$,(B,
        !           122:
        !           123: @itemize @bullet
        !           124: @item $BL58B1sE@$O(B 0.
        !           125: @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
        !           126: 0 $B$G$J$$(B.
        !           127: @end itemize
        !           128:
        !           129: $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
        !           130: $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
        !           131: $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
        !           132: $B@8@.$9$kI,MW$,$"$k(B.
        !           133: $B1i;;7k2L$b@F<!:BI8$GF@$i$l$k$,(B, @var{z} $B:BI8$,(B 1 $B$H$O8B$i$J$$$?$a(B,
        !           134: $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
        !           135: $B3d$kI,MW$,$"$k(B.
        !           136:
        !           137: @node $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B,,, $BM-8BBN$K4X$9$k1i;;(B
        !           138: @section $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           139:
        !           140: @menu
        !           141: * setmod_ff::
        !           142: * field_type_ff::
        !           143: * field_order_ff::
        !           144: * characteristic_ff::
        !           145: * extdeg_ff::
        !           146: * simp_ff::
        !           147: * random_ff::
        !           148: * lmptop::
        !           149: * ntogf2n::
        !           150: * gf2nton::
        !           151: * ptogf2n::
        !           152: * gf2ntop::
        !           153: * defpoly_mod2::
        !           154: * fctr_ff::
        !           155: * irredcheck_ff::
        !           156: * randpoly_ff::
        !           157: * ecm_add_ff ecm_sub_ff ecm_chsgn_ff::
        !           158: * extdeg_ff::
        !           159: @end menu
        !           160:
        !           161: @node setmod_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           162: @subsection @code{setmod_ff}
        !           163: @findex setmod_ff
        !           164:
        !           165: @table @t
        !           166: @item setmod_ff([@var{prime}|@var{poly}])
        !           167: :: $BM-8BBN$N@_Dj(B, $B@_Dj$5$l$F$$$kM-8BBN$NK!(B, $BDj5AB?9`<0$NI=<((B
        !           168: @end table
        !           169:
        !           170: @table @var
        !           171: @item return
        !           172: $B?t$^$?$OB?9`<0(B
        !           173: @item prime
        !           174: $BAG?t(B
        !           175: @item poly
        !           176: GF(2) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
        !           177: @end table
        !           178:
        !           179: @itemize @bullet
        !           180: @item
        !           181: $B0z?t$,@5@0?t(B @var{prime} $B$N;~(B, GF(@var{prime}) $B$r4pACBN$H$7$F@_Dj$9$k(B.
        !           182: @item
        !           183: $B0z?t$,B?9`<0(B @var{poly} $B$N;~(B,
        !           184: GF(2^deg(@var{poly} mod 2)) = GF(2)[t]/(@var{poly}(t) mod2)
        !           185: $B$r4pACBN$H$7$F@_Dj$9$k(B.
        !           186: @item
        !           187: $BL50z?t$N;~(B, $B@_Dj$5$l$F$$$k4pACBN$,(B GF(@var{prime}) $B$N>l9g(B @var{prime},
        !           188: GF(2^n) $B$N>l9gDj5AB?9`<0$rJV$9(B.
        !           189: @item
        !           190: 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
        !           191: $B1F6A$9$k$?$a(B, @code{defpoly_mod2()} $B$G@8@.$9$k$N$,$h$$(B.
        !           192: @end itemize
        !           193:
        !           194: @example
        !           195: [174] defpoly_mod2(100);
        !           196: x^100+x^15+1
        !           197: [175] setmod_ff(@@@@);
        !           198: x^100+x^15+1
        !           199: [176] setmod_ff();
        !           200: x^100+x^15+1
        !           201: @end example
        !           202:
        !           203: @table @t
        !           204: @item $B;2>H(B
        !           205: @fref{defpoly_mod2}
        !           206: @end table
        !           207:
        !           208: @node field_type_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           209: @subsection @code{field_type_ff}
        !           210: @findex field_type_ff
        !           211:
        !           212: @table @t
        !           213: @item field_type_ff()
        !           214: :: $B@_Dj$5$l$F$$$k4pACBN$N<oN`(B
        !           215: @end table
        !           216:
        !           217: @table @var
        !           218: @item return
        !           219: $B?t(B
        !           220: @end table
        !           221:
        !           222: @itemize @bullet
        !           223: @item
        !           224: $B@_Dj$5$l$F$$$k4pACBN$N<oN`$rJV$9(B.
        !           225: @item
        !           226: $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.
        !           227: @end itemize
        !           228:
        !           229: @example
        !           230: [0] field_type_ff();
        !           231: 0
        !           232: [1] setmod_ff(3);
        !           233: 3
        !           234: [2] field_type_ff();
        !           235: 1
        !           236: [3] setmod_ff(x^2+x+1);
        !           237: x^2+x+1
        !           238: [4] field_type_ff();
        !           239: 2
        !           240: @end example
        !           241:
        !           242: @table @t
        !           243: @item $B;2>H(B
        !           244: @fref{setmod_ff}
        !           245: @end table
        !           246:
        !           247: @node field_order_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           248: @subsection @code{field_order_ff}
        !           249: @findex field_order_ff
        !           250:
        !           251: @table @t
        !           252: @item field_order_ff()
        !           253: :: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B
        !           254: @end table
        !           255:
        !           256: @table @var
        !           257: @item return
        !           258: $B?t(B
        !           259: @end table
        !           260:
        !           261: @itemize @bullet
        !           262: @item
        !           263: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B ($B85$N8D?t(B) $B$rJV$9(B.
        !           264: @item
        !           265: $B@_Dj$5$l$F$$$kBN$,(B GF(q) $B$J$i$P(B q $B$rJV$9(B.
        !           266: @end itemize
        !           267:
        !           268: @example
        !           269: [0] field_order_ff();
        !           270: field_order_ff : current_ff is not set
        !           271: return to toplevel
        !           272: [0] setmod_ff(3);
        !           273: 3
        !           274: [1] field_order_ff();
        !           275: 3
        !           276: [2] setmod_ff(x^2+x+1);
        !           277: x^2+x+1
        !           278: [3] field_order_ff();
        !           279: 4
        !           280: @end example
        !           281:
        !           282: @table @t
        !           283: @item $B;2>H(B
        !           284: @fref{setmod_ff}
        !           285: @end table
        !           286:
        !           287: @node characteristic_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           288: @subsection @code{characteristic_ff}
        !           289: @findex characteristic_ff
        !           290:
        !           291: @table @t
        !           292: @item characteristic_ff()
        !           293: :: $B@_Dj$5$l$F$$$kBN$NI8?t(B
        !           294: @end table
        !           295:
        !           296: @table @var
        !           297: @item return
        !           298: $B?t(B
        !           299: @end table
        !           300:
        !           301: @itemize @bullet
        !           302: @item
        !           303: $B@_Dj$5$l$F$$$kBN$NI8?t$rJV$9(B.
        !           304: @item
        !           305: GF(p) $B$N>l9g(B p, GF(2^n) $B$N>l9g(B 2 $B$rJV$9(B.
        !           306: @end itemize
        !           307:
        !           308: @example
        !           309: [0] characteristic_ff();
        !           310: characteristic_ff : current_ff is not set
        !           311: return to toplevel
        !           312: [0] setmod_ff(3);
        !           313: 3
        !           314: [1] characteristic_ff();
        !           315: 3
        !           316: [2] setmod_ff(x^2+x+1);
        !           317: x^2+x+1
        !           318: [3] characteristic_ff();
        !           319: 2
        !           320: @end example
        !           321:
        !           322: @table @t
        !           323: @item $B;2>H(B
        !           324: @fref{setmod_ff}
        !           325: @end table
        !           326:
        !           327: @node extdeg_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           328: @subsection @code{extdeg_ff}
        !           329: @findex extdeg_ff
        !           330:
        !           331: @table @t
        !           332: @item extdeg_ff()
        !           333: :: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t(B
        !           334: @end table
        !           335:
        !           336: @table @var
        !           337: @item return
        !           338: $B?t(B
        !           339: @end table
        !           340:
        !           341: @itemize @bullet
        !           342: @item
        !           343: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t$rJV$9(B.
        !           344: @item
        !           345: GF(p) $B$N>l9g(B 1, GF(2^n) $B$N>l9g(B n $B$rJV$9(B.
        !           346: @end itemize
        !           347:
        !           348: @example
        !           349: [0] extdeg_ff();
        !           350: extdeg_ff : current_ff is not set
        !           351: return to toplevel
        !           352: [0] setmod_ff(3);
        !           353: 3
        !           354: [1] extdeg_ff();
        !           355: 1
        !           356: [2] setmod_ff(x^2+x+1);
        !           357: x^2+x+1
        !           358: [3] extdeg_ff();
        !           359: 2
        !           360: @end example
        !           361:
        !           362: @table @t
        !           363: @item $B;2>H(B
        !           364: @fref{setmod_ff}
        !           365: @end table
        !           366:
        !           367: @node simp_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           368: @subsection @code{simp_ff}
        !           369: @findex simp_ff
        !           370:
        !           371: @table @t
        !           372: @item simp_ff(@var{obj})
        !           373: :: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49(B
        !           374: @end table
        !           375:
        !           376: @table @var
        !           377: @item return
        !           378: $B?t$^$?$OB?9`<0(B
        !           379: @item obj
        !           380: $B?t$^$?$OB?9`<0(B
        !           381: @end table
        !           382:
        !           383: @itemize @bullet
        !           384: @item
        !           385: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49$9$k(B.
        !           386: @item
        !           387: $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
        !           388: $BMQ$$$k(B.
        !           389: @item
        !           390: $BM-8BBN$N85$KBP$7(B, $BK!$"$k$$$ODj5AB?9`<0$K$h$k(B reduction $B$r9T$&>l9g$K$b(B
        !           391: $BMQ$$$k(B.
        !           392: @end itemize
        !           393:
        !           394: @example
        !           395: [0] simp_ff((x+1)^10);
        !           396: 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
        !           397: [1] setmod_ff(3);
        !           398: 3
        !           399: [2] simp_ff((x+1)^10);
        !           400: 1*x^10+1*x^9+1*x+1
        !           401: [3] ntype(coef(@@@@,10));
        !           402: 6
        !           403: @end example
        !           404:
        !           405: @table @t
        !           406: @item $B;2>H(B
        !           407: @fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}
        !           408: @end table
        !           409:
        !           410: @node random_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           411: @subsection @code{random_ff}
        !           412: @findex random_ff
        !           413:
        !           414: @table @t
        !           415: @item random_ff()
        !           416: :: $BM-8BBN$N85$NMp?t@8@.(B
        !           417: @end table
        !           418:
        !           419: @table @var
        !           420: @item return
        !           421: $BM-8BBN$N85(B
        !           422: @end table
        !           423:
        !           424: @itemize @bullet
        !           425: @item
        !           426: $BM-8BBN$N85$rMp?t@8@.$9$k(B.
        !           427: @item
        !           428: 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,
        !           429: 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
        !           430: $BJV$9(B.
        !           431: @item
        !           432: @code{random()}, @code{lrandom()} $B$HF1$8(B 32bit $BMp?tH/@84o$r;HMQ$7$F$$$k(B.
        !           433: @end itemize
        !           434:
        !           435: @example
        !           436: [0] random_ff();
        !           437: random_ff : current_ff is not set
        !           438: return to toplevel
        !           439: [0] setmod_ff(pari(nextprime,2^40));
        !           440: 1099511627791
        !           441: [1] random_ff();
        !           442: 561856154357
        !           443: [2] random_ff();
        !           444: 45141628299
        !           445: @end example
        !           446:
        !           447: @table @t
        !           448: @item $B;2>H(B
        !           449: @fref{setmod_ff}, @fref{random}, @fref{lrandom}
        !           450: @end table
        !           451:
        !           452: @node lmptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           453: @subsection @code{lmptop}
        !           454: @findex lmptop
        !           455:
        !           456: @table @t
        !           457: @item lmptop(@var{obj})
        !           458: :: GF(p) $B78?tB?9`<0$N78?t$r@0?t$KJQ49(B
        !           459: @end table
        !           460:
        !           461: @table @var
        !           462: @item return
        !           463: $B@0?t78?tB?9`<0(B
        !           464: @item obj
        !           465: GF(p)$B78?tB?9`<0(B
        !           466: @end table
        !           467:
        !           468: @itemize @bullet
        !           469: @item
        !           470: GF(p) $B78?tB?9`<0$N78?t$r@0?t$KJQ49$9$k(B.
        !           471: @item
        !           472: GF(p) $B$N85$O(B, 0 $B0J>e(B p $BL$K~$N@0?t$GI=8=$5$l$F$$$k(B.
        !           473: $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
        !           474: $BJQ49$5$l$k(B.
        !           475: @item
        !           476: GF(p) $B$N85$O(B, $B@0?t$KJQ49$5$l$k(B.
        !           477: @end itemize
        !           478:
        !           479: @example
        !           480: [0] setmod_ff(pari(nextprime,2^40));
        !           481: 1099511627791
        !           482: [1] F=simp_ff((x-1)^10);
        !           483: 1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
        !           484: +1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
        !           485: [2] setmod_ff(547);
        !           486: 547
        !           487: [3] F=simp_ff((x-1)^10);
        !           488: 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
        !           489: [4] lmptop(F);
        !           490: 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
        !           491: [5] lmptop(coef(F,1));
        !           492: 537
        !           493: [6] ntype(@@@@);
        !           494: 0
        !           495: @end example
        !           496:
        !           497: @table @t
        !           498: @item $B;2>H(B
        !           499: @fref{simp_ff}
        !           500: @end table
        !           501:
        !           502: @node ntogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           503: @subsection @code{ntogf2n}
        !           504: @findex ntogf2n
        !           505:
        !           506: @table @t
        !           507: @item ntogf2n(@var{m})
        !           508: :: $B<+A3?t$r(B GF(2^n) $B$N85$KJQ49(B
        !           509: @end table
        !           510:
        !           511: @table @var
        !           512: @item return
        !           513: GF(2^n) $B$N85(B
        !           514: @item m
        !           515: $BHsIi@0?t(B
        !           516: @end table
        !           517:
        !           518: @itemize @bullet
        !           519: @item
        !           520: $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
        !           521: $B$KBP$7(B, GF(2^n)=GF(2)[t]/(g(t)) $B$N85(B
        !           522: @var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) $B$rJV$9(B.
        !           523: @item
        !           524: $BDj5AB?9`<0$K$h$k>jM>$O<+F0E*$K$O7W;;$5$l$J$$$?$a(B, @code{simp_ff()} $B$r(B
        !           525: $BE,MQ$9$kI,MW$,$"$k(B.
        !           526: @end itemize
        !           527:
        !           528: @example
        !           529: [1] setmod_ff(x^30+x+1);
        !           530: x^30+x+1
        !           531: [2] N=ntogf2n(2^100);
        !           532: (@@^100)
        !           533: [3] simp_ff(N);
        !           534: (@@^13+@@^12+@@^11+@@^10)
        !           535: @end example
        !           536:
        !           537: @table @t
        !           538: @item $B;2>H(B
        !           539: @fref{gf2nton}
        !           540: @end table
        !           541:
        !           542: @node gf2nton,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           543: @subsection @code{gf2nton}
        !           544: @findex gf2nton
        !           545:
        !           546: @table @t
        !           547: @item gf2nton(@var{m})
        !           548: :: GF(2^n) $B$N85$r<+A3?t$KJQ49(B
        !           549: @end table
        !           550:
        !           551: @table @var
        !           552: @item return
        !           553: $BHsIi@0?t(B
        !           554: @item m
        !           555: GF(2^n) $B$N85(B
        !           556: @end table
        !           557:
        !           558: @itemize @bullet
        !           559: @item
        !           560: @code{gf2nton} $B$N5UJQ49$G$"$k(B.
        !           561: @end itemize
        !           562:
        !           563: @example
        !           564: [1] setmod_ff(x^30+x+1);
        !           565: x^30+x+1
        !           566: [2] N=gf2nton(2^100);
        !           567: (@@^100)
        !           568: [3] simp_ff(N);
        !           569: (@@^13+@@^12+@@^11+@@^10)
        !           570: [4] gf2nton(N);
        !           571: 1267650600228229401496703205376
        !           572: [5] gf2nton(simp_ff(N));
        !           573: 15360
        !           574: @end example
        !           575:
        !           576: @table @t
        !           577: @item $B;2>H(B
        !           578: @fref{gf2nton}
        !           579: @end table
        !           580:
        !           581: @node ptogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           582: @subsection @code{ptogf2n}
        !           583: @findex ptogf2n
        !           584:
        !           585: @table @t
        !           586: @item ptogf2n(@var{poly})
        !           587: :: $B0lJQ?tB?9`<0$r(B GF(2^n) $B$N85$KJQ49(B
        !           588: @end table
        !           589:
        !           590: @table @var
        !           591: @item return
        !           592: GF(2^n) $B$N85(B
        !           593: @item poly
        !           594: $B0lJQ?tB?9`<0(B
        !           595: @end table
        !           596:
        !           597: @itemize @bullet
        !           598: @item
        !           599: @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
        !           600: $BJQ49$5$l$k(B.
        !           601: @var{poly} $B$NJQ?t$K(B @code{@@} $B$rBeF~$7$?7k2L$HEy$7$$(B.
        !           602: @end itemize
        !           603:
        !           604: @example
        !           605: [1] setmod_ff(x^30+x+1);
        !           606: x^30+x+1
        !           607: [2] ptogf2n(x^100);
        !           608: (@@^100)
        !           609: @end example
        !           610:
        !           611: @table @t
        !           612: @item $B;2>H(B
        !           613: @fref{gf2ntop}
        !           614: @end table
        !           615:
        !           616: @node gf2ntop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           617: @subsection @code{gf2ntop}
        !           618: @findex gf2ntop
        !           619:
        !           620: @table @t
        !           621: @item gf2ntop(@var{m}[,@var{v}])
        !           622: :: GF(2^n) $B$N85$rB?9`<0$KJQ49(B
        !           623: @end table
        !           624:
        !           625: @table @var
        !           626: @item return
        !           627: $B0lJQ?tB?9`<0(B
        !           628: @item m
        !           629: GF(2^n) $B$N85(B
        !           630: @item v
        !           631: $BITDj85(B
        !           632: @end table
        !           633:
        !           634: @itemize @bullet
        !           635: @item
        !           636: @var{m} $B$rI=$9B?9`<0$r(B, $B@0?t78?t$NB?9`<0%*%V%8%'%/%H$H$7$FJV$9(B.
        !           637: @item @var{v} $B$N;XDj$,$J$$>l9g(B, $BD>A0$N(B @code{ptogf2n()} $B8F$S=P$7(B
        !           638: $B$K$*$1$k0z?t$NJQ?t(B ($B%G%U%)%k%H$O(B @code{x}), $B;XDj$,$"$k>l9g$K$O(B
        !           639: $B;XDj$5$l$?ITDj85$rJQ?t$H$9$kB?9`<0$rJV$9(B.
        !           640: @end itemize
        !           641:
        !           642: @example
        !           643: [1] setmod_ff(x^30+x+1);
        !           644: x^30+x+1
        !           645: [2] N=simp_ff(gf2ntop(2^100));
        !           646: (@@^13+@@^12+@@^11+@@^10)
        !           647: [5] gf2ntop(N);
        !           648: [207] gf2ntop(N);
        !           649: x^13+x^12+x^11+x^10
        !           650: [208] gf2ntop(N,t);
        !           651: t^13+t^12+t^11+t^10
        !           652: @end example
        !           653:
        !           654: @table @t
        !           655: @item $B;2>H(B
        !           656: @fref{ptogf2n}
        !           657: @end table
        !           658:
        !           659: @node defpoly_mod2,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           660: @subsection @code{defpoly_mod2}
        !           661: @findex defpoly_mod2
        !           662:
        !           663: @table @t
        !           664: @item defpoly_mod2(@var{d})
        !           665: :: GF(2) $B>e4{Ls$J0lJQ?tB?9`<0$N@8@.(B
        !           666: @end table
        !           667:
        !           668: @table @var
        !           669: @item return
        !           670: $BB?9`<0(B
        !           671: @item d
        !           672: $B@5@0?t(B
        !           673: @end table
        !           674:
        !           675: @itemize @bullet
        !           676: @item
        !           677: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
        !           678: @item
        !           679: $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.
        !           680: @item
        !           681: $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
        !           682: 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,
        !           683: $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
        !           684: $B>.$5$$$b$N$rJV$9(B.
        !           685: @end itemize
        !           686:
        !           687: @example
        !           688: @end example
        !           689:
        !           690: @table @t
        !           691: @item $B;2>H(B
        !           692: @fref{setmod_ff}
        !           693: @end table
        !           694:
        !           695: @node fctr_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           696: @subsection @code{fctr_ff}
        !           697: @findex fctr_ff
        !           698:
        !           699: @table @t
        !           700: @item fctr_ff(@var{poly})
        !           701: :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsJ,2r(B
        !           702: @end table
        !           703:
        !           704: @table @var
        !           705: @item return
        !           706: $B%j%9%H(B
        !           707: @item poly
        !           708: $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
        !           709: @end table
        !           710:
        !           711: @itemize @bullet
        !           712: @item
        !           713: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
        !           714: @item
        !           715: $B0lJQ?tB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G4{LsJ,2r$9$k(B.
        !           716: @item
        !           717: $B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
        !           718: $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
        !           719: $B=EJ#EY$G$"$k(B.
        !           720: @item
        !           721: @var{poly} $B$N<g78?t$O<N$F$i$l$k(B.
        !           722: @end itemize
        !           723:
        !           724: @example
        !           725: [178] setmod_ff(2^64-95);
        !           726: 18446744073709551521
        !           727: [179]  fctr_ff(x^5+x+1);
        !           728: [[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
        !           729: [1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]
        !           730: @end example
        !           731:
        !           732: @table @t
        !           733: @item $B;2>H(B
        !           734: @fref{setmod_ff}
        !           735: @end table
        !           736:
        !           737: @node irredcheck_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           738: @subsection @code{irredcheck_ff}
        !           739: @findex irredcheck_ff
        !           740:
        !           741: @table @t
        !           742: @item irredcheck_ff(@var{poly})
        !           743: :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsH=Dj(B
        !           744: @end table
        !           745:
        !           746: @table @var
        !           747: @item return
        !           748: 0|1
        !           749: @item poly
        !           750: $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
        !           751: @end table
        !           752:
        !           753: @itemize @bullet
        !           754: @item
        !           755: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
        !           756: @item
        !           757: $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.
        !           758: @end itemize
        !           759:
        !           760: @example
        !           761: [178] setmod_ff(2^64-95);
        !           762: 18446744073709551521
        !           763: [179] ] F=x^10+random_ff();
        !           764: x^10+14687973587364016969
        !           765: [180] irredcheck_ff(F);
        !           766: 1
        !           767: @end example
        !           768:
        !           769: @table @t
        !           770: @item $B;2>H(B
        !           771: @fref{setmod_ff}
        !           772: @end table
        !           773:
        !           774: @node randpoly_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           775: @subsection @code{randpoly_ff}
        !           776: @findex randpoly_ff
        !           777:
        !           778: @table @t
        !           779: @item randpoly_ff(@var{d},@var{v})
        !           780: :: $BM-8BBN>e$N(B $BMp?t78?t(B 1 $BJQ?tB?9`<0$N@8@.(B
        !           781: @end table
        !           782:
        !           783: @table @var
        !           784: @item return
        !           785: $BB?9`<0(B
        !           786: @item d
        !           787: $B@5@0?t(B
        !           788: @item v
        !           789: $BITDj85(B
        !           790: @end table
        !           791:
        !           792: @itemize @bullet
        !           793: @item
        !           794: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
        !           795: @item
        !           796: @var{d} $B<!L$K~(B, $BJQ?t$,(B @var{v}, $B78?t$,8=:_@_Dj$5$l$F$$$kM-8BBN$KB0$9$k(B
        !           797: 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.
        !           798: @end itemize
        !           799:
        !           800: @example
        !           801: [178] setmod_ff(2^64-95);
        !           802: 18446744073709551521
        !           803: [179] ] F=x^10+random_ff();
        !           804: [180] randpoly_ff(3,x);
        !           805: 17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
        !           806: [181] randpoly_ff(3,x);
        !           807: 7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
        !           808: [182] randpoly_ff(3,x);
        !           809: 10247781277095450395*x^2+10243690944992524936*x+4063829049268845492
        !           810: @end example
        !           811:
        !           812: @table @t
        !           813: @item $B;2>H(B
        !           814: @fref{setmod_ff}, @fref{random_ff}
        !           815: @end table
        !           816:
        !           817: @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !           818: @subsection @code{ecm_add_ff}, @code{ecm_sub_ff}, @code{ecm_chsgn_ff}
        !           819: @findex ecm_add_ff
        !           820: @findex ecm_sub_ff
        !           821: @findex ecm_chsgn_ff
        !           822:
        !           823: @table @t
        !           824: @item ecm_add_ff(@var{p1},@var{p2},@var{ec})
        !           825: @itemx ecm_sub_ff(@var{p1},@var{p2},@var{ec})
        !           826: @itemx ecm_chsgn_ff(@var{p1},@var{p2},@var{ec})
        !           827: :: $BBJ1_6J@~>e$NE@$N2C;;(B, $B8:;;(B, $B5U85(B
        !           828: @end table
        !           829:
        !           830: @table @var
        !           831: @item return
        !           832: $B%Y%/%H%k$^$?$O(B 0
        !           833: @item p1,p2
        !           834: $BD9$5(B 3 $B$N%Y%/%H%k$^$?$O(B 0
        !           835: @item ec
        !           836: $BD9$5(B 2 $B$N%Y%/%H%k(B
        !           837: @end table
        !           838:
        !           839: @itemize @bullet
        !           840: @item
        !           841: $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G(B,  @var{ec} $B$GDj5A$5$l$kBJ1_6J@~>e$N(B
        !           842: $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.
        !           843: @item
        !           844: @var{ec} $B$O(B, $B@_Dj$5$l$F$$$kM-8BBN$,4qI8?tAGBN$N>l9g(B,
        !           845: @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]}
        !           846: $B$rI=$9(B.
        !           847: @item
        !           848: $B0z?t(B, $B7k2L$H$b$K(B, $BL58B1sE@$O(B 0 $B$GI=$5$l$k(B.
        !           849: @item
        !           850: @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
        !           851: $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.
        !           852: @item
        !           853: $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.
        !           854: $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
        !           855: $B$G3d$kI,MW$,$"$k(B.
        !           856: @item
        !           857: @var{p1}, @var{p2} $B$,BJ1_6J@~>e$NE@$+$I$&$+$N%A%'%C%/$O$7$J$$(B.
        !           858: @end itemize
        !           859:
        !           860: @example
        !           861: [0] setmod_ff(1125899906842679)$
        !           862: [1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
        !           863: [2] Pt1=newvect(3,[1,-412127497938252,1])$
        !           864: [3] Pt2=newvect(3,[6,-252647084363045,1])$
        !           865: [4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
        !           866: [ 560137044461222 184453736165476 125 ]
        !           867: [5] F=y^2-(x^3+EC[0]*x+EC[1])$
        !           868: [6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
        !           869: 0
        !           870: [7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
        !           871: 0
        !           872: [8] D=ecm_sub_ff(Pt3,Pt2,EC);
        !           873: [ 886545905133065 119584559149586 886545905133065 ]
        !           874: [9] D[0]/D[2]==Pt1[0]/Pt1[2];
        !           875: 1
        !           876: [10] D[1]/D[2]==Pt1[1]/Pt1[2];
        !           877: 1
        !           878: @end example
        !           879:
        !           880: @table @t
        !           881: @item $B;2>H(B
        !           882: @fref{setmod_ff}
        !           883: @end table
        !           884: