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

1.3     ! noro        1: @comment $OpenXM: OpenXM/src/asir-doc/parts/ff.texi,v 1.2 1999/12/21 02:47:31 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::
                     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})
1.3     ! noro     1203: @itemx ecm_chsgn_ff(@var{p1})
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})
1.3     ! noro     1246: and ecm_chsgn_ff(@var{p1}) returns
1.2       noro     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: