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

1.5     ! noro        1: @comment $OpenXM: OpenXM/src/asir-doc/parts/ff.texi,v 1.4 2003/04/19 10:36:30 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::
                    335: * fctr_ff::
                    336: * irredcheck_ff::
                    337: * randpoly_ff::
                    338: * ecm_add_ff ecm_sub_ff ecm_chsgn_ff::
                    339: * extdeg_ff::
                    340: @end menu
                    341:
1.2       noro      342: \JP @node setmod_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    343: \EG @node setmod_ff,,, Functions for Finite fields
1.1       noro      344: @subsection @code{setmod_ff}
                    345: @findex setmod_ff
                    346:
                    347: @table @t
                    348: @item setmod_ff([@var{prime}|@var{poly}])
1.5     ! noro      349: @itemx setmod_ff(@var{prime},@var{n}])
1.2       noro      350: \JP :: $BM-8BBN$N@_Dj(B, $B@_Dj$5$l$F$$$kM-8BBN$NK!(B, $BDj5AB?9`<0$NI=<((B
                    351: \EG :: Sets/Gets the current base fields.
1.1       noro      352: @end table
                    353:
                    354: @table @var
                    355: @item return
1.2       noro      356: \JP $B?t$^$?$OB?9`<0(B
                    357: \EG number or polynomial
1.1       noro      358: @item prime
1.2       noro      359: \JP $BAG?t(B
                    360: \EG prime
1.1       noro      361: @item poly
1.2       noro      362: \JP GF(2) $B>e4{Ls$J(B 1 $BJQ?tB?9`<0(B
                    363: \EG univariate polynomial irreducible over GF(2)
1.5     ! noro      364: @item n
        !           365: \JP $B3HBg<!?t(B
        !           366: \EG the extension degree
1.1       noro      367: @end table
                    368:
                    369: @itemize @bullet
1.2       noro      370: \BJP
1.1       noro      371: @item
                    372: $B0z?t$,@5@0?t(B @var{prime} $B$N;~(B, GF(@var{prime}) $B$r4pACBN$H$7$F@_Dj$9$k(B.
                    373: @item
                    374: $B0z?t$,B?9`<0(B @var{poly} $B$N;~(B,
1.2       noro      375: GF(2^deg(@var{poly} mod 2)) = GF(2)[t]/(@var{poly}(t) mod 2)
1.1       noro      376: $B$r4pACBN$H$7$F@_Dj$9$k(B.
                    377: @item
1.5     ! noro      378: $B0z?t$,(B @var{p} $B$H(B @var{n} $B$N;~(B,
        !           379: 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
        !           380: $B$J$1$l$P$J$i$J$$(B. $B$^$?(B, @var{p} $B$,(B @var{2^14} $B0J>e$N$H$-(B,
        !           381: @var{n} $B$O(B 1 $B$G$J$1$l$P$J$i$J$$(B.
        !           382: @item
        !           383: $BL50z?t$N;~(B, $B@_Dj$5$l$F$$$k4pACBN$,(B GF(@var{prime})$B$N>l9g(B @var{prime},
        !           384: GF(2^@var{n}) $B$N>l9gDj5AB?9`<0$rJV$9(B.
        !           385: $B4pACBN$,(B GF(p^@var{n})
        !           386: (@var{p^n} $B$,(B @var{2^14} $BL$K~(B) $B$N>l9g(B,
        !           387: [@var{p},@var{defpoly},@var{prim_elem}] $B$rJV$9(B. $B$3$3$G(B, @var{defpoly}
        !           388: $B$O(B, @var{n} $B<!3HBg$NDj5AB?9`<0(B, @var{prim_elem} $B$O(B, GF(@var{p^n})
        !           389: $B>hK!72$N@8@.85$r0UL#$9$k(B.
1.1       noro      390: @item
1.5     ! noro      391: 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      392: $B1F6A$9$k$?$a(B, @code{defpoly_mod2()} $B$G@8@.$9$k$N$,$h$$(B.
1.2       noro      393: \E
                    394: \BEG
                    395: @item
                    396: If the argument is a non-negative integer @var{prime}, GF(@var{prime})
                    397: is set as the current base field.
                    398: @item
                    399: If the argument is a polynomial @var{poly},
                    400: GF(2^deg(@var{poly} mod 2)) = GF(2)[t]/(@var{poly}(t) mod2)
                    401: is set as the current base field.
                    402: @item
1.5     ! noro      403: If the arguments are a prime @var{p} and an extension degree @var{n},
        !           404: GF(@var{p^n}) is set as the current base field. @var{p^n} must be
        !           405: less than @var{2^29} and if @var{p} is greater than or equal to @var{2^14},
        !           406: then @var{n} must be equal to 1.
        !           407: @item
1.2       noro      408: If no argument is specified, the modulus indicating the current base field
                    409: is returned. If the current base field is GF(@var{prime}), @var{prime} is
1.5     ! noro      410: returned. If it is GF(2^@var{n}), the defining polynomial is returned.
        !           411: If it is GF(@var{p^n}), where @var{p^n} is less than @var{2^14},
        !           412: [@var{p},@var{defpoly},@var{prim_elem}] is returned. Here, @var{defpoly}
        !           413: is the defining polynomial of the @var{n}-th extension,
        !           414: and @var{prim_elem} is the generator of the multiplicative group
        !           415: of GF(@var{p^n}).
1.2       noro      416: @item
                    417: Any irreducible univariate polynomial over GF(2) is available to
1.5     ! noro      418: set GF(2^@var{n}). However the use of @code{defpoly_mod2()} is recommended
1.2       noro      419: for efficiency.
                    420: \E
1.1       noro      421: @end itemize
                    422:
                    423: @example
                    424: [174] defpoly_mod2(100);
                    425: x^100+x^15+1
                    426: [175] setmod_ff(@@@@);
                    427: x^100+x^15+1
                    428: [176] setmod_ff();
                    429: x^100+x^15+1
1.5     ! noro      430: [177] setmod_ff(2,5);
        !           431: [2,x^5+x^2+1,x]
1.1       noro      432: @end example
                    433:
                    434: @table @t
1.2       noro      435: \JP @item $B;2>H(B
                    436: \EG @item References
1.1       noro      437: @fref{defpoly_mod2}
                    438: @end table
                    439:
1.2       noro      440: \JP @node field_type_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    441: \EG @node field_type_ff,,, Functions for Finite fields
1.1       noro      442: @subsection @code{field_type_ff}
                    443: @findex field_type_ff
                    444:
                    445: @table @t
                    446: @item field_type_ff()
1.2       noro      447: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N<oN`(B
                    448: \EG :: Type of the current base field.
1.1       noro      449: @end table
                    450:
                    451: @table @var
                    452: @item return
1.2       noro      453: \JP $B@0?t(B
                    454: \EG integer
1.1       noro      455: @end table
                    456:
                    457: @itemize @bullet
1.2       noro      458: \BJP
1.1       noro      459: @item
                    460: $B@_Dj$5$l$F$$$k4pACBN$N<oN`$rJV$9(B.
                    461: @item
1.5     ! noro      462: $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      463: \E
                    464: \BEG
                    465: @item
                    466: Returns the type of the current base field.
                    467: @item
1.5     ! noro      468: If no field is set, 0 is returned. If GF(@var{p}) is set, 1 is returned.
        !           469: If GF(2^@var{n}) is set, 2 is returned.
1.2       noro      470: \E
1.1       noro      471: @end itemize
                    472:
                    473: @example
                    474: [0] field_type_ff();
                    475: 0
                    476: [1] setmod_ff(3);
                    477: 3
                    478: [2] field_type_ff();
                    479: 1
                    480: [3] setmod_ff(x^2+x+1);
                    481: x^2+x+1
                    482: [4] field_type_ff();
                    483: 2
                    484: @end example
                    485:
                    486: @table @t
1.2       noro      487: \JP @item $B;2>H(B
                    488: \EG @item References
1.1       noro      489: @fref{setmod_ff}
                    490: @end table
                    491:
1.2       noro      492: \JP @node field_order_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    493: \EG @node field_order_ff,,, Functions for Finite fields
1.1       noro      494: @subsection @code{field_order_ff}
                    495: @findex field_order_ff
                    496:
                    497: @table @t
                    498: @item field_order_ff()
1.2       noro      499: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B
                    500: \EG :: Order of the current base field.
1.1       noro      501: @end table
                    502:
                    503: @table @var
                    504: @item return
1.2       noro      505: \JP $B@0?t(B
                    506: \EG integer
1.1       noro      507: @end table
                    508:
                    509: @itemize @bullet
1.2       noro      510: \BJP
1.1       noro      511: @item
                    512: $B@_Dj$5$l$F$$$k4pACBN$N0L?t(B ($B85$N8D?t(B) $B$rJV$9(B.
                    513: @item
1.5     ! noro      514: $B@_Dj$5$l$F$$$kBN$,(B GF(@var{q}) $B$J$i$P(B q $B$rJV$9(B.
1.2       noro      515: \E
                    516: \BEG
                    517: @item
                    518: Returns the order of the current base field.
                    519: @item
1.5     ! noro      520: @var{q} is returned if the current base field is GF(@var{q}).
1.2       noro      521: \E
1.1       noro      522: @end itemize
                    523:
                    524: @example
                    525: [0] field_order_ff();
                    526: field_order_ff : current_ff is not set
                    527: return to toplevel
                    528: [0] setmod_ff(3);
                    529: 3
                    530: [1] field_order_ff();
                    531: 3
                    532: [2] setmod_ff(x^2+x+1);
                    533: x^2+x+1
                    534: [3] field_order_ff();
                    535: 4
                    536: @end example
                    537:
                    538: @table @t
1.2       noro      539: \JP @item $B;2>H(B
                    540: \EG @item References
1.1       noro      541: @fref{setmod_ff}
                    542: @end table
                    543:
1.2       noro      544: \JP @node characteristic_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    545: \EG @node characteristic_ff,,, Functions for Finite fields
1.1       noro      546: @subsection @code{characteristic_ff}
                    547: @findex characteristic_ff
                    548:
                    549: @table @t
                    550: @item characteristic_ff()
1.2       noro      551: \JP :: $B@_Dj$5$l$F$$$kBN$NI8?t(B
                    552: \EG :: Characteristic of the current base field.
1.1       noro      553: @end table
                    554:
                    555: @table @var
                    556: @item return
1.2       noro      557: \JP $B@0?t(B
                    558: \EG integer
1.1       noro      559: @end table
                    560:
                    561: @itemize @bullet
1.2       noro      562: \BJP
1.1       noro      563: @item
                    564: $B@_Dj$5$l$F$$$kBN$NI8?t$rJV$9(B.
                    565: @item
1.5     ! noro      566: 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      567: \E
                    568: \BEG
                    569: @item
                    570: Returns the characteristic of the current base field.
                    571: @item
1.5     ! noro      572: @var{p} is returned if GF(@var{p}), where @var{p} is a prime, is set.
        !           573: @var{2} is returned if GF(2^@var{n}) is set.
1.2       noro      574: \E
1.1       noro      575: @end itemize
                    576:
                    577: @example
                    578: [0] characteristic_ff();
                    579: characteristic_ff : current_ff is not set
                    580: return to toplevel
                    581: [0] setmod_ff(3);
                    582: 3
                    583: [1] characteristic_ff();
                    584: 3
                    585: [2] setmod_ff(x^2+x+1);
                    586: x^2+x+1
                    587: [3] characteristic_ff();
                    588: 2
                    589: @end example
                    590:
                    591: @table @t
1.2       noro      592: \JP @item $B;2>H(B
                    593: \EG @item References
1.1       noro      594: @fref{setmod_ff}
                    595: @end table
                    596:
1.2       noro      597: \JP @node extdeg_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    598: \EG @node extdeg_ff,,, Functions for Finite fields
1.1       noro      599: @subsection @code{extdeg_ff}
                    600: @findex extdeg_ff
                    601:
                    602: @table @t
                    603: @item extdeg_ff()
1.2       noro      604: \JP :: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t(B
                    605: \EG :: Extension degree of the current base field over the prime field.
1.1       noro      606: @end table
                    607:
                    608: @table @var
                    609: @item return
1.2       noro      610: \JP $B@0?t(B
                    611: \EG integer
1.1       noro      612: @end table
                    613:
                    614: @itemize @bullet
1.2       noro      615: \BJP
1.1       noro      616: @item
                    617: $B@_Dj$5$l$F$$$k4pACBN$N(B, $BAGBN$KBP$9$k3HBg<!?t$rJV$9(B.
                    618: @item
1.5     ! noro      619: 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      620: \E
                    621: \BEG
                    622: @item
                    623: Returns the extension degree of the current base field over the prime field.
                    624: @item
1.5     ! noro      625: 1 is returned if GF(@var{p}), where @var{p} is a prime, is set.
        !           626: @var{n} is returned if GF(2^@var{n}) is set.
1.2       noro      627: \E
1.1       noro      628: @end itemize
                    629:
                    630: @example
                    631: [0] extdeg_ff();
                    632: extdeg_ff : current_ff is not set
                    633: return to toplevel
                    634: [0] setmod_ff(3);
                    635: 3
                    636: [1] extdeg_ff();
                    637: 1
                    638: [2] setmod_ff(x^2+x+1);
                    639: x^2+x+1
                    640: [3] extdeg_ff();
                    641: 2
                    642: @end example
                    643:
                    644: @table @t
1.2       noro      645: \JP @item $B;2>H(B
                    646: \EG @item References
1.1       noro      647: @fref{setmod_ff}
                    648: @end table
                    649:
1.2       noro      650: \JP @node simp_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    651: \EG @node simp_ff,,, Functions for Finite fields
1.1       noro      652: @subsection @code{simp_ff}
                    653: @findex simp_ff
                    654:
                    655: @table @t
                    656: @item simp_ff(@var{obj})
1.2       noro      657: \JP :: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49(B
                    658: \BEG
                    659: :: Converts numbers or coefficients of polynomials into elements
                    660: in finite fields.
                    661: \E
1.1       noro      662: @end table
                    663:
                    664: @table @var
                    665: @item return
1.2       noro      666: \JP $B?t$^$?$OB?9`<0(B
                    667: \EG number or polynomial
1.1       noro      668: @item obj
1.2       noro      669: \JP $B?t$^$?$OB?9`<0(B
                    670: \EG number or polynomial
1.1       noro      671: @end table
                    672:
                    673: @itemize @bullet
1.2       noro      674: \BJP
1.1       noro      675: @item
                    676: $B?t(B, $B$"$k$$$OB?9`<0$N78?t$rM-8BBN$N85$KJQ49$9$k(B.
                    677: @item
                    678: $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
                    679: $BMQ$$$k(B.
                    680: @item
                    681: $BM-8BBN$N85$KBP$7(B, $BK!$"$k$$$ODj5AB?9`<0$K$h$k(B reduction $B$r9T$&>l9g$K$b(B
                    682: $BMQ$$$k(B.
1.5     ! noro      683: @item
        !           684: $B>.I8?tM-8BBN$N85$KJQ49$9$k>l9g(B, $B0lC6AGBN>e$K<M1F$7$F$+$i(B, $B3HBgBN$N(B
        !           685: $B85$KJQ49$5$l$k(B. $B3HBgBN$N85$KD>@\JQ49$9$k$K$O(B @code{ptosfp()} $B$r(B
        !           686: $BMQ$$$k(B.
1.2       noro      687: \E
                    688: \BEG
                    689: @item
                    690: Converts numbers or coefficients of polynomials into elements in finite
                    691: fields.
                    692: @item
                    693: It is used to convert integers or intrgral polynomials int
                    694: elements of finite fields or polynomials over finite fields.
                    695: @item
                    696: An element of a finite field may not have the reduced representation.
1.5     ! noro      697: In such case an application of @code{simp_ff} ensures that the output has
1.2       noro      698: the reduced representation.
1.5     ! noro      699: If a small finite field is set as a ground field,
        !           700: an integer is projected the finite prime field, then
        !           701: it is embedded into the ground field. @code{ptosfp()}
        !           702: can be used for direct projection to the ground field.
1.2       noro      703: \E
1.1       noro      704: @end itemize
                    705:
                    706: @example
                    707: [0] simp_ff((x+1)^10);
                    708: 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
                    709: [1] setmod_ff(3);
                    710: 3
                    711: [2] simp_ff((x+1)^10);
                    712: 1*x^10+1*x^9+1*x+1
                    713: [3] ntype(coef(@@@@,10));
                    714: 6
1.5     ! noro      715: [4] setmod_ff(2,3);
        !           716: [2,x^3+x+1,x]
        !           717: [5] simp_ff(1);
        !           718: @@_0
        !           719: [6] simp_ff(2);
        !           720: 0
        !           721: [7] ptosfp(2);
        !           722: @@_1
1.1       noro      723: @end example
                    724:
                    725: @table @t
1.2       noro      726: \JP @item $B;2>H(B
                    727: \EG @item References
1.5     ! noro      728: @fref{setmod_ff}, @fref{lmptop}, @fref{gf2nton}, @fref{ptosfp sfptop}
1.1       noro      729: @end table
                    730:
1.2       noro      731: \JP @node random_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    732: \EG @node random_ff,,, Functions for Finite fields
1.1       noro      733: @subsection @code{random_ff}
                    734: @findex random_ff
                    735:
                    736: @table @t
                    737: @item random_ff()
1.2       noro      738: \JP :: $BM-8BBN$N85$NMp?t@8@.(B
                    739: \EG :: Random generation of an element of a finite field.
1.1       noro      740: @end table
                    741:
                    742: @table @var
                    743: @item return
1.2       noro      744: \JP $BM-8BBN$N85(B
                    745: \EG element of a finite field
1.1       noro      746: @end table
                    747:
                    748: @itemize @bullet
1.2       noro      749: \BJP
1.1       noro      750: @item
                    751: $BM-8BBN$N85$rMp?t@8@.$9$k(B.
                    752: @item
1.2       noro      753: @code{random()}, @code{lrandom()} $B$HF1$8(B 32bit $BMp?tH/@84o$r;HMQ$7$F$$$k(B.
                    754: \E
                    755: \BEG
                    756: @item
                    757: Generates an element of the current base field randomly.
1.1       noro      758: @item
1.2       noro      759: The same random generator as in @code{random()}, @code{lrandom()}
                    760: is used.
                    761: \E
1.1       noro      762: @end itemize
                    763:
                    764: @example
                    765: [0] random_ff();
                    766: random_ff : current_ff is not set
                    767: return to toplevel
                    768: [0] setmod_ff(pari(nextprime,2^40));
                    769: 1099511627791
                    770: [1] random_ff();
                    771: 561856154357
                    772: [2] random_ff();
                    773: 45141628299
                    774: @end example
                    775:
                    776: @table @t
1.2       noro      777: \JP @item $B;2>H(B
                    778: \EG @item References
1.1       noro      779: @fref{setmod_ff}, @fref{random}, @fref{lrandom}
                    780: @end table
                    781:
1.2       noro      782: \JP @node lmptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    783: \EG @node lmptop,,, Functions for Finite fields
1.1       noro      784: @subsection @code{lmptop}
                    785: @findex lmptop
                    786:
                    787: @table @t
                    788: @item lmptop(@var{obj})
1.5     ! noro      789: \JP :: GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49(B
        !           790: \EG :: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
1.1       noro      791: @end table
                    792:
                    793: @table @var
                    794: @item return
1.2       noro      795: \JP $B@0?t78?tB?9`<0(B
                    796: \EG integral polynomial
1.1       noro      797: @item obj
1.5     ! noro      798: \JP GF(@var{p}) $B78?tB?9`<0(B
        !           799: \EG polynomial over GF(@var{p})
1.1       noro      800: @end table
                    801:
                    802: @itemize @bullet
1.2       noro      803: \BJP
1.1       noro      804: @item
1.5     ! noro      805: GF(@var{p}) $B78?tB?9`<0$N78?t$r@0?t$KJQ49$9$k(B.
1.1       noro      806: @item
1.5     ! noro      807: 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      808: $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
                    809: $BJQ49$5$l$k(B.
1.2       noro      810: \E
                    811: \BEG
                    812: @item
1.5     ! noro      813: Converts the coefficients of a polynomial over GF(@var{p}) into integers.
1.1       noro      814: @item
1.5     ! noro      815: An element of GF(@var{p}) is represented by a non-negative integer @var{r} less than
1.2       noro      816: @var{p}.
                    817: Each coefficient of a polynomial is converted into an integer object
                    818: whose value is @var{r}.
                    819: \E
1.1       noro      820: @end itemize
                    821:
                    822: @example
                    823: [0] setmod_ff(pari(nextprime,2^40));
                    824: 1099511627791
                    825: [1] F=simp_ff((x-1)^10);
                    826: 1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
                    827: +1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
                    828: [2] setmod_ff(547);
                    829: 547
                    830: [3] F=simp_ff((x-1)^10);
                    831: 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
                    832: [4] lmptop(F);
                    833: 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
                    834: [5] lmptop(coef(F,1));
                    835: 537
                    836: [6] ntype(@@@@);
                    837: 0
                    838: @end example
                    839:
                    840: @table @t
1.2       noro      841: \JP @item $B;2>H(B
                    842: \EG @item References
1.1       noro      843: @fref{simp_ff}
                    844: @end table
                    845:
1.2       noro      846: \JP @node ntogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    847: \EG @node ntogf2n,,, Functions for Finite fields
1.1       noro      848: @subsection @code{ntogf2n}
                    849: @findex ntogf2n
                    850:
                    851: @table @t
                    852: @item ntogf2n(@var{m})
1.5     ! noro      853: \JP :: $B<+A3?t$r(B GF(2^@var{n}) $B$N85$KJQ49(B
        !           854: \EG :: Converts a non-negative integer into an element of GF(2^@var{n}).
1.1       noro      855: @end table
                    856:
                    857: @table @var
                    858: @item return
1.5     ! noro      859: \JP GF(2^@var{n}) $B$N85(B
        !           860: \EG element of GF(2^@var{n})
1.1       noro      861: @item m
1.2       noro      862: \JP $BHsIi@0?t(B
                    863: \EG non-negative integer
1.1       noro      864: @end table
                    865:
                    866: @itemize @bullet
1.2       noro      867: \BJP
1.1       noro      868: @item
                    869: $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      870: $B$KBP$7(B, GF(2^@var{n})=GF(2)[t]/(g(t)) $B$N85(B
1.1       noro      871: @var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t) $B$rJV$9(B.
                    872: @item
                    873: $BDj5AB?9`<0$K$h$k>jM>$O<+F0E*$K$O7W;;$5$l$J$$$?$a(B, @code{simp_ff()} $B$r(B
                    874: $BE,MQ$9$kI,MW$,$"$k(B.
1.2       noro      875: \E
                    876: \BEG
                    877: @item
                    878: Let @var{m} be a non-negative integer.
                    879: @var{m} has the binary representation
                    880: @var{m}=@var{m0}+@var{m1}*2+...+@var{mk}*2^k.
1.5     ! noro      881: This function returns an element of  GF(2^@var{n})=GF(2)[t]/(g(t)),
1.2       noro      882: @var{m0}+@var{m1}*t+...+@var{mk}*t^k mod g(t).
                    883: @item
                    884: Apply @code{simp_ff()} to reduce the result.
                    885: \E
1.1       noro      886: @end itemize
                    887:
                    888: @example
                    889: [1] setmod_ff(x^30+x+1);
                    890: x^30+x+1
                    891: [2] N=ntogf2n(2^100);
                    892: (@@^100)
                    893: [3] simp_ff(N);
                    894: (@@^13+@@^12+@@^11+@@^10)
                    895: @end example
                    896:
                    897: @table @t
1.2       noro      898: \JP @item $B;2>H(B
                    899: \EG @item References
1.1       noro      900: @fref{gf2nton}
                    901: @end table
                    902:
1.2       noro      903: \JP @node gf2nton,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    904: \EG @node gf2nton,,, Functions for Finite fields
1.1       noro      905: @subsection @code{gf2nton}
                    906: @findex gf2nton
                    907:
                    908: @table @t
                    909: @item gf2nton(@var{m})
1.5     ! noro      910: \JP :: GF(2^@var{n}) $B$N85$r<+A3?t$KJQ49(B
        !           911: \EG :: Converts an element of GF(2^@var{n}) into a non-negative integer.
1.1       noro      912: @end table
                    913:
                    914: @table @var
                    915: @item return
1.2       noro      916: \JP $BHsIi@0?t(B
                    917: \EG non-negative integer
1.1       noro      918: @item m
1.5     ! noro      919: \JP GF(2^@var{n}) $B$N85(B
        !           920: \EG element of GF(2^@var{n})
1.1       noro      921: @end table
                    922:
                    923: @itemize @bullet
                    924: @item
1.2       noro      925: \JP @code{gf2nton} $B$N5UJQ49$G$"$k(B.
                    926: \EG The inverse of @code{gf2nton}.
1.1       noro      927: @end itemize
                    928:
                    929: @example
                    930: [1] setmod_ff(x^30+x+1);
                    931: x^30+x+1
                    932: [2] N=gf2nton(2^100);
                    933: (@@^100)
                    934: [3] simp_ff(N);
                    935: (@@^13+@@^12+@@^11+@@^10)
                    936: [4] gf2nton(N);
                    937: 1267650600228229401496703205376
                    938: [5] gf2nton(simp_ff(N));
                    939: 15360
                    940: @end example
                    941:
                    942: @table @t
1.2       noro      943: \JP @item $B;2>H(B
                    944: \EG @item References
1.1       noro      945: @fref{gf2nton}
                    946: @end table
                    947:
1.2       noro      948: \JP @node ptogf2n,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    949: \EG @node ptogf2n,,, Functions for Finite fields
1.1       noro      950: @subsection @code{ptogf2n}
                    951: @findex ptogf2n
                    952:
                    953: @table @t
                    954: @item ptogf2n(@var{poly})
1.5     ! noro      955: \JP :: $B0lJQ?tB?9`<0$r(B GF(2^@var{n}) $B$N85$KJQ49(B
        !           956: \EG :: Converts a univariate polynomial into an element of GF(2^@var{n}).
1.1       noro      957: @end table
                    958:
                    959: @table @var
                    960: @item return
1.5     ! noro      961: \JP GF(2^@var{n}) $B$N85(B
        !           962: \EG element of GF(2^@var{n})
1.1       noro      963: @item poly
1.2       noro      964: \JP $B0lJQ?tB?9`<0(B
                    965: \EG univariate polynomial
1.1       noro      966: @end table
                    967:
                    968: @itemize @bullet
                    969: @item
1.2       noro      970: \BJP
1.5     ! noro      971: @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      972: $BJQ49$5$l$k(B.
                    973: @var{poly} $B$NJQ?t$K(B @code{@@} $B$rBeF~$7$?7k2L$HEy$7$$(B.
1.2       noro      974: \E
                    975: \BEG
1.5     ! noro      976: Generates an element of GF(2^@var{n}) represented by @var{poly}.
1.2       noro      977: The coefficients are reduced modulo 2.
                    978: The output is equal to the result by substituting @code{@@} for
                    979: the variable of @var{poly}.
                    980: \E
1.1       noro      981: @end itemize
                    982:
                    983: @example
                    984: [1] setmod_ff(x^30+x+1);
                    985: x^30+x+1
                    986: [2] ptogf2n(x^100);
                    987: (@@^100)
                    988: @end example
                    989:
                    990: @table @t
1.2       noro      991: \JP @item $B;2>H(B
                    992: \EG @item References
1.1       noro      993: @fref{gf2ntop}
                    994: @end table
                    995:
1.2       noro      996: \JP @node gf2ntop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                    997: \EG @node gf2ntop,,, Functions for Finite fields
1.1       noro      998: @subsection @code{gf2ntop}
                    999: @findex gf2ntop
                   1000:
                   1001: @table @t
                   1002: @item gf2ntop(@var{m}[,@var{v}])
1.5     ! noro     1003: \JP :: GF(2^@var{n}) $B$N85$rB?9`<0$KJQ49(B
        !          1004: \EG :: Converts an element of GF(2^@var{n}) into a polynomial.
1.1       noro     1005: @end table
                   1006:
                   1007: @table @var
                   1008: @item return
1.2       noro     1009: \JP $B0lJQ?tB?9`<0(B
                   1010: \EG univariate polynomial
1.1       noro     1011: @item m
1.5     ! noro     1012: \JP GF(2^@var{n}) $B$N85(B
        !          1013: \EG an element of GF(2^@var{n})
1.1       noro     1014: @item v
1.2       noro     1015: \JP $BITDj85(B
                   1016: \EG indeterminate
1.1       noro     1017: @end table
                   1018:
                   1019: @itemize @bullet
1.2       noro     1020: \BJP
1.1       noro     1021: @item
                   1022: @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     1023: @item
                   1024: @var{v} $B$N;XDj$,$J$$>l9g(B, $BD>A0$N(B @code{ptogf2n()} $B8F$S=P$7(B
1.1       noro     1025: $B$K$*$1$k0z?t$NJQ?t(B ($B%G%U%)%k%H$O(B @code{x}), $B;XDj$,$"$k>l9g$K$O(B
                   1026: $B;XDj$5$l$?ITDj85$rJQ?t$H$9$kB?9`<0$rJV$9(B.
1.2       noro     1027: \E
                   1028: \BEG
                   1029: @item
                   1030: Returns a polynomial representing @var{m}.
                   1031: @item
                   1032: If @var{v} is used as the variable of the output.
                   1033: If @var{v} is not specified, the variable of the argument
                   1034: of the latest @code{ptogf2n()} call. The default variable is @code{x}.
                   1035: \E
1.1       noro     1036: @end itemize
                   1037:
                   1038: @example
                   1039: [1] setmod_ff(x^30+x+1);
                   1040: x^30+x+1
                   1041: [2] N=simp_ff(gf2ntop(2^100));
                   1042: (@@^13+@@^12+@@^11+@@^10)
                   1043: [5] gf2ntop(N);
                   1044: [207] gf2ntop(N);
                   1045: x^13+x^12+x^11+x^10
                   1046: [208] gf2ntop(N,t);
                   1047: t^13+t^12+t^11+t^10
                   1048: @end example
                   1049:
                   1050: @table @t
1.2       noro     1051: \JP @item $B;2>H(B
                   1052: \EG @item References
1.1       noro     1053: @fref{ptogf2n}
                   1054: @end table
                   1055:
1.5     ! noro     1056: \JP @node ptosfp sfptop,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
        !          1057: \EG @node ptosfp sfptop,,, Functions for Finite fields
        !          1058: @subsection @code{ptosfp}, @code{sfptop}
        !          1059: @findex ptosfp
        !          1060: @findex sfptop
        !          1061:
        !          1062: @table @t
        !          1063: @item ptosfp(@var{p})
        !          1064: @itemx sfptop(@var{p})
        !          1065: \JP :: $B>.I8?tM-8BBN$X$NJQ49(B, $B5UJQ49(B
        !          1066: \EG :: Transformation to/from a small finite field
        !          1067: @end table
        !          1068:
        !          1069: @table @var
        !          1070: @item return
        !          1071: \JP $BB?9`<0(B
        !          1072: \EG polynomial
        !          1073: @item p
        !          1074: \JP $BB?9`<0(B
        !          1075: \EG polynomial
        !          1076: @end table
        !          1077:
        !          1078: @itemize @bullet
        !          1079: \BJP
        !          1080: @item
        !          1081: @code{ptosfp()} $B$O(B, $BB?9`<0$N78?t$r(B, $B8=:_@_Dj$5$l$F$$$k>.I8?tM-8BBN(B
        !          1082: GF(p^@var{n}) $B$N85$KD>@\JQ49$9$k(B. $B78?t$,4{$KM-8BBN$N85$N>l9g$OJQ2=$7$J$$(B.
        !          1083: $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}
        !          1084: $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.
        !          1085: $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
        !          1086: $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
        !          1087: $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
        !          1088: $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,
        !          1089: @var{@@_17} $B$HJQ49$5$l$k(B.
        !          1090: @item
        !          1091: @code{sfptop()} $B$O(B @code{ptosfp()} $B$N5UJQ49$G$"$k(B.
        !          1092: \E
        !          1093: \BEG
        !          1094: @item
        !          1095: @code{ptosfp()} converts coefficients of a polynomial to
        !          1096: elements in a small finite field GF(@var{p^n}) set as a ground field.
        !          1097: If a coefficient is already an element of the field,
        !          1098: no conversion is done. If a coefficient is a positive integer,
        !          1099: then its residue modulo @var{p^n} is expanded as @var{p}-adic integer,
        !          1100: then @var{p} is substituted by @var{x}, finally the polynomial
        !          1101: is converted to its correspoding logarithmic representation
        !          1102: with respect to the primitive element.
        !          1103: For example, GF(3^5) is represented as F(3)[@var{x}]/(@var{x^5+2*x+1}),
        !          1104: and each element of the field is represented as @var{@@_k}
        !          1105: by its exponent @var{k} with respect to the primitive element @var{x}.
        !          1106: @var{23 = 2*3^2+3+2} is represented as @var{2*x^2+x+2} and
        !          1107: it is equivalent to @var{x^17} modulo @var{x^5+2*x+1}.
        !          1108: Therefore an integer @var{23} is conterted to @var{@@_17}.
        !          1109: @item
        !          1110: @code{sfptop()} is the inverse of @code{ptosfp()}.
        !          1111: \E
        !          1112: @end itemize
        !          1113:
        !          1114: @example
        !          1115: [196] setmod_ff(3,5);
        !          1116: [3,x^5+2*x+1,x]
        !          1117: [197] A = ptosfp(23);
        !          1118: @@_17
        !          1119: [198] 9*2+3+2;
        !          1120: 23
        !          1121: [199] x^17-(2*x^2+x+2);
        !          1122: x^17-2*x^2-x-2
        !          1123: [200] sremm(@@,x^5+2*x+1,3);
        !          1124: 0
        !          1125: [201] sfptop(A);
        !          1126: 23
        !          1127: @end example
        !          1128:
        !          1129: @table @t
        !          1130: \JP @item $B;2>H(B
        !          1131: \EG @item References
        !          1132: @fref{setmod_ff}, @fref{simp_ff}
        !          1133: @end table
1.2       noro     1134: \JP @node defpoly_mod2,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1135: \EG @node defpoly_mod2,,, Functions for Finite fields
1.1       noro     1136: @subsection @code{defpoly_mod2}
                   1137: @findex defpoly_mod2
                   1138:
                   1139: @table @t
                   1140: @item defpoly_mod2(@var{d})
1.2       noro     1141: \JP :: GF(2) $B>e4{Ls$J0lJQ?tB?9`<0$N@8@.(B
                   1142: \EG :: Generates an irreducible univariate polynomial over GF(2).
1.1       noro     1143: @end table
                   1144:
                   1145: @table @var
                   1146: @item return
1.2       noro     1147: \JP $BB?9`<0(B
                   1148: \EG univariate polynomial
1.1       noro     1149: @item d
1.2       noro     1150: \JP $B@5@0?t(B
                   1151: \EG positive integer
1.1       noro     1152: @end table
                   1153:
                   1154: @itemize @bullet
1.2       noro     1155: \BJP
1.1       noro     1156: @item
                   1157: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1158: @item
                   1159: $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.
                   1160: @item
                   1161: $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
                   1162: 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,
                   1163: $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
                   1164: $B>.$5$$$b$N$rJV$9(B.
1.2       noro     1165: \E
                   1166: \BEG
                   1167: @item
                   1168: Defined in @samp{fff}.
                   1169: @item
                   1170: An irreducible univariate polynomial of degree @var{d} is returned.
                   1171: @item
                   1172: If an irreducible trinomial @var{x^d+x^m+1} exists, then the one
                   1173: with the smallest @var{m} is returned.
                   1174: Otherwise, an irreducible pentanomial @var{x^d+x^m1+x^m2+x^m3+1}
                   1175: (@var{m1>m2>m3} is returned.
                   1176: @var{m1}, @var{m2} and @var{m3} are determined as follows:
                   1177: Fix @var{m1} as small as possible. Then fix @var{m2} as small as possible.
                   1178: Then fix @var{m3} as small as possible.
                   1179: \E
1.1       noro     1180: @end itemize
                   1181:
                   1182: @example
                   1183: @end example
                   1184:
                   1185: @table @t
1.2       noro     1186: \JP @item $B;2>H(B
                   1187: \EG @item References
1.1       noro     1188: @fref{setmod_ff}
                   1189: @end table
                   1190:
1.2       noro     1191: \JP @node fctr_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1192: \EG @node fctr_ff,,, Functions for Finite fields
1.1       noro     1193: @subsection @code{fctr_ff}
                   1194: @findex fctr_ff
                   1195:
                   1196: @table @t
                   1197: @item fctr_ff(@var{poly})
1.2       noro     1198: \JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsJ,2r(B
                   1199: \EG :: Irreducible univariate factorization over a finite field.
1.1       noro     1200: @end table
                   1201:
                   1202: @table @var
                   1203: @item return
1.2       noro     1204: \JP $B%j%9%H(B
                   1205: \EG list
1.1       noro     1206: @item poly
1.2       noro     1207: \JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
                   1208: \EG univariate polynomial over a finite field
1.1       noro     1209: @end table
                   1210:
                   1211: @itemize @bullet
1.2       noro     1212: \BJP
1.1       noro     1213: @item
                   1214: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1215: @item
                   1216: $B0lJQ?tB?9`<0$r(B, $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G4{LsJ,2r$9$k(B.
                   1217: @item
                   1218: $B7k2L$O(B, [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...] $B$J$k(B
                   1219: $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
                   1220: $B=EJ#EY$G$"$k(B.
                   1221: @item
                   1222: @var{poly} $B$N<g78?t$O<N$F$i$l$k(B.
1.2       noro     1223: \E
                   1224: \BEG
                   1225: @item
                   1226: Defined in @samp{fff}.
                   1227: @item
                   1228: Factorize @var{poly} into irreducible factors over the current base field.
                   1229: @item
                   1230: The result is a list [[@var{f1},@var{m1}],[@var{f2},@var{m2}],...],
                   1231: where @var{fi} is a monic irreducible factor and @var{mi} is its
                   1232: multiplicity.
                   1233: @item
                   1234: The leading coefficient of @var{poly} is abandoned.
                   1235: \E
1.1       noro     1236: @end itemize
                   1237:
                   1238: @example
                   1239: [178] setmod_ff(2^64-95);
                   1240: 18446744073709551521
                   1241: [179]  fctr_ff(x^5+x+1);
                   1242: [[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
                   1243: [1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]
                   1244: @end example
                   1245:
                   1246: @table @t
1.2       noro     1247: \JP @item $B;2>H(B
                   1248: \EG @item References
1.1       noro     1249: @fref{setmod_ff}
                   1250: @end table
                   1251:
1.2       noro     1252: \JP @node irredcheck_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1253: \EG @node irredcheck_ff,,, Functions for Finite fields
1.1       noro     1254: @subsection @code{irredcheck_ff}
                   1255: @findex irredcheck_ff
                   1256:
                   1257: @table @t
                   1258: @item irredcheck_ff(@var{poly})
1.2       noro     1259: \JP :: 1 $BJQ?tB?9`<0$NM-8BBN>e$G$N4{LsH=Dj(B
                   1260: \EG :: Primality check of a univariate polynomial over a finite field.
1.1       noro     1261: @end table
                   1262:
                   1263: @table @var
                   1264: @item return
                   1265: 0|1
                   1266: @item poly
1.2       noro     1267: \JP $BM-8BBN>e$N(B 1 $BJQ?tB?9`<0(B
                   1268: \EG univariate polynomial over a finite field
1.1       noro     1269: @end table
                   1270:
                   1271: @itemize @bullet
1.2       noro     1272: \BJP
1.1       noro     1273: @item
                   1274: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1275: @item
                   1276: $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     1277: \E
                   1278: \BEG
                   1279: @item
                   1280: Defined in @samp{fff}.
                   1281: @item
                   1282: Returns 1 if @var{poly} is irreducible over the current base field.
                   1283: Returns 0 otherwise.
                   1284: \E
1.1       noro     1285: @end itemize
                   1286:
                   1287: @example
                   1288: [178] setmod_ff(2^64-95);
                   1289: 18446744073709551521
                   1290: [179] ] F=x^10+random_ff();
                   1291: x^10+14687973587364016969
                   1292: [180] irredcheck_ff(F);
                   1293: 1
                   1294: @end example
                   1295:
                   1296: @table @t
1.2       noro     1297: \JP @item $B;2>H(B
                   1298: \EG @item References
1.1       noro     1299: @fref{setmod_ff}
                   1300: @end table
                   1301:
1.2       noro     1302: \JP @node randpoly_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1303: \EG @node randpoly_ff,,, Functions for Finite fields
1.1       noro     1304: @subsection @code{randpoly_ff}
                   1305: @findex randpoly_ff
                   1306:
                   1307: @table @t
                   1308: @item randpoly_ff(@var{d},@var{v})
1.2       noro     1309: \JP :: $BM-8BBN>e$N(B $BMp?t78?t(B 1 $BJQ?tB?9`<0$N@8@.(B
                   1310: \EG :: Generation of a random univariate polynomial over a finite field.
1.1       noro     1311: @end table
                   1312:
                   1313: @table @var
                   1314: @item return
1.2       noro     1315: \JP $BB?9`<0(B
                   1316: \EG polynomial
1.1       noro     1317: @item d
1.2       noro     1318: \JP $B@5@0?t(B
                   1319: \EG positive integer
1.1       noro     1320: @item v
1.2       noro     1321: \JP $BITDj85(B
                   1322: \EG indeterminate
1.1       noro     1323: @end table
                   1324:
                   1325: @itemize @bullet
1.2       noro     1326: \BJP
1.1       noro     1327: @item
                   1328: @samp{fff} $B$GDj5A$5$l$F$$$k(B.
                   1329: @item
                   1330: @var{d} $B<!L$K~(B, $BJQ?t$,(B @var{v}, $B78?t$,8=:_@_Dj$5$l$F$$$kM-8BBN$KB0$9$k(B
                   1331: 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     1332: \E
                   1333: \BEG
                   1334: @item
                   1335: Defined in @samp{fff}.
                   1336: @item
                   1337: Generates a polynomial of @var{v} such that the degree is less than @var{d}
                   1338: and the coefficients are in the current base field.
                   1339: The coefficients are generated by @code{random_ff()}.
                   1340: \E
1.1       noro     1341: @end itemize
                   1342:
                   1343: @example
                   1344: [178] setmod_ff(2^64-95);
                   1345: 18446744073709551521
                   1346: [179] ] F=x^10+random_ff();
                   1347: [180] randpoly_ff(3,x);
                   1348: 17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
                   1349: [181] randpoly_ff(3,x);
                   1350: 7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
                   1351: [182] randpoly_ff(3,x);
                   1352: 10247781277095450395*x^2+10243690944992524936*x+4063829049268845492
                   1353: @end example
                   1354:
                   1355: @table @t
1.2       noro     1356: \JP @item $B;2>H(B
                   1357: \EG @item References
1.1       noro     1358: @fref{setmod_ff}, @fref{random_ff}
                   1359: @end table
                   1360:
1.2       noro     1361: \JP @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, $BM-8BBN$K4X$9$kH!?t$N$^$H$a(B
                   1362: \EG @node ecm_add_ff ecm_sub_ff ecm_chsgn_ff,,, Functions for Finite fields
1.1       noro     1363: @subsection @code{ecm_add_ff}, @code{ecm_sub_ff}, @code{ecm_chsgn_ff}
                   1364: @findex ecm_add_ff
                   1365: @findex ecm_sub_ff
                   1366: @findex ecm_chsgn_ff
                   1367:
                   1368: @table @t
                   1369: @item ecm_add_ff(@var{p1},@var{p2},@var{ec})
                   1370: @itemx ecm_sub_ff(@var{p1},@var{p2},@var{ec})
1.3       noro     1371: @itemx ecm_chsgn_ff(@var{p1})
1.2       noro     1372: \JP :: $BBJ1_6J@~>e$NE@$N2C;;(B, $B8:;;(B, $B5U85(B
                   1373: \EG :: Addition, Subtraction and additive inverse for points on an elliptic curve.
1.1       noro     1374: @end table
                   1375:
                   1376: @table @var
                   1377: @item return
1.2       noro     1378: \JP $B%Y%/%H%k$^$?$O(B 0
                   1379: \EG vector or 0
1.5     ! noro     1380: @item p1 p2
1.2       noro     1381: \JP $BD9$5(B 3 $B$N%Y%/%H%k$^$?$O(B 0
                   1382: \EG vector of length 3 or 0
1.1       noro     1383: @item ec
1.2       noro     1384: \JP $BD9$5(B 2 $B$N%Y%/%H%k(B
                   1385: \EG vector of length 2
1.1       noro     1386: @end table
                   1387:
                   1388: @itemize @bullet
1.2       noro     1389: \BJP
1.1       noro     1390: @item
                   1391: $B8=:_@_Dj$5$l$F$$$kM-8BBN>e$G(B,  @var{ec} $B$GDj5A$5$l$kBJ1_6J@~>e$N(B
                   1392: $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.
                   1393: @item
                   1394: @var{ec} $B$O(B, $B@_Dj$5$l$F$$$kM-8BBN$,4qI8?tAGBN$N>l9g(B,
1.5     ! noro     1395: 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     1396: $B$rI=$9(B.
                   1397: @item
                   1398: $B0z?t(B, $B7k2L$H$b$K(B, $BL58B1sE@$O(B 0 $B$GI=$5$l$k(B.
                   1399: @item
                   1400: @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
                   1401: $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.
                   1402: @item
                   1403: $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.
                   1404: $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
                   1405: $B$G3d$kI,MW$,$"$k(B.
                   1406: @item
                   1407: @var{p1}, @var{p2} $B$,BJ1_6J@~>e$NE@$+$I$&$+$N%A%'%C%/$O$7$J$$(B.
1.2       noro     1408: \E
                   1409: \BEG
                   1410: @item
                   1411: Let @var{p1}, @var{p2} be points on the elliptic curve represented by
                   1412: @var{ec} over the current base field.
                   1413: ecm_add_ff(@var{p1},@var{p2},@var{ec}), ecm_sub_ff(@var{p1},@var{p2},@var{ec})
1.3       noro     1414: and ecm_chsgn_ff(@var{p1}) returns
1.2       noro     1415: @var{p1+p2}, @var{p1-p2} and @var{-p1} respectively.
                   1416: @item
                   1417: If the current base field is a prime field of odd order, then
1.5     ! noro     1418: @var{ec} represents y^2=x^3+ec[0]x+ec[1].
1.2       noro     1419: If the characteristic of the current base field is 2,
1.5     ! noro     1420: then @var{ec} represents y^2+xy=x^3+ec[0]x^2+ec[1].
1.2       noro     1421: @item
                   1422: The point at infinity is represented by 0.
                   1423: @item
                   1424: If an argument denoting a point is a vector of length 3,
                   1425: then it is the projective coordinate. In such a case
                   1426: the third coordinate must not be 0.
                   1427: @item
                   1428: If the result is a vector of length 3, then the third coordinate
                   1429: is not equal to 0 but not necessarily 1. To get the result by
                   1430: the affine coordinate, the first and the second coordinates should
                   1431: be divided by the third coordinate.
                   1432: @item
                   1433: The check whether the arguments are on the curve is omitted.
                   1434: \E
1.1       noro     1435: @end itemize
                   1436:
                   1437: @example
                   1438: [0] setmod_ff(1125899906842679)$
                   1439: [1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
                   1440: [2] Pt1=newvect(3,[1,-412127497938252,1])$
                   1441: [3] Pt2=newvect(3,[6,-252647084363045,1])$
                   1442: [4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
                   1443: [ 560137044461222 184453736165476 125 ]
                   1444: [5] F=y^2-(x^3+EC[0]*x+EC[1])$
                   1445: [6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
                   1446: 0
                   1447: [7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
                   1448: 0
                   1449: [8] D=ecm_sub_ff(Pt3,Pt2,EC);
                   1450: [ 886545905133065 119584559149586 886545905133065 ]
                   1451: [9] D[0]/D[2]==Pt1[0]/Pt1[2];
                   1452: 1
                   1453: [10] D[1]/D[2]==Pt1[1]/Pt1[2];
                   1454: 1
                   1455: @end example
                   1456:
                   1457: @table @t
1.2       noro     1458: \JP @item $B;2>H(B
                   1459: \EG @item References
1.1       noro     1460: @fref{setmod_ff}
                   1461: @end table
                   1462: