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

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