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