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

1.8     ! noro        1: @comment $OpenXM: OpenXM/src/asir-doc/parts/ff.texi,v 1.7 2003/04/21 03:07:32 noro Exp $
1.2       noro        2: \BJP
1.1       noro        3: @node $BM-8BBN$K4X$9$k1i;;(B,,, Top
                      4: @chapter $BM-8BBN$K4X$9$k1i;;(B
1.2       noro        5: \E
                      6: \BEG
                      7: @node Finite fields,,, Top
                      8: @chapter Finite fields
                      9: \E
1.1       noro       10:
                     11: @menu
1.2       noro       12: \BJP
1.1       noro       13: * $BM-8BBN$NI=8=$*$h$S1i;;(B::
                     14: * $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
1.5       noro       15: * $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B::
1.1       noro       16: * $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B::
                     17: * $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B::
1.2       noro       18: \E
                     19: \BEG
                     20: * Representation of finite fields::
                     21: * Univariate polynomials on finite fields::
1.5       noro       22: * Polynomials on small finite fields::
1.2       noro       23: * Elliptic curves on finite fields::
                     24: * Functions for Finite fields::
                     25: \E
1.1       noro       26: @end menu
                     27:
1.2       noro       28: \BJP
1.1       noro       29: @node $BM-8BBN$NI=8=$*$h$S1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
                     30: @section $BM-8BBN$NI=8=$*$h$S1i;;(B
1.2       noro       31: \E
                     32: \BEG
                     33: @node Representation of finite fields,,, Finite fields
                     34: @section Representation of finite fields
                     35: \E
1.1       noro       36:
                     37: @noindent
1.2       noro       38: \BJP
1.5       noro       39: @b{Asir} $B$K$*$$$F$O(B, $BM-8BBN$O(B, $B@5I8?tAGBN(B GF(@var{p}), $BI8?t(B 2 $B$NM-8BBN(B GF(2^@var{n}),
                     40: GF(@var{p}) $B$N(B @var{n} $B<!3HBg(B GF(@var{p^n})
1.1       noro       41: $B$,Dj5A$G$-$k(B. $B$3$l$i$OA4$F(B, @code{setmod_ff()} $B$K$h$jDj5A$5$l$k(B.
1.2       noro       42: \E
                     43: \BEG
1.5       noro       44: On @b{Asir} GF(@var{p}), GF(2^@var{n}), GF(@var{p^n}) can be defined, where
                     45: GF(@var{p}) is a finite prime field of charateristic @var{p},
                     46: GF(2^@var{n}) is a finite field of characteristic 2 and
                     47: GF(@var{p^n}) is a finite extension of GF(@var{p}). These are
1.2       noro       48: all defined by @code{setmod_ff()}.
                     49: \E
1.1       noro       50:
                     51: @example
                     52: [0] P=pari(nextprime,2^50);
                     53: 1125899906842679
                     54: [1] setmod_ff(P);
                     55: 1125899906842679
                     56: [2] field_type_ff();
                     57: 1
                     58: [3] load("fff");
                     59: 1
                     60: [4] F=defpoly_mod2(50);
                     61: x^50+x^4+x^3+x^2+1
                     62: [5] setmod_ff(F);
                     63: x^50+x^4+x^3+x^2+1
                     64: [6] field_type_ff();
                     65: 2
1.4       noro       66: [7] setmod_ff(x^3+x+1,1125899906842679);
                     67: [1*x^3+1*x+1,1125899906842679]
                     68: [8] field_type_ff();
                     69: 3
                     70: [9] setmod_ff(3,5);
                     71: [3,x^5+2*x+1,x]
                     72: [10] field_type_ff();
                     73: 4
1.1       noro       74: @end example
1.2       noro       75: \BJP
1.4       noro       76: @code{setmod_ff()} $B$O(B, $B$5$^$6$^$J%?%$%W$NM-8BBN$r4pACBN$H$7$F%;%C%H$9$k(B.
1.5       noro       77: $B0z?t$,@5@0?t(B @var{p} $B$N>l9g(B GF(@var{p}), @var{n} $B<!B?9`<0(B f(x) $B$N>l(B
                     78: $B9g(B, f(x) mod 2 $B$rDj5AB?9`<0$H$9$k(B GF(2^@var{n}) $B$r$=$l$>$l4pACBN$H$7$F%;%C%H$9(B
1.4       noro       79: $B$k(B. $B$^$?(B, $BM-8BAGBN$NM-8B<!3HBg$bDj5A$G$-$k(B. $B>\$7$/$O(B @xref{$B?t$N7?(B}.
                     80: @code{setmod_ff()} $B$K$*$$$F$O0z?t$N4{Ls%A%'%C%/$O9T$o$:(B, $B8F$S=P$7B&(B
1.1       noro       81: $B$,@UG$$r;}$D(B.
                     82:
                     83: $B4pACBN$H$O(B, $B$"$/$^$GM-8BBN$N85$H$7$F@k8@$"$k$$$ODj5A$5$l$?%*%V%8%'%/%H$,(B,
                     84: $B%;%C%H$5$l$?4pACBN$N1i;;$K=>$&$H$$$&0UL#$G$"$k(B. $BB($A(B, $BM-M}?t$I$&$7$N1i;;(B
                     85: $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
                     86: $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
                     87: $B$k(B.
                     88:
                     89: 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.
1.5       noro       90: $B$5$i$K(B, 0 $B$G$J$$M-8BBN$N85$N?t<1JL;R$O(B, GF(@var{p}) $B$N>l9g(B 6, GF(2^@var{n}) $B$N>l9g(B 7
1.1       noro       91: $B$H$J$k(B.
                     92:
1.5       noro       93: $BM-8BBN$N85$NF~NOJ}K!$O(B, $BM-8BBN$N<oN`$K$h$jMM!9$G$"$k(B. GF(@var{p}) $B$N>l9g(B,
1.1       noro       94: @code{simp_ff()} $B$K$h$k(B.
1.2       noro       95: \E
                     96:
                     97: \BEG
                     98: If @var{p} is a positive integer, @code{setmod_ff(@var{p})} sets
1.5       noro       99: GF(@var{p}) as the current base field.
1.2       noro      100: If @var{f} is a univariate polynomial of degree @var{n},
1.5       noro      101: @code{setmod_ff(@var{f})} sets GF(2^@var{n}) as the current
                    102: base field.  GF(2^@var{n}) is represented
                    103: as an algebraic extension of GF(2) with the defining polynomial
1.4       noro      104: @var{f mod 2}. Furthermore, finite extensions of prime finite fields
                    105: can be defined. @xref{Types of numbers}.
                    106: In all cases the primality check of the argument is
1.2       noro      107: not done and the caller is responsible for it.
                    108:
                    109: Correctly speaking there is no actual object corresponding to a 'base field'.
                    110: Setting a base field means that operations on elements of finite fields
                    111: are done according to the arithmetics of the base field. Thus, if
                    112: operands of an arithmetic operation are both rational numbers, then the result
                    113: is also a rational number. However, if one of the operands is in
                    114: a finite field, then the other is automatically regarded as in the
                    115: same finite field and the operation is done in the finite field.
                    116:
                    117: A non zero element of a finite field belongs to the number and has object
1.5       noro      118: identifier 1. Its number identifier is 6 if the finite field is GF(@var{p}),
                    119: 7 if it is GF(2^@var{n}).
1.2       noro      120:
                    121: There are several methods to input an element of a finite field.
1.5       noro      122: An element of GF(@var{p}) can be input by @code{simp_ff()}.
1.2       noro      123: \E
1.1       noro      124:
                    125: @example
                    126: [0] P=pari(nextprime,2^50);
                    127: 1125899906842679
                    128: [1] setmod_ff(P);
                    129: 1125899906842679
                    130: [2] A=simp_ff(2^100);
                    131: 3025
                    132: [3] ntype(@@@@);
                    133: 6
                    134: @end example
                    135:
1.5       noro      136: \JP $B$^$?(B, GF(2^@var{n}) $B$N>l9g$$$/$D$+$NJ}K!$,$"$k(B.
                    137: \EG In the case of GF(2^@var{n}) the following methods are available.
1.2       noro      138:
1.1       noro      139: @example
                    140: [0] setmod_ff(x^50+x^4+x^3+x^2+1);
                    141: x^50+x^4+x^3+x^2+1
                    142: [1] A=@@;
                    143: (@@)
                    144: [2] ptogf2n(x^50+1);
                    145: (@@^50+1)
                    146: [3] simp_ff(@@@@);
                    147: (@@^4+@@^3+@@^2)
                    148: [4] ntogf2n(2^10-1);
                    149: (@@^9+@@^8+@@^7+@@^6+@@^5+@@^4+@@^3+@@^2+@@+1)
                    150: @end example
                    151:
1.2       noro      152: \BJP
1.1       noro      153: $BM-8BBN$N85$O?t$G$"$j(B, $BBN1i;;$,2DG=$G$"$k(B. @code{@@} $B$O(B
1.5       noro      154: GF(2^@var{n}) $B$N(B, GF(2) $B>e$N@8@.85$G$"$k(B. $B>\$7$/$O(B @xref{$B?t$N7?(B}.
1.2       noro      155: \E
                    156: \BEG
                    157: Elements of finite fields are numbers and one can apply field arithmetics
1.5       noro      158: to them. @code{@@} is a generator of GF(2^@var{n}) over GF(2).
1.2       noro      159: @xref{Types of numbers}.
                    160: \E
1.1       noro      161:
                    162: @noindent
                    163:
1.2       noro      164: \BJP
1.1       noro      165: @node $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
                    166: @section $BM-8BBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
1.2       noro      167: \E
                    168: \BEG
                    169: @node Univariate polynomials on finite fields,,, Finite fields
                    170: @section Univariate polynomials on finite fields
                    171: \E
1.1       noro      172:
                    173: @noindent
1.2       noro      174: \BJP
1.1       noro      175: @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,
                    176: $BB?9`<0$N4{LsH=Dj$J$I$N4X?t$,Dj5A$5$l$F$$$k(B.
                    177:
                    178: $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
                    179: $B$H$J$j(B, $BF~NOB?9`<0$N<g78?t$O<N$F$i$l$k(B.
                    180:
                    181: $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
                    182: $B%"%k%4%j%:%`$r:NMQ$7$F$$$k(B.
                    183:
                    184: $BM-8BBN>e$G$N0x?tJ,2r$O(B, DDF $B$N8e(B, $B<!?tJL0x;R$NJ,2r$N:]$K(B, Berlekamp
                    185: $B%"%k%4%j%:%`$GNm6u4V$r5a$a(B, $B4pDl%Y%/%H%k$N:G>.B?9`<0$r5a$a(B, $B$=$N:,(B
                    186: $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.
1.2       noro      187: \E
                    188: \BEG
                    189: In @samp{fff} square-free factorization, DDF (distinct degree factorization),
                    190: irreducible factorization and primality check are implemented for
                    191: univariate polynomials over finite fields.
                    192:
                    193: Factorizers return lists of [@b{factor},@b{multiplicity}]. The factor
                    194: part is monic and the information on the leading coefficient of the
                    195: input polynomial is abandoned.
                    196:
                    197: The algorithm used in square-free factorization is the most primitive one.
                    198:
                    199: The irreducible factorization proceeds as follows.
1.1       noro      200:
1.2       noro      201: @enumerate
                    202: @item DDF
                    203: @item Nullspace computation by Berlekamp algorithm
                    204: @item Root finding of minimal polynomials of bases of the nullspace
                    205: @item Separation of irreducible factors by the roots
                    206: @end enumerate
                    207: \E
1.1       noro      208:
1.5       noro      209: @noindent
                    210:
                    211: \BJP
                    212: @node $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
                    213: @section $B>.I8?tM-8BBN>e$G$NB?9`<0$N1i;;(B
                    214: \E
                    215: \BEG
                    216: @node Polynomials on small finite fields,,, Finite fields
                    217: @section Polynomials on small finite fields
                    218: \E
                    219:
                    220: \BJP
                    221: $B>.I8?tM-8BBN78?t$NB?9`<0$K8B$j(B, $BB?JQ?tB?9`<0$N0x?tJ,2r$,(B
                    222: $BAH$_9~$_4X?t$H$7$F<BAu$5$l$F$$$k(B. $B4X?t$O(B @code{sffctr()}
                    223: $B$G$"$k(B. $B$^$?(B, @code{modfctr()} $B$b(B, $BM-8BAGBN>e$GB?JQ?t(B
                    224: $BB?9`<0$N0x?tJ,2r$r9T$&$,(B, $B<B:]$K$O(B, $BFbIt$G==J,Bg$-$J(B
                    225: $B3HBgBN$r@_Dj$7(B, @code{sffctr()} $B$r8F$S=P$7$F(B,
                    226: $B:G=*E*$KAGBN>e$N0x;R$r9=@.$9$k(B, $B$H$$$&J}K!$G7W;;$7$F$$$k(B.
                    227: \E
                    228:
                    229: \BEG
                    230: A multivariate polynomial over small finite field
                    231: set by @code{setmod_ff(p,n)} can be factorized by
                    232: using a builtin function @code{sffctr()}. @code{modfctr()}
                    233: also factorizes a polynomial over a finite prime field.
                    234: Internally, @code{modfctr()} creates a sufficiently large
                    235: field extension of the specified ground field, and
                    236: it calls @code{sffctr()}, then it constructs irreducible
                    237: factors over the ground field from the factors returned by
                    238: @code{sffctr()}.
                    239: \E
                    240:
1.2       noro      241: \BJP
1.1       noro      242: @node $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B,,, $BM-8BBN$K4X$9$k1i;;(B
                    243: @section $BM-8BBN>e$NBJ1_6J@~$K4X$9$k1i;;(B
1.2       noro      244: \E
                    245: \BEG
                    246: @node Elliptic curves on finite fields,,, Finite fields
                    247: @section Elliptic curves on finite fields
                    248: \E
1.1       noro      249:
1.2       noro      250: \BJP
1.1       noro      251: $BM-8BBN>e$NBJ1_6J@~$K4X$9$k$$$/$D$+$N4pK\E*$J1i;;$,(B, $BAH$_9~$_4X?t$H$7$F(B
                    252: $BDs6!$5$l$F$$$k(B.
                    253:
1.5       noro      254: $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}
1.1       noro      255: $B$OM-8BBN$N85$G(B,
                    256: @code{setmod_ff} $B$GDj5A$5$l$F$$$kM-8BBN$,AGBN$N>l9g(B, @var{y^2=x^3+ax+b},
                    257: $BI8?t(B 2 $B$NBN$N>l9g(B @var{y^2+xy=x^3+ax^2+b} $B$rI=$9(B.
                    258:
                    259: $BBJ1_6J@~>e$NE@$O(B, $BL58B1sE@$b9~$a$F2CK!72$r$J$9(B. $B$3$N1i;;$K4X$7$F(B, $B2C;;(B
                    260: (@code{ecm_add_ff()}), $B8:;;(B (@code{ecm_sub_ff()}) $B$*$h$S5U857W;;$N$?$a$N(B
                    261: $B4X?t(B (@code{ecm_chsgn_ff()}) $B$,Ds6!$5$l$F$$$k(B. $BCm0U$9$Y$-$O(B, $B1i;;$NBP>](B
                    262: $B$H$J$kE@$NI=8=$,(B,
                    263:
                    264: @itemize @bullet
                    265: @item $BL58B1sE@$O(B 0.
1.5       noro      266: @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
1.1       noro      267: 0 $B$G$J$$(B.
                    268: @end itemize
                    269:
1.5       noro      270: $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
                    271: $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
                    272: $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
1.1       noro      273: $B@8@.$9$kI,MW$,$"$k(B.
                    274: $B1i;;7k2L$b@F<!:BI8$GF@$i$l$k$,(B, @var{z} $B:BI8$,(B 1 $B$H$O8B$i$J$$$?$a(B,
                    275: $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
                    276: $B3d$kI,MW$,$"$k(B.
1.2       noro      277: \E
                    278:
                    279: \BEG
                    280: Several fundamental operations on elliptic curves over finite fields
                    281: are provided as built-in functions.
                    282:
1.5       noro      283: An elliptic curve is specified by a vector [@var{a b}] of length 2,
1.2       noro      284: where @var{a}, @var{b} are elements of finite fields.
1.5       noro      285: If the current base field is a prime field, then [@var{a b}] represents
1.2       noro      286: @var{y^2=x^3+ax+b}. If the current base field is a finite field of
1.5       noro      287: characteristic 2, then [@var{a b}] represents @var{y^2+xy=x^3+ax^2+b}.
1.2       noro      288:
                    289: Points on an elliptic curve together with the point at infinity
                    290: forms an additive group. The addition, the subtraction and the
                    291: additive inverse operation are provided as @code{ecm_add_ff()},
                    292: @code{ecm_sub_ff()} and @code{ecm_chsgn_ff()} respectively.
                    293: Here the representation of points are as follows.
                    294:
                    295: @itemize @bullet
                    296: @item 0 denotes the point at infinity.
1.5       noro      297: @item The other points are represented by vectors [@var{x y z}] of
1.2       noro      298: length 3 with non-zero @var{z}.
                    299: @end itemize
                    300:
1.5       noro      301: [@var{x y z}] represents a projective coordinate and
                    302: it corresponds to [@var{x/z y/z}] in the affine coordinate.
                    303: To apply the above operations to a point [@var{x y}],
                    304: [@var{x y 1}] should be used instead as an argument.
1.2       noro      305: The result of an operation is also represented by the projective
                    306: coordinate. As the third coordinate is not always equal to 1,
                    307: one has to divide the first and the scond coordinate by the third
                    308: one to obtain the affine coordinate.
                    309: \E
1.1       noro      310:
1.2       noro      311: \BJP
1.1       noro      312: @node $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B,,, $BM-8BBN$K4X$9$k1i;;(B
                    313: @section $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
1.2       noro      314: \E
                    315: \BEG
                    316: @node Functions for Finite fields,,, Finite fields
                    317: @section Functions for Finite fields
                    318: \E
1.1       noro      319:
                    320: @menu
                    321: * setmod_ff::
                    322: * field_type_ff::
                    323: * field_order_ff::
                    324: * characteristic_ff::
                    325: * extdeg_ff::
                    326: * simp_ff::
                    327: * random_ff::
                    328: * lmptop::
                    329: * ntogf2n::
                    330: * gf2nton::
                    331: * ptogf2n::
                    332: * gf2ntop::
1.5       noro      333: * ptosfp sfptop::
1.1       noro      334: * defpoly_mod2::
1.6       noro      335: * sffctr::
1.1       noro      336: * fctr_ff::
                    337: * irredcheck_ff::
                    338: * randpoly_ff::
                    339: * ecm_add_ff ecm_sub_ff ecm_chsgn_ff::
                    340: * extdeg_ff::
                    341: @end menu
                    342:
1.2       noro      343: \JP @node setmod_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    344: \EG @node setmod_ff,,, Functions for Finite fields
1.1       noro      345: @subsection @code{setmod_ff}
                    346: @findex setmod_ff
                    347:
                    348: @table @t
1.8     ! noro      349: @item setmod_ff([@var{p}|@var{defpoly2}])
        !           350: @itemx setmod_ff([@var{defpolyp},@var{p}])
        !           351: @itemx setmod_ff([@var{p},@var{n}])
1.2       noro      352: \JP :: $BM-8BBN$N@_Dj(B, $B@_Dj$5$l$F$$$kM-8BBN$NK!(B, $BDj5AB?9`<0$NI=<((B
                    353: \EG :: Sets/Gets the current base fields.
1.1       noro      354: @end table
                    355:
                    356: @table @var
                    357: @item return
1.2       noro      358: \JP $B?t$^$?$OB?9`<0(B
                    359: \EG number or polynomial
1.8     ! noro      360: @item p
1.2       noro      361: \JP $BAG?t(B
                    362: \EG prime
1.8     ! noro      363: @item defpoly2
1.2       noro      364: \JP GF(2) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
                    365: \EG univariate polynomial irreducible over GF(2)
1.8     ! noro      366: @item defpolyp
        !           367: \JP GF(@var{p}) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
        !           368: \EG univariate polynomial irreducible over GF(@var{p})
1.5       noro      369: @item n
                    370: \JP $B3HBg<!?t(B
                    371: \EG the extension degree
1.1       noro      372: @end table
                    373:
                    374: @itemize @bullet
1.2       noro      375: \BJP
1.1       noro      376: @item
1.8     ! noro      377: $B0z?t$,@5@0?t(B @var{p} $B$N;~(B, GF(@var{p}) $B$r4pACBN$H$7$F@_Dj$9$k(B.
1.1       noro      378: @item
1.8     ! noro      379: $B0z?t$,B?9`<0(B @var{defpoly2} $B$N;~(B,
        !           380: GF(2^deg(@var{defpoly2} mod 2)) = GF(2)[t]/(@var{defpoly2}(t) mod 2)
1.1       noro      381: $B$r4pACBN$H$7$F@_Dj$9$k(B.
                    382: @item
1.8     ! noro      383: $B0z?t$,(B @var{defpolyp} $B$H(B @var{p} $B$N;~(B,
        !           384: GF(@var{p^deg(defpolyp)}) $B$r4pACBN$H$7$F@_Dj$9$k(B.
        !           385: @item
1.5       noro      386: $B0z?t$,(B @var{p} $B$H(B @var{n} $B$N;~(B,
                    387: GF(@var{p^n}) $B$r4pACBN$H$7$F@_Dj$9$k(B. @var{p^n} $B$O(B @var{2^29} $BL$K~$G(B
                    388: $B$J$1$l$P$J$i$J$$(B. $B$^$?(B, @var{p} $B$,(B @var{2^14} $B0J>e$N$H$-(B,
                    389: @var{n} $B$O(B 1 $B$G$J$1$l$P$J$i$J$$(B.
                    390: @item
1.8     ! noro      391: $BL50z?t$N;~(B, $B@_Dj$5$l$F$$$k4pACBN$,(B GF(@var{p})$B$N>l9g(B @var{p},
1.5       noro      392: GF(2^@var{n}) $B$N>l9gDj5AB?9`<0$rJV$9(B.
1.8     ! noro      393: $B4pACBN$,(B @code{setmod_ff(@var{defpoly},@var{p})} $B$GDj5A$5$l$?(B
        !           394: GF(@var{p}^@var{n}) $B$N>l9g(B, [@var{defpoly},@var{p}] $B$rJV$9(B.
        !           395: $B4pACBN$,(B @code{setmod_ff(@var{p},@var{n})} $B$GDj5A$5$l$?(B
        !           396: GF(p^@var{n}) $B$N>l9g(B,
1.5       noro      397: [@var{p},@var{defpoly},@var{prim_elem}] $B$rJV$9(B. $B$3$3$G(B, @var{defpoly}
1.8     ! noro      398: $B$O(B, @var{n} $B<!3HBg$NDj5AB?9`<0(B, @var{prim_elem} $B$O(B, GF(@var{p^n})$B$N(B
1.5       noro      399: $B>hK!72$N@8@.85$r0UL#$9$k(B.
1.1       noro      400: @item
1.5       noro      401: GF(2^@var{n}) $B$NDj5AB?9`<0$O(B, GF(2) $B>e(B n $B<!4{Ls$J$i$J$s$G$bNI$$$,(B, $B8zN($K(B
1.1       noro      402: $B1F6A$9$k$?$a(B, @code{defpoly_mod2()} $B$G@8@.$9$k$N$,$h$$(B.
1.2       noro      403: \E
                    404: \BEG
                    405: @item
1.8     ! noro      406: If the argument is a non-negative integer @var{p}, GF(@var{p})
        !           407: is set as the current base field.
        !           408: @item
        !           409: If the argument is a polynomial @var{defpoly2},
        !           410: GF(2^deg(@var{defpoly2} mod 2)) = GF(2)[t]/(@var{defpoly2}(t) mod2)
1.2       noro      411: is set as the current base field.
                    412: @item
1.8     ! noro      413: If the arguments are a polynomial @var{defpolyp} and a prime @var{p},
        !           414: GF(@var{p}^deg(@var{defpolyp})) = GF(@var{p})[t]/(@var{defpolyp}(t))
1.2       noro      415: is set as the current base field.
                    416: @item
1.5       noro      417: If the arguments are a prime @var{p} and an extension degree @var{n},
                    418: GF(@var{p^n}) is set as the current base field. @var{p^n} must be
                    419: less than @var{2^29} and if @var{p} is greater than or equal to @var{2^14},
                    420: then @var{n} must be equal to 1.
                    421: @item
1.2       noro      422: If no argument is specified, the modulus indicating the current base field
1.8     ! noro      423: is returned. If the current base field is GF(@var{p}), @var{p} is
1.5       noro      424: returned. If it is GF(2^@var{n}), the defining polynomial is returned.
1.8     ! noro      425: If it is GF(@var{p^n}) defined by @code{setmod_ff(@var{defpoly},@var{p})},
        !           426: [@var{defpolyp},@var{p}] is returned.
        !           427: If it is GF(@var{p^n}) defined by @code{setmod_ff(@var{p},@var{n})},
1.5       noro      428: [@var{p},@var{defpoly},@var{prim_elem}] is returned. Here, @var{defpoly}
                    429: is the defining polynomial of the @var{n}-th extension,
                    430: and @var{prim_elem} is the generator of the multiplicative group
                    431: of GF(@var{p^n}).
1.2       noro      432: @item
                    433: Any irreducible univariate polynomial over GF(2) is available to
1.5       noro      434: set GF(2^@var{n}). However the use of @code{defpoly_mod2()} is recommended
1.2       noro      435: for efficiency.
                    436: \E
1.1       noro      437: @end itemize
                    438:
                    439: @example
                    440: [174] defpoly_mod2(100);
                    441: x^100+x^15+1
                    442: [175] setmod_ff(@@@@);
                    443: x^100+x^15+1
                    444: [176] setmod_ff();
                    445: x^100+x^15+1
1.8     ! noro      446: [177] setmod_ff(x^4+x+1,547);
        !           447: [1*x^4+1*x+1,547]
        !           448: [178] setmod_ff(2,5);
1.5       noro      449: [2,x^5+x^2+1,x]
1.1       noro      450: @end example
                    451:
                    452: @table @t
1.2       noro      453: \JP @item $B;2>H(B
                    454: \EG @item References
1.1       noro      455: @fref{defpoly_mod2}
                    456: @end table
                    457:
1.2       noro      458: \JP @node field_type_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    459: \EG @node field_type_ff,,, Functions for Finite fields
1.1       noro      460: @subsection @code{field_type_ff}
                    461: @findex field_type_ff
                    462:
                    463: @table @t
                    464: @item field_type_ff()
1.2       noro      465: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N<oN`(B
                    466: \EG :: Type of the current base field.
1.1       noro      467: @end table
                    468:
                    469: @table @var
                    470: @item return
1.2       noro      471: \JP $B@0?t(B
                    472: \EG integer
1.1       noro      473: @end table
                    474:
                    475: @itemize @bullet
1.2       noro      476: \BJP
1.1       noro      477: @item
                    478: $B@_Dj$5$l$F$$$k4pACBN$N<oN`$rJV$9(B.
                    479: @item
1.5       noro      480: $B@_Dj$J$7$J$i(B 0, GF(@var{p}) $B$J$i(B 1, GF(2^@var{n}) $B$J$i(B 2 $B$rJV$9(B.
1.2       noro      481: \E
                    482: \BEG
                    483: @item
                    484: Returns the type of the current base field.
                    485: @item
1.5       noro      486: If no field is set, 0 is returned. If GF(@var{p}) is set, 1 is returned.
                    487: If GF(2^@var{n}) is set, 2 is returned.
1.2       noro      488: \E
1.1       noro      489: @end itemize
                    490:
                    491: @example
                    492: [0] field_type_ff();
                    493: 0
                    494: [1] setmod_ff(3);
                    495: 3
                    496: [2] field_type_ff();
                    497: 1
                    498: [3] setmod_ff(x^2+x+1);
                    499: x^2+x+1
                    500: [4] field_type_ff();
                    501: 2
                    502: @end example
                    503:
                    504: @table @t
1.2       noro      505: \JP @item $B;2>H(B
                    506: \EG @item References
1.1       noro      507: @fref{setmod_ff}
                    508: @end table
                    509:
1.2       noro      510: \JP @node field_order_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    511: \EG @node field_order_ff,,, Functions for Finite fields
1.1       noro      512: @subsection @code{field_order_ff}
                    513: @findex field_order_ff
                    514:
                    515: @table @t
                    516: @item field_order_ff()
1.2       noro      517: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B
                    518: \EG :: Order of the current base field.
1.1       noro      519: @end table
                    520:
                    521: @table @var
                    522: @item return
1.2       noro      523: \JP $B@0?t(B
                    524: \EG integer
1.1       noro      525: @end table
                    526:
                    527: @itemize @bullet
1.2       noro      528: \BJP
1.1       noro      529: @item
                    530: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B ($B85$N8D?t(B) $B$rJV$9(B.
                    531: @item
1.5       noro      532: $B@_Dj$5$l$F$$$kBN$,(B GF(@var{q}) $B$J$i$P(B q $B$rJV$9(B.
1.2       noro      533: \E
                    534: \BEG
                    535: @item
                    536: Returns the order of the current base field.
                    537: @item
1.5       noro      538: @var{q} is returned if the current base field is GF(@var{q}).
1.2       noro      539: \E
1.1       noro      540: @end itemize
                    541:
                    542: @example
                    543: [0] field_order_ff();
                    544: field_order_ff : current_ff is not set
                    545: return to toplevel
                    546: [0] setmod_ff(3);
                    547: 3
                    548: [1] field_order_ff();
                    549: 3
                    550: [2] setmod_ff(x^2+x+1);
                    551: x^2+x+1
                    552: [3] field_order_ff();
                    553: 4
                    554: @end example
                    555:
                    556: @table @t
1.2       noro      557: \JP @item $B;2>H(B
                    558: \EG @item References
1.1       noro      559: @fref{setmod_ff}
                    560: @end table
                    561:
1.2       noro      562: \JP @node characteristic_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    563: \EG @node characteristic_ff,,, Functions for Finite fields
1.1       noro      564: @subsection @code{characteristic_ff}
                    565: @findex characteristic_ff
                    566:
                    567: @table @t
                    568: @item characteristic_ff()
1.2       noro      569: \JP :: $B@_Dj$5$l$F$$$kBN$NI8?t(B
                    570: \EG :: Characteristic of the current base field.
1.1       noro      571: @end table
                    572:
                    573: @table @var
                    574: @item return
1.2       noro      575: \JP $B@0?t(B
                    576: \EG integer
1.1       noro      577: @end table
                    578:
                    579: @itemize @bullet
1.2       noro      580: \BJP
1.1       noro      581: @item
                    582: $B@_Dj$5$l$F$$$kBN$NI8?t$rJV$9(B.
                    583: @item
1.5       noro      584: GF(@var{p}) $B$N>l9g(B @var{p}, GF(2^@var{n}) $B$N>l9g(B 2 $B$rJV$9(B.
1.2       noro      585: \E
                    586: \BEG
                    587: @item
                    588: Returns the characteristic of the current base field.
                    589: @item
1.5       noro      590: @var{p} is returned if GF(@var{p}), where @var{p} is a prime, is set.
                    591: @var{2} is returned if GF(2^@var{n}) is set.
1.2       noro      592: \E
1.1       noro      593: @end itemize
                    594:
                    595: @example
                    596: [0] characteristic_ff();
                    597: characteristic_ff : current_ff is not set
                    598: return to toplevel
                    599: [0] setmod_ff(3);
                    600: 3
                    601: [1] characteristic_ff();
                    602: 3
                    603: [2] setmod_ff(x^2+x+1);
                    604: x^2+x+1
                    605: [3] characteristic_ff();
                    606: 2
                    607: @end example
                    608:
                    609: @table @t
1.2       noro      610: \JP @item $B;2>H(B
                    611: \EG @item References
1.1       noro      612: @fref{setmod_ff}
                    613: @end table
                    614:
1.2       noro      615: \JP @node extdeg_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    616: \EG @node extdeg_ff,,, Functions for Finite fields
1.1       noro      617: @subsection @code{extdeg_ff}
                    618: @findex extdeg_ff
                    619:
                    620: @table @t
                    621: @item extdeg_ff()
1.2       noro      622: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t(B
                    623: \EG :: Extension degree of the current base field over the prime field.
1.1       noro      624: @end table
                    625:
                    626: @table @var
                    627: @item return
1.2       noro      628: \JP $B@0?t(B
                    629: \EG integer
1.1       noro      630: @end table
                    631:
                    632: @itemize @bullet
1.2       noro      633: \BJP
1.1       noro      634: @item
                    635: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t$rJV$9(B.
                    636: @item
1.5       noro      637: GF(@var{p}) $B$N>l9g(B 1, GF(2^@var{n}) $B$N>l9g(B @var{n} $B$rJV$9(B.
1.2       noro      638: \E
                    639: \BEG
                    640: @item
                    641: Returns the extension degree of the current base field over the prime field.
                    642: @item
1.5       noro      643: 1 is returned if GF(@var{p}), where @var{p} is a prime, is set.
                    644: @var{n} is returned if GF(2^@var{n}) is set.
1.2       noro      645: \E
1.1       noro      646: @end itemize
                    647:
                    648: @example
                    649: [0] extdeg_ff();
                    650: extdeg_ff : current_ff is not set
                    651: return to toplevel
                    652: [0] setmod_ff(3);
                    653: 3
                    654: [1] extdeg_ff();
                    655: 1
                    656: [2] setmod_ff(x^2+x+1);
                    657: x^2+x+1
                    658: [3] extdeg_ff();
                    659: 2
                    660: @end example
                    661:
                    662: @table @t
1.2       noro      663: \JP @item $B;2>H(B
                    664: \EG @item References
1.1       noro      665: @fref{setmod_ff}
                    666: @end table
                    667:
1.2       noro      668: \JP @node simp_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    669: \EG @node simp_ff,,, Functions for Finite fields
1.1       noro      670: @subsection @code{simp_ff}
                    671: @findex simp_ff
                    672:
                    673: @table @t
                    674: @item simp_ff(@var{obj})
1.2       noro      675: \JP :: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49(B
                    676: \BEG
                    677: :: Converts numbers or coefficients of polynomials into elements
                    678: in finite fields.
                    679: \E
1.1       noro      680: @end table
                    681:
                    682: @table @var
                    683: @item return
1.2       noro      684: \JP $B?t$^$?$OB?9`<0(B
                    685: \EG number or polynomial
1.1       noro      686: @item obj
1.2       noro      687: \JP $B?t$^$?$OB?9`<0(B
                    688: \EG number or polynomial
1.1       noro      689: @end table
                    690:
                    691: @itemize @bullet
1.2       noro      692: \BJP
1.1       noro      693: @item
                    694: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49$9$k(B.
                    695: @item
                    696: $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
                    697: $BMQ$$$k(B.
                    698: @item
                    699: $BM-8BBN$N85$KBP$7(B, $BK!$"$k$$$ODj5AB?9`<0$K$h$k(B reduction $B$r9T$&>l9g$K$b(B
                    700: $BMQ$$$k(B.
1.5       noro      701: @item
                    702: $B>.I8?tM-8BBN$N85$KJQ49$9$k>l9g(B, $B0lC6AGBN>e$K<M1F$7$F$+$i(B, $B3HBgBN$N(B
                    703: $B85$KJQ49$5$l$k(B. $B3HBgBN$N85$KD>@\JQ49$9$k$K$O(B @code{ptosfp()} $B$r(B
                    704: $BMQ$$$k(B.
1.2       noro      705: \E
                    706: \BEG
                    707: @item
                    708: Converts numbers or coefficients of polynomials into elements in finite
                    709: fields.
                    710: @item
                    711: It is used to convert integers or intrgral polynomials int
                    712: elements of finite fields or polynomials over finite fields.
                    713: @item
                    714: An element of a finite field may not have the reduced representation.
1.5       noro      715: In such case an application of @code{simp_ff} ensures that the output has
1.2       noro      716: the reduced representation.
1.5       noro      717: If a small finite field is set as a ground field,
                    718: an integer is projected the finite prime field, then
                    719: it is embedded into the ground field. @code{ptosfp()}
                    720: can be used for direct projection to the ground field.
1.2       noro      721: \E
1.1       noro      722: @end itemize
                    723:
                    724: @example
                    725: [0] simp_ff((x+1)^10);
                    726: 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
                    727: [1] setmod_ff(3);
                    728: 3
                    729: [2] simp_ff((x+1)^10);
                    730: 1*x^10+1*x^9+1*x+1
                    731: [3] ntype(coef(@@@@,10));
                    732: 6
1.5       noro      733: [4] setmod_ff(2,3);
                    734: [2,x^3+x+1,x]
                    735: [5] simp_ff(1);
                    736: @@_0
                    737: [6] simp_ff(2);
                    738: 0
                    739: [7] ptosfp(2);
                    740: @@_1
1.1       noro      741: @end example
                    742:
                    743: @table @t
1.2       noro      744: \JP @item $B;2>H(B
                    745: \EG @item References
1.5       noro      746: @fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}, @fref{ptosfp sfptop}
1.1       noro      747: @end table
                    748:
1.2       noro      749: \JP @node random_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    750: \EG @node random_ff,,, Functions for Finite fields
1.1       noro      751: @subsection @code{random_ff}
                    752: @findex random_ff
                    753:
                    754: @table @t
                    755: @item random_ff()
1.2       noro      756: \JP :: $BM-8BBN$N85$NMp?t@8@.(B
                    757: \EG :: Random generation of an element of a finite field.
1.1       noro      758: @end table
                    759:
                    760: @table @var
                    761: @item return
1.2       noro      762: \JP $BM-8BBN$N85(B
                    763: \EG element of a finite field
1.1       noro      764: @end table
                    765:
                    766: @itemize @bullet
1.2       noro      767: \BJP
1.1       noro      768: @item
                    769: $BM-8BBN$N85$rMp?t@8@.$9$k(B.
                    770: @item
1.2       noro      771: @code{random()}, @code{lrandom()} $B$HF1$8(B 32bit $BMp?tH/@84o$r;HMQ$7$F$$$k(B.
                    772: \E
                    773: \BEG
                    774: @item
                    775: Generates an element of the current base field randomly.
1.1       noro      776: @item
1.2       noro      777: The same random generator as in @code{random()}, @code{lrandom()}
                    778: is used.
                    779: \E
1.1       noro      780: @end itemize
                    781:
                    782: @example
                    783: [0] random_ff();
                    784: random_ff : current_ff is not set
                    785: return to toplevel
                    786: [0] setmod_ff(pari(nextprime,2^40));
                    787: 1099511627791
                    788: [1] random_ff();
                    789: 561856154357
                    790: [2] random_ff();
                    791: 45141628299
                    792: @end example
                    793:
                    794: @table @t
1.2       noro      795: \JP @item $B;2>H(B
                    796: \EG @item References
1.1       noro      797: @fref{setmod_ff}, @fref{random}, @fref{lrandom}
                    798: @end table
                    799:
1.2       noro      800: \JP @node lmptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    801: \EG @node lmptop,,, Functions for Finite fields
1.1       noro      802: @subsection @code{lmptop}
                    803: @findex lmptop
                    804:
                    805: @table @t
                    806: @item lmptop(@var{obj})
1.5       noro      807: \JP :: GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49(B
                    808: \EG :: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
1.1       noro      809: @end table
                    810:
                    811: @table @var
                    812: @item return
1.2       noro      813: \JP $B@0?t78?tB?9`<0(B
                    814: \EG integral polynomial
1.1       noro      815: @item obj
1.5       noro      816: \JP GF(@var{p}) $B78?tB?9`<0(B
                    817: \EG polynomial over GF(@var{p})
1.1       noro      818: @end table
                    819:
                    820: @itemize @bullet
1.2       noro      821: \BJP
1.1       noro      822: @item
1.5       noro      823: GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49$9$k(B.
1.1       noro      824: @item
1.5       noro      825: GF(@var{p}) $B$N85$O(B, 0 $B0J>e(B p $BL$K~$N@0?t$GI=8=$5$l$F$$$k(B.
1.1       noro      826: $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
                    827: $BJQ49$5$l$k(B.
1.2       noro      828: \E
                    829: \BEG
                    830: @item
1.5       noro      831: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
1.1       noro      832: @item
1.5       noro      833: An element of GF(@var{p}) is represented by a non-negative integer @var{r} less than
1.2       noro      834: @var{p}.
                    835: Each coefficient of a polynomial is converted into an integer object
                    836: whose value is @var{r}.
                    837: \E
1.1       noro      838: @end itemize
                    839:
                    840: @example
                    841: [0] setmod_ff(pari(nextprime,2^40));
                    842: 1099511627791
                    843: [1] F=simp_ff((x-1)^10);
                    844: 1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
                    845: +1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
                    846: [2] setmod_ff(547);
                    847: 547
                    848: [3] F=simp_ff((x-1)^10);
1.6       noro      849: 1*x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
                    850: +45*x^2+537*x+1
1.1       noro      851: [4] lmptop(F);
1.6       noro      852: x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
                    853: +45*x^2+537*x+1
1.1       noro      854: [5] lmptop(coef(F,1));
                    855: 537
                    856: [6] ntype(@@@@);
                    857: 0
                    858: @end example
                    859:
                    860: @table @t
1.2       noro      861: \JP @item $B;2>H(B
                    862: \EG @item References
1.1       noro      863: @fref{simp_ff}
                    864: @end table
                    865:
1.2       noro      866: \JP @node ntogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    867: \EG @node ntogf2n,,, Functions for Finite fields
1.1       noro      868: @subsection @code{ntogf2n}
                    869: @findex ntogf2n
                    870:
                    871: @table @t
                    872: @item ntogf2n(@var{m})
1.5       noro      873: \JP :: $B<+A3?t$r(B GF(2^@var{n}) $B$N85$KJQ49(B
                    874: \EG :: Converts a non-negative integer into an element of GF(2^@var{n}).
1.1       noro      875: @end table
                    876:
                    877: @table @var
                    878: @item return
1.5       noro      879: \JP GF(2^@var{n}) $B$N85(B
                    880: \EG element of GF(2^@var{n})
1.1       noro      881: @item m
1.2       noro      882: \JP $BHsIi@0?t(B
                    883: \EG non-negative integer
1.1       noro      884: @end table
                    885:
                    886: @itemize @bullet
1.2       noro      887: \BJP
1.1       noro      888: @item
                    889: $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
1.5       noro      890: $B$KBP$7(B, GF(2^@var{n})=GF(2)[t]/(g(t)) $B$N85(B
1.1       noro      891: @var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) $B$rJV$9(B.
                    892: @item
                    893: $BDj5AB?9`<0$K$h$k>jM>$O<+F0E*$K$O7W;;$5$l$J$$$?$a(B, @code{simp_ff()} $B$r(B
                    894: $BE,MQ$9$kI,MW$,$"$k(B.
1.2       noro      895: \E
                    896: \BEG
                    897: @item
                    898: Let @var{m} be a non-negative integer.
                    899: @var{m} has the binary representation
                    900: @var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k.
1.6       noro      901: This function returns an element of  GF(2^@var{n}) = GF(2)[t]/(g(t)),
1.2       noro      902: @var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t).
                    903: @item
                    904: Apply @code{simp_ff()} to reduce the result.
                    905: \E
1.1       noro      906: @end itemize
                    907:
                    908: @example
                    909: [1] setmod_ff(x^30+x+1);
                    910: x^30+x+1
                    911: [2] N=ntogf2n(2^100);
                    912: (@@^100)
                    913: [3] simp_ff(N);
                    914: (@@^13+@@^12+@@^11+@@^10)
                    915: @end example
                    916:
                    917: @table @t
1.2       noro      918: \JP @item $B;2>H(B
                    919: \EG @item References
1.1       noro      920: @fref{gf2nton}
                    921: @end table
                    922:
1.2       noro      923: \JP @node gf2nton,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    924: \EG @node gf2nton,,, Functions for Finite fields
1.1       noro      925: @subsection @code{gf2nton}
                    926: @findex gf2nton
                    927:
                    928: @table @t
                    929: @item gf2nton(@var{m})
1.5       noro      930: \JP :: GF(2^@var{n}) $B$N85$r<+A3?t$KJQ49(B
                    931: \EG :: Converts an element of GF(2^@var{n}) into a non-negative integer.
1.1       noro      932: @end table
                    933:
                    934: @table @var
                    935: @item return
1.2       noro      936: \JP $BHsIi@0?t(B
                    937: \EG non-negative integer
1.1       noro      938: @item m
1.5       noro      939: \JP GF(2^@var{n}) $B$N85(B
                    940: \EG element of GF(2^@var{n})
1.1       noro      941: @end table
                    942:
                    943: @itemize @bullet
                    944: @item
1.2       noro      945: \JP @code{gf2nton} $B$N5UJQ49$G$"$k(B.
                    946: \EG The inverse of @code{gf2nton}.
1.1       noro      947: @end itemize
                    948:
                    949: @example
                    950: [1] setmod_ff(x^30+x+1);
                    951: x^30+x+1
                    952: [2] N=gf2nton(2^100);
                    953: (@@^100)
                    954: [3] simp_ff(N);
                    955: (@@^13+@@^12+@@^11+@@^10)
                    956: [4] gf2nton(N);
                    957: 1267650600228229401496703205376
                    958: [5] gf2nton(simp_ff(N));
                    959: 15360
                    960: @end example
                    961:
                    962: @table @t
1.2       noro      963: \JP @item $B;2>H(B
                    964: \EG @item References
1.1       noro      965: @fref{gf2nton}
                    966: @end table
                    967:
1.2       noro      968: \JP @node ptogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    969: \EG @node ptogf2n,,, Functions for Finite fields
1.1       noro      970: @subsection @code{ptogf2n}
                    971: @findex ptogf2n
                    972:
                    973: @table @t
                    974: @item ptogf2n(@var{poly})
1.5       noro      975: \JP :: $B0lJQ?tB?9`<0$r(B GF(2^@var{n}) $B$N85$KJQ49(B
                    976: \EG :: Converts a univariate polynomial into an element of GF(2^@var{n}).
1.1       noro      977: @end table
                    978:
                    979: @table @var
                    980: @item return
1.5       noro      981: \JP GF(2^@var{n}) $B$N85(B
                    982: \EG element of GF(2^@var{n})
1.1       noro      983: @item poly
1.2       noro      984: \JP $B0lJQ?tB?9`<0(B
                    985: \EG univariate polynomial
1.1       noro      986: @end table
                    987:
                    988: @itemize @bullet
                    989: @item
1.2       noro      990: \BJP
1.5       noro      991: @var{poly} $B$NI=$9(B GF(2^@var{n}) $B$N85$r@8@.$9$k(B. $B78?t$O(B, 2 $B$G3d$C$?M>$j$K(B
1.1       noro      992: $BJQ49$5$l$k(B.
                    993: @var{poly} $B$NJQ?t$K(B @code{@@} $B$rBeF~$7$?7k2L$HEy$7$$(B.
1.2       noro      994: \E
                    995: \BEG
1.5       noro      996: Generates an element of GF(2^@var{n}) represented by @var{poly}.
1.2       noro      997: The coefficients are reduced modulo 2.
                    998: The output is equal to the result by substituting @code{@@} for
                    999: the variable of @var{poly}.
                   1000: \E
1.1       noro     1001: @end itemize
                   1002:
                   1003: @example
                   1004: [1] setmod_ff(x^30+x+1);
                   1005: x^30+x+1
                   1006: [2] ptogf2n(x^100);
                   1007: (@@^100)
                   1008: @end example
                   1009:
                   1010: @table @t
1.2       noro     1011: \JP @item $B;2>H(B
                   1012: \EG @item References
1.1       noro     1013: @fref{gf2ntop}
                   1014: @end table
                   1015:
1.2       noro     1016: \JP @node gf2ntop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1017: \EG @node gf2ntop,,, Functions for Finite fields
1.1       noro     1018: @subsection @code{gf2ntop}
                   1019: @findex gf2ntop
                   1020:
                   1021: @table @t
                   1022: @item gf2ntop(@var{m}[,@var{v}])
1.5       noro     1023: \JP :: GF(2^@var{n}) $B$N85$rB?9`<0$KJQ49(B
                   1024: \EG :: Converts an element of GF(2^@var{n}) into a polynomial.
1.1       noro     1025: @end table
                   1026:
                   1027: @table @var
                   1028: @item return
1.2       noro     1029: \JP $B0lJQ?tB?9`<0(B
                   1030: \EG univariate polynomial
1.1       noro     1031: @item m
1.5       noro     1032: \JP GF(2^@var{n}) $B$N85(B
                   1033: \EG an element of GF(2^@var{n})
1.1       noro     1034: @item v
1.2       noro     1035: \JP $BITDj85(B
                   1036: \EG indeterminate
1.1       noro     1037: @end table
                   1038:
                   1039: @itemize @bullet
1.2       noro     1040: \BJP
1.1       noro     1041: @item
                   1042: @var{m} $B$rI=$9B?9`<0$r(B, $B@0?t78?t$NB?9`<0%*%V%8%'%/%H$H$7$FJV$9(B.
1.2       noro     1043: @item
                   1044: @var{v} $B$N;XDj$,$J$$>l9g(B, $BD>A0$N(B @code{ptogf2n()} $B8F$S=P$7(B
1.1       noro     1045: $B$K$*$1$k0z?t$NJQ?t(B ($B%G%U%)%k%H$O(B @code{x}), $B;XDj$,$"$k>l9g$K$O(B
                   1046: $B;XDj$5$l$?ITDj85$rJQ?t$H$9$kB?9`<0$rJV$9(B.
1.2       noro     1047: \E
                   1048: \BEG
                   1049: @item
                   1050: Returns a polynomial representing @var{m}.
                   1051: @item
                   1052: If @var{v} is used as the variable of the output.
                   1053: If @var{v} is not specified, the variable of the argument
                   1054: of the latest @code{ptogf2n()} call. The default variable is @code{x}.
                   1055: \E
1.1       noro     1056: @end itemize
                   1057:
                   1058: @example
                   1059: [1] setmod_ff(x^30+x+1);
                   1060: x^30+x+1
                   1061: [2] N=simp_ff(gf2ntop(2^100));
                   1062: (@@^13+@@^12+@@^11+@@^10)
                   1063: [5] gf2ntop(N);
                   1064: [207] gf2ntop(N);
                   1065: x^13+x^12+x^11+x^10
                   1066: [208] gf2ntop(N,t);
                   1067: t^13+t^12+t^11+t^10
                   1068: @end example
                   1069:
                   1070: @table @t
1.2       noro     1071: \JP @item $B;2>H(B
                   1072: \EG @item References
1.1       noro     1073: @fref{ptogf2n}
                   1074: @end table
                   1075:
1.5       noro     1076: \JP @node ptosfp sfptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1077: \EG @node ptosfp sfptop,,, Functions for Finite fields
                   1078: @subsection @code{ptosfp}, @code{sfptop}
                   1079: @findex ptosfp
                   1080: @findex sfptop
                   1081:
                   1082: @table @t
                   1083: @item ptosfp(@var{p})
                   1084: @itemx sfptop(@var{p})
                   1085: \JP :: $B>.I8?tM-8BBN$X$NJQ49(B, $B5UJQ49(B
                   1086: \EG :: Transformation to/from a small finite field
                   1087: @end table
                   1088:
                   1089: @table @var
                   1090: @item return
                   1091: \JP $BB?9`<0(B
                   1092: \EG polynomial
                   1093: @item p
                   1094: \JP $BB?9`<0(B
                   1095: \EG polynomial
                   1096: @end table
                   1097:
                   1098: @itemize @bullet
                   1099: \BJP
                   1100: @item
                   1101: @code{ptosfp()} $B$O(B, $BB?9`<0$N78?t$r(B, $B8=:_@_Dj$5$l$F$$$k>.I8?tM-8BBN(B
                   1102: GF(p^@var{n}) $B$N85$KD>@\JQ49$9$k(B. $B78?t$,4{$KM-8BBN$N85$N>l9g$OJQ2=$7$J$$(B.
                   1103: $B@5@0?t$N>l9g(B, $B$^$:0L?t$G>jM>$r7W;;$7$?$"$H(B, $BI8?t(B @var{p} $B$K$h$j(B @var{p}
                   1104: $B?JE83+$7(B, @var{p} $B$r(B x $B$KCV$-49$($?B?9`<0$r(B, $B86;O85I=8=$KJQ49$9$k(B.
                   1105: $BNc$($P(B, GF(3^5) $B$O(B GF(3)[x]/(x^5+2*x+1) $B$H$7$FI=8=$5$l(B, $B$=$N3F(B
                   1106: $B85$O86;O85(B x $B$K4X$9$k$Y$-;X?t(B @var{k} $B$K$h$j(B @var{@@_k} $B$H$7$F(B
                   1107: $BI=<($5$l$k(B. $B$3$N$H$-(B, $BNc$($P(B @var{23 = 2*3^2+3+2} $B$O(B, 2*x^2+x+2
                   1108: $B$HI=8=$5$l(B, $B$3$l$O7k6I(B x^17 $B$HK!(B x^5+2*x+1 $B$GEy$7$$$N$G(B,
                   1109: @var{@@_17} $B$HJQ49$5$l$k(B.
                   1110: @item
                   1111: @code{sfptop()} $B$O(B @code{ptosfp()} $B$N5UJQ49$G$"$k(B.
                   1112: \E
                   1113: \BEG
                   1114: @item
                   1115: @code{ptosfp()} converts coefficients of a polynomial to
                   1116: elements in a small finite field GF(@var{p^n}) set as a ground field.
                   1117: If a coefficient is already an element of the field,
                   1118: no conversion is done. If a coefficient is a positive integer,
                   1119: then its residue modulo @var{p^n} is expanded as @var{p}-adic integer,
                   1120: then @var{p} is substituted by @var{x}, finally the polynomial
                   1121: is converted to its correspoding logarithmic representation
                   1122: with respect to the primitive element.
                   1123: For example, GF(3^5) is represented as F(3)[@var{x}]/(@var{x^5+2*x+1}),
                   1124: and each element of the field is represented as @var{@@_k}
                   1125: by its exponent @var{k} with respect to the primitive element @var{x}.
                   1126: @var{23 = 2*3^2+3+2} is represented as @var{2*x^2+x+2} and
                   1127: it is equivalent to @var{x^17} modulo @var{x^5+2*x+1}.
                   1128: Therefore an integer @var{23} is conterted to @var{@@_17}.
                   1129: @item
                   1130: @code{sfptop()} is the inverse of @code{ptosfp()}.
                   1131: \E
                   1132: @end itemize
                   1133:
                   1134: @example
                   1135: [196] setmod_ff(3,5);
                   1136: [3,x^5+2*x+1,x]
                   1137: [197] A = ptosfp(23);
                   1138: @@_17
                   1139: [198] 9*2+3+2;
                   1140: 23
                   1141: [199] x^17-(2*x^2+x+2);
                   1142: x^17-2*x^2-x-2
                   1143: [200] sremm(@@,x^5+2*x+1,3);
                   1144: 0
                   1145: [201] sfptop(A);
                   1146: 23
                   1147: @end example
                   1148:
                   1149: @table @t
                   1150: \JP @item $B;2>H(B
                   1151: \EG @item References
                   1152: @fref{setmod_ff}, @fref{simp_ff}
                   1153: @end table
1.2       noro     1154: \JP @node defpoly_mod2,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1155: \EG @node defpoly_mod2,,, Functions for Finite fields
1.1       noro     1156: @subsection @code{defpoly_mod2}
                   1157: @findex defpoly_mod2
                   1158:
                   1159: @table @t
                   1160: @item defpoly_mod2(@var{d})
1.2       noro     1161: \JP :: GF(2) $B>e4{Ls$J0lJQ?tB?9`<0$N@8@.(B
                   1162: \EG :: Generates an irreducible univariate polynomial over GF(2).
1.1       noro     1163: @end table
                   1164:
                   1165: @table @var
                   1166: @item return
1.2       noro     1167: \JP $BB?9`<0(B
                   1168: \EG univariate polynomial
1.1       noro     1169: @item d
1.2       noro     1170: \JP $B@5@0?t(B
                   1171: \EG positive integer
1.1       noro     1172: @end table
                   1173:
                   1174: @itemize @bullet
1.2       noro     1175: \BJP
1.1       noro     1176: @item
                   1177: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1178: @item
                   1179: $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.
                   1180: @item
                   1181: $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
                   1182: 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,
                   1183: $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
                   1184: $B>.$5$$$b$N$rJV$9(B.
1.2       noro     1185: \E
                   1186: \BEG
                   1187: @item
                   1188: Defined in @samp{fff}.
                   1189: @item
                   1190: An irreducible univariate polynomial of degree @var{d} is returned.
                   1191: @item
                   1192: If an irreducible trinomial @var{x^d+x^m+1} exists, then the one
                   1193: with the smallest @var{m} is returned.
                   1194: Otherwise, an irreducible pentanomial @var{x^d+x^m1+x^m2+x^m3+1}
                   1195: (@var{m1>m2>m3} is returned.
                   1196: @var{m1}, @var{m2} and @var{m3} are determined as follows:
                   1197: Fix @var{m1} as small as possible. Then fix @var{m2} as small as possible.
                   1198: Then fix @var{m3} as small as possible.
                   1199: \E
1.1       noro     1200: @end itemize
                   1201:
                   1202: @example
                   1203: @end example
                   1204:
                   1205: @table @t
1.2       noro     1206: \JP @item $B;2>H(B
                   1207: \EG @item References
1.1       noro     1208: @fref{setmod_ff}
1.6       noro     1209: @end table
                   1210:
                   1211: \JP @node sffctr,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1212: \EG @node sffctr,,, Functions for Finite fields
                   1213: @subsection @code{sffctr}
                   1214: @findex sffctr
                   1215:
                   1216: @table @t
                   1217: @item sffctr(@var{poly})
                   1218: \JP :: $BB?9`<0$N>.I8?tM-8BBN>e$G$N4{LsJ,2r(B
                   1219: \EG :: Irreducible factorization over a small finite field.
                   1220: @end table
                   1221:
                   1222: @table @var
                   1223: @item return
                   1224: \JP $B%j%9%H(B
                   1225: \EG list
                   1226: @item poly
                   1227: \JP $BM-8BBN>e$N(B $BB?9`<0(B
                   1228: \EG polynomial over a finite field
                   1229: @end table
                   1230:
                   1231: @itemize @bullet
                   1232: \BJP
                   1233: @item
                   1234: $BB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$k>.I8?tM-8BBN>e$G4{LsJ,2r$9$k(B.
                   1235: @item
                   1236: $B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
                   1237: $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
                   1238: $B=EJ#EY$G$"$k(B.
                   1239: \E
                   1240: \BEG
                   1241: @item
                   1242: Factorize @var{poly} into irreducible factors over
                   1243: a small finite field currently set.
                   1244: @item
                   1245: The result is a list [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...],
                   1246: where @var{fi} is a monic irreducible factor and @var{mi} is its
                   1247: multiplicity.
                   1248: \E
                   1249: @end itemize
1.7       noro     1250:
                   1251: @example
1.6       noro     1252: [0] setmod_ff(2,10);
                   1253: [2,x^10+x^3+1,x]
                   1254: [1] sffctr((z*y^3+z*y)*x^3+(y^5+y^3+z*y^2+z)*x^2+z^11*y*x+z^10*y^3+z^11);
                   1255: [[@@_0,1],[@@_0*z*y*x+@@_0*y^3+@@_0*z,1],[(@@_0*y+@@_0)*x+@@_0*z^5,2]]
                   1256: @end example
                   1257:
                   1258: @table @t
                   1259: \JP @item $B;2>H(B
                   1260: \EG @item References
                   1261: @fref{setmod_ff},
                   1262: @fref{modfctr}
1.1       noro     1263: @end table
                   1264:
1.2       noro     1265: \JP @node fctr_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1266: \EG @node fctr_ff,,, Functions for Finite fields
1.1       noro     1267: @subsection @code{fctr_ff}
                   1268: @findex fctr_ff
                   1269:
                   1270: @table @t
                   1271: @item fctr_ff(@var{poly})
1.2       noro     1272: \JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsJ,2r(B
                   1273: \EG :: Irreducible univariate factorization over a finite field.
1.1       noro     1274: @end table
                   1275:
                   1276: @table @var
                   1277: @item return
1.2       noro     1278: \JP $B%j%9%H(B
                   1279: \EG list
1.1       noro     1280: @item poly
1.2       noro     1281: \JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
                   1282: \EG univariate polynomial over a finite field
1.1       noro     1283: @end table
                   1284:
                   1285: @itemize @bullet
1.2       noro     1286: \BJP
1.1       noro     1287: @item
                   1288: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1289: @item
                   1290: $B0lJQ?tB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G4{LsJ,2r$9$k(B.
                   1291: @item
                   1292: $B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
                   1293: $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
                   1294: $B=EJ#EY$G$"$k(B.
                   1295: @item
                   1296: @var{poly} $B$N<g78?t$O<N$F$i$l$k(B.
1.2       noro     1297: \E
                   1298: \BEG
                   1299: @item
                   1300: Defined in @samp{fff}.
                   1301: @item
                   1302: Factorize @var{poly} into irreducible factors over the current base field.
                   1303: @item
                   1304: The result is a list [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...],
                   1305: where @var{fi} is a monic irreducible factor and @var{mi} is its
                   1306: multiplicity.
                   1307: @item
                   1308: The leading coefficient of @var{poly} is abandoned.
                   1309: \E
1.1       noro     1310: @end itemize
                   1311:
                   1312: @example
                   1313: [178] setmod_ff(2^64-95);
                   1314: 18446744073709551521
                   1315: [179]  fctr_ff(x^5+x+1);
                   1316: [[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
                   1317: [1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]
                   1318: @end example
                   1319:
                   1320: @table @t
1.2       noro     1321: \JP @item $B;2>H(B
                   1322: \EG @item References
1.1       noro     1323: @fref{setmod_ff}
                   1324: @end table
                   1325:
1.2       noro     1326: \JP @node irredcheck_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1327: \EG @node irredcheck_ff,,, Functions for Finite fields
1.1       noro     1328: @subsection @code{irredcheck_ff}
                   1329: @findex irredcheck_ff
                   1330:
                   1331: @table @t
                   1332: @item irredcheck_ff(@var{poly})
1.2       noro     1333: \JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsH=Dj(B
                   1334: \EG :: Primality check of a univariate polynomial over a finite field.
1.1       noro     1335: @end table
                   1336:
                   1337: @table @var
                   1338: @item return
                   1339: 0|1
                   1340: @item poly
1.2       noro     1341: \JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
                   1342: \EG univariate polynomial over a finite field
1.1       noro     1343: @end table
                   1344:
                   1345: @itemize @bullet
1.2       noro     1346: \BJP
1.1       noro     1347: @item
                   1348: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1349: @item
                   1350: $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.
1.2       noro     1351: \E
                   1352: \BEG
                   1353: @item
                   1354: Defined in @samp{fff}.
                   1355: @item
                   1356: Returns 1 if @var{poly} is irreducible over the current base field.
                   1357: Returns 0 otherwise.
                   1358: \E
1.1       noro     1359: @end itemize
                   1360:
                   1361: @example
                   1362: [178] setmod_ff(2^64-95);
                   1363: 18446744073709551521
                   1364: [179] ] F=x^10+random_ff();
                   1365: x^10+14687973587364016969
                   1366: [180] irredcheck_ff(F);
                   1367: 1
                   1368: @end example
                   1369:
                   1370: @table @t
1.2       noro     1371: \JP @item $B;2>H(B
                   1372: \EG @item References
1.1       noro     1373: @fref{setmod_ff}
                   1374: @end table
                   1375:
1.2       noro     1376: \JP @node randpoly_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1377: \EG @node randpoly_ff,,, Functions for Finite fields
1.1       noro     1378: @subsection @code{randpoly_ff}
                   1379: @findex randpoly_ff
                   1380:
                   1381: @table @t
                   1382: @item randpoly_ff(@var{d},@var{v})
1.2       noro     1383: \JP :: $BM-8BBN>e$N(B $BMp?t78?t(B 1 $BJQ?tB?9`<0$N@8@.(B
                   1384: \EG :: Generation of a random univariate polynomial over a finite field.
1.1       noro     1385: @end table
                   1386:
                   1387: @table @var
                   1388: @item return
1.2       noro     1389: \JP $BB?9`<0(B
                   1390: \EG polynomial
1.1       noro     1391: @item d
1.2       noro     1392: \JP $B@5@0?t(B
                   1393: \EG positive integer
1.1       noro     1394: @item v
1.2       noro     1395: \JP $BITDj85(B
                   1396: \EG indeterminate
1.1       noro     1397: @end table
                   1398:
                   1399: @itemize @bullet
1.2       noro     1400: \BJP
1.1       noro     1401: @item
                   1402: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1403: @item
                   1404: @var{d} $B<!L$K~(B, $BJQ?t$,(B @var{v}, $B78?t$,8=:_@_Dj$5$l$F$$$kM-8BBN$KB0$9$k(B
                   1405: 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.
1.2       noro     1406: \E
                   1407: \BEG
                   1408: @item
                   1409: Defined in @samp{fff}.
                   1410: @item
                   1411: Generates a polynomial of @var{v} such that the degree is less than @var{d}
                   1412: and the coefficients are in the current base field.
                   1413: The coefficients are generated by @code{random_ff()}.
                   1414: \E
1.1       noro     1415: @end itemize
                   1416:
                   1417: @example
                   1418: [178] setmod_ff(2^64-95);
                   1419: 18446744073709551521
                   1420: [179] ] F=x^10+random_ff();
                   1421: [180] randpoly_ff(3,x);
                   1422: 17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
                   1423: [181] randpoly_ff(3,x);
                   1424: 7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
                   1425: [182] randpoly_ff(3,x);
                   1426: 10247781277095450395*x^2+10243690944992524936*x+4063829049268845492
                   1427: @end example
                   1428:
                   1429: @table @t
1.2       noro     1430: \JP @item $B;2>H(B
                   1431: \EG @item References
1.1       noro     1432: @fref{setmod_ff}, @fref{random_ff}
                   1433: @end table
                   1434:
1.2       noro     1435: \JP @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1436: \EG @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, Functions for Finite fields
1.1       noro     1437: @subsection @code{ecm_add_ff}, @code{ecm_sub_ff}, @code{ecm_chsgn_ff}
                   1438: @findex ecm_add_ff
                   1439: @findex ecm_sub_ff
                   1440: @findex ecm_chsgn_ff
                   1441:
                   1442: @table @t
                   1443: @item ecm_add_ff(@var{p1},@var{p2},@var{ec})
                   1444: @itemx ecm_sub_ff(@var{p1},@var{p2},@var{ec})
1.3       noro     1445: @itemx ecm_chsgn_ff(@var{p1})
1.2       noro     1446: \JP :: $BBJ1_6J@~>e$NE@$N2C;;(B, $B8:;;(B, $B5U85(B
                   1447: \EG :: Addition, Subtraction and additive inverse for points on an elliptic curve.
1.1       noro     1448: @end table
                   1449:
                   1450: @table @var
                   1451: @item return
1.2       noro     1452: \JP $B%Y%/%H%k$^$?$O(B 0
                   1453: \EG vector or 0
1.5       noro     1454: @item p1 p2
1.2       noro     1455: \JP $BD9$5(B 3 $B$N%Y%/%H%k$^$?$O(B 0
                   1456: \EG vector of length 3 or 0
1.1       noro     1457: @item ec
1.2       noro     1458: \JP $BD9$5(B 2 $B$N%Y%/%H%k(B
                   1459: \EG vector of length 2
1.1       noro     1460: @end table
                   1461:
                   1462: @itemize @bullet
1.2       noro     1463: \BJP
1.1       noro     1464: @item
                   1465: $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G(B,  @var{ec} $B$GDj5A$5$l$kBJ1_6J@~>e$N(B
                   1466: $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.
                   1467: @item
                   1468: @var{ec} $B$O(B, $B@_Dj$5$l$F$$$kM-8BBN$,4qI8?tAGBN$N>l9g(B,
1.5       noro     1469: y^2=x^3+ec[0]x+ec[1], $BI8?t(B 2 $B$N>l9g(B y^2+xy=x^3+ec[0]x^2+ec[1]
1.1       noro     1470: $B$rI=$9(B.
                   1471: @item
                   1472: $B0z?t(B, $B7k2L$H$b$K(B, $BL58B1sE@$O(B 0 $B$GI=$5$l$k(B.
                   1473: @item
                   1474: @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
                   1475: $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.
                   1476: @item
                   1477: $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.
                   1478: $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
                   1479: $B$G3d$kI,MW$,$"$k(B.
                   1480: @item
                   1481: @var{p1}, @var{p2} $B$,BJ1_6J@~>e$NE@$+$I$&$+$N%A%'%C%/$O$7$J$$(B.
1.2       noro     1482: \E
                   1483: \BEG
                   1484: @item
                   1485: Let @var{p1}, @var{p2} be points on the elliptic curve represented by
                   1486: @var{ec} over the current base field.
                   1487: ecm_add_ff(@var{p1},@var{p2},@var{ec}), ecm_sub_ff(@var{p1},@var{p2},@var{ec})
1.3       noro     1488: and ecm_chsgn_ff(@var{p1}) returns
1.2       noro     1489: @var{p1+p2}, @var{p1-p2} and @var{-p1} respectively.
                   1490: @item
                   1491: If the current base field is a prime field of odd order, then
1.5       noro     1492: @var{ec} represents y^2=x^3+ec[0]x+ec[1].
1.2       noro     1493: If the characteristic of the current base field is 2,
1.5       noro     1494: then @var{ec} represents y^2+xy=x^3+ec[0]x^2+ec[1].
1.2       noro     1495: @item
                   1496: The point at infinity is represented by 0.
                   1497: @item
                   1498: If an argument denoting a point is a vector of length 3,
                   1499: then it is the projective coordinate. In such a case
                   1500: the third coordinate must not be 0.
                   1501: @item
                   1502: If the result is a vector of length 3, then the third coordinate
                   1503: is not equal to 0 but not necessarily 1. To get the result by
                   1504: the affine coordinate, the first and the second coordinates should
                   1505: be divided by the third coordinate.
                   1506: @item
                   1507: The check whether the arguments are on the curve is omitted.
                   1508: \E
1.1       noro     1509: @end itemize
                   1510:
                   1511: @example
                   1512: [0] setmod_ff(1125899906842679)$
                   1513: [1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
                   1514: [2] Pt1=newvect(3,[1,-412127497938252,1])$
                   1515: [3] Pt2=newvect(3,[6,-252647084363045,1])$
                   1516: [4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
                   1517: [ 560137044461222 184453736165476 125 ]
                   1518: [5] F=y^2-(x^3+EC[0]*x+EC[1])$
                   1519: [6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
                   1520: 0
                   1521: [7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
                   1522: 0
                   1523: [8] D=ecm_sub_ff(Pt3,Pt2,EC);
                   1524: [ 886545905133065 119584559149586 886545905133065 ]
                   1525: [9] D[0]/D[2]==Pt1[0]/Pt1[2];
                   1526: 1
                   1527: [10] D[1]/D[2]==Pt1[1]/Pt1[2];
                   1528: 1
                   1529: @end example
                   1530:
                   1531: @table @t
1.2       noro     1532: \JP @item $B;2>H(B
                   1533: \EG @item References
1.1       noro     1534: @fref{setmod_ff}
                   1535: @end table
                   1536: