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

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: