Annotation of OpenXM/src/asir-doc/parts/algnum.texi, Revision 1.2
1.2 ! noro 1: @comment $OpenXM$
! 2: \BJP
1.1 noro 3: @node $BBe?tE*?t$K4X$9$k1i;;(B,,, Top
4: @chapter $BBe?tE*?t$K4X$9$k1i;;(B
1.2 ! noro 5: \E
! 6: \BEG
! 7: @node Algebraic numbers,,, Top
! 8: @chapter Algebraic numbers
! 9: \E
1.1 noro 10:
11: @menu
1.2 ! noro 12: \BJP
1.1 noro 13: * $BBe?tE*?t$NI=8=(B::
14: * $BBe?tE*?t$N1i;;(B::
15: * $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
16: * $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B::
1.2 ! noro 17: \E
! 18: \BEG
! 19: * Representation of algebraic numbers::
! 20: * Operations over algebraic numbers::
! 21: * Operations for uni-variate polynomials over an algebraic number field::
! 22: * Summary of functions for algebraic numbers::
! 23: \E
1.1 noro 24: @end menu
25:
1.2 ! noro 26: \BJP
1.1 noro 27: @node $BBe?tE*?t$NI=8=(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
28: @section $BBe?tE*?t$NI=8=(B
1.2 ! noro 29: \E
! 30: \BEG
! 31: @node Representation of algebraic numbers,,, Algebraic numbers
! 32: @section Representation of algebraic numbers
! 33: \E
1.1 noro 34:
35: @noindent
1.2 ! noro 36: \BJP
1.1 noro 37: @b{Asir} $B$K$*$$$F$O(B, $BBe?tBN$H$$$&BP>]$ODj5A$5$l$J$$(B.
38: $BFHN)$7$?BP>]$H$7$FDj5A$5$l$k$N$O(B, $BBe?tE*?t$G$"$k(B.
39: $BBe?tBN$O(B, $BM-M}?tBN$K(B, $BBe?tE*?t$rM-8B8D(B
40: $B=g<!E:2C$7$?BN$H$7$F2>A[E*$KDj5A$5$l$k(B. $B?7$?$JBe?tE*?t$O(B, $BM-M}?t$*$h$S(B
41: $B$3$l$^$GDj5A$5$l$?Be?tE*?t$NB?9`<0$r78?t$H$9$k(B 1 $BJQ?tB?9`<0(B
42: $B$rDj5AB?9`<0$H$7$FDj5A$5$l$k(B. $B0J2<(B, $B$"$kDj5AB?9`<0$N:,$H$7$F(B
43: $BDj5A$5$l$?Be?tE*?t$r(B, @code{root} $B$H8F$V$3$H$K$9$k(B.
1.2 ! noro 44: \E
! 45: \BEG
! 46: In @b{Asir} algebraic number fields are not defined
! 47: as independent objects.
! 48: Instead, individual algebraic numbers are defined by some
! 49: means. In @b{Asir} an algebraic number field is
! 50: defined virtually as a number field obtained by adjoining a finite number
! 51: of algebraic numbers to the rational number field.
! 52:
! 53: A new algebraic number is introduced in @b{Asir} in such a way where
! 54: it is defined as a root of an uni-variate polynomial
! 55: whose coefficients include already defined algebraic numbers
! 56: as well as rational numbers.
! 57: We shall call such a newly defined algebraic number a @b{root}.
! 58: Also, we call such an uni-variate polynomial the defining polynomial
! 59: of that @b{root}.
! 60: \E
1.1 noro 61:
62: @example
63: [0] A0=newalg(x^2+1);
64: (#0)
65: [1] A1=newalg(x^3+A0*x+A0);
66: (#1)
67: [2] [type(A0),ntype(A0)];
68: [1,2]
69: @end example
70:
71: @noindent
1.2 ! noro 72: \BJP
1.1 noro 73: $B$3$NNc$G$O(B, @code{A0} $B$O(B @code{x^2+1=0} $B$N:,(B, @code{A1} $B$O(B, $B$=$N(B @code{A0}
74: $B$r78?t$K4^$`(B @code{x^3+A0*x+A0=0} $B$N:,$H$7$FDj5A$5$l$F$$$k(B.
1.2 ! noro 75: \E
! 76: \BEG
! 77: In this example, the algebraic number assigned to @code{A0} is defined
! 78: as a @b{root} of a polynomial @code{x^2+1};
! 79: that of @code{A1} is defined as a @b{root} of a polynomial
! 80: @code{x^3+A0*x+A0}, which you see contains the previously defined
! 81: @b{root} (@code{A0}) in its coefficients.
! 82: \E
1.1 noro 83:
84: @noindent
1.2 ! noro 85: \JP @code{newalg()} $B$N0z?t$9$J$o$ADj5AB?9`<0$K$O<!$N$h$&$J@)8B$,$"$k(B.
! 86: \BEG
! 87: The argument to @code{newalg()}, i.e., the defining polynomial,
! 88: must satisfy the following conditions.
! 89: \E
1.1 noro 90:
91: @enumerate
92: @item
1.2 ! noro 93: \JP $BDj5AB?9`<0$O(B 1 $BJQ?tB?9`<0$G$J$1$l$P$J$i$J$$(B.
! 94: \EG A defining polynomial must be an uni-variate polynomial.
1.1 noro 95:
96: @item
1.2 ! noro 97: \BJP
1.1 noro 98: @code{newalg()} $B$N0z?t$G$"$kDj5AB?9`<0$O(B, $BBe?tE*?t$r4^$`<0$N4JC12=$N$?(B
99: $B$a$KMQ$$$i$l$k(B. $B$3$N4JC12=$O(B, $BAH$_9~$_H!?t(B @code{srem()} $B$KAjEv$9$kFb(B
100: $BIt%k!<%A%s$rMQ$$$F9T$o$l$k(B. $B$3$N$?$a(B, $BDj5AB?9`<0$N<g78?t$O(B, $BM-M}?t$K(B
101: $B$J$C$F$$$kI,MW$,$"$k(B.
1.2 ! noro 102: \E
! 103: \BEG
! 104: A defining polynomial is used
! 105: to simplify expressions containing that algebraic number.
! 106: The procedure of such simplification is performed by an internal routine
! 107: similar to the built-in function @code{srem()}, where the defining
! 108: polynomial is used for the second argument, the divisor.
! 109: By this reason, the leading coefficient of the defining polynomial
! 110: must be a rational number (must not be an algebraic number.)
! 111: \E
1.1 noro 112:
113: @item
1.2 ! noro 114: \BJP
1.1 noro 115: $BDj5AB?9`<0$N78?t$O(B $B$9$G$KDj5A$5$l$F$$$k(B @code{root} $B$NM-M}?t78?tB?9`<0(B
116: $B$G$J$1$l$P$J$i$J$$(B.
1.2 ! noro 117: \E
! 118: \BEG
! 119: Every coefficients of a defining polynomial must be
! 120: a `(multi-variate) polynomial' in already defined @b{root}'s.
! 121: Here, `(multi-variate) polynomial' means a mathematical concept,
! 122: not the object type `polynomial' in @b{Asir}.
! 123: \E
1.1 noro 124: @item
1.2 ! noro 125: \BJP
1.1 noro 126: $BDj5AB?9`<0$O(B, $B$=$N78?t$K4^$^$l$kA4$F$N(B @code{root} $B$rM-M}?t$KE:2C$7$?(B
127: $BBN>e$G4{Ls$G$J$1$l$P$J$i$J$$(B.
1.2 ! noro 128: \E
! 129: \BEG
! 130: A defining polynomial must be irreducible over the field that is obtained
! 131: by adjoining all @b{root}'s contained in its coefficients
! 132: to the rational number field.
! 133: \E
1.1 noro 134: @end enumerate
135:
136: @noindent
1.2 ! noro 137: \BJP
1.1 noro 138: @code{newalg()} $B$,9T$&0z?t%A%'%C%/$O(B, 1 $B$*$h$S(B 2 $B$N$_$G$"$k(B.
139: $BFC$K(B, $B0z?t$NDj5AB?9`<0$N4{Ls@-$OA4$/%A%'%C%/$5$l$J$$(B. $B$3$l$O(B
140: $B4{Ls@-$N%A%'%C%/$,B?Bg$J7W;;NL$rI,MW$H$9$k$?$a$G(B, $B$3$NE@$K4X$7$F$O(B,
141: $B%f!<%6$N@UG$$KG$$5$l$F$$$k(B.
1.2 ! noro 142: \E
! 143: \BEG
! 144: Only the first two conditions (1 and 2) are checked
! 145: by function @code{newalg()}.
! 146: Among all, it should be emphasized that no check is done for the
! 147: irreducibility at all.
! 148: The reason is that the irreducibility test requires enormously much
! 149: computation time. You are trusted whether to check it at your own risk.
! 150: \E
1.1 noro 151:
152: @noindent
1.2 ! noro 153: \BJP
1.1 noro 154: $B0lC6(B @code{newalg()} $B$K$h$C$FDj5A$5$l$?Be?tE*?t$O(B, $B?t$H$7$F$N<1JL;R$r;}$A(B,
155: $B$^$?(B, $B?t$NCf$G$OBe?tE*?t$H$7$F$N<1JL;R$r;}$D(B. (@code{type()}, @code{vtype()}
156: $B;2>H(B.) $B$5$i$K(B, $BM-M}?t$H(B, @code{root} $B$NM-M}<0$bF1MM$KBe?tE*?t$H$J$k(B.
1.2 ! noro 157: \E
! 158: \BEG
! 159: Once a @b{root} has been defined by @code{newalg()} function,
! 160: it is given the type identifier for a number, and furthermore,
! 161: the sub-type identifier for an algebraic number.
! 162: (@xref{type}, @ref{ntype}.)
! 163: Also, any rational combination of rational numbers and @b{root}'s
! 164: is an algebraic number.
! 165: \E
1.1 noro 166:
167: @example
168: [87] N=(A0^2+A1)/(A1^2-A0-1);
169: ((#1+#0^2)/(#1^2-#0-1))
170: [88] [type(N),ntype(N)];
171: [1,2]
172: @end example
173:
174: @noindent
1.2 ! noro 175: \BJP
1.1 noro 176: $BNc$+$i$o$+$k$h$&$K(B, @code{root}$B$O(B @code{#@var{n}}
177: $B$HI=<($5$l$k(B. $B$7$+$7(B, $B%f!<%6$O$3$N7A$G$OF~NO$G$-$J$$(B. @code{root} $B$O(B
178: $BJQ?t$K3JG<$7$FMQ$$$k$+(B, $B$"$k$$$O(B @code{alg(@var{n})} $B$K$h$j<h$j=P$9(B.
179: $B$^$?(B, $B8zN($OMn$A$k$,(B, $BA4$/F1$80z?t(B ($BJQ?t$O0[$J$C$F$$$F$b$h$$(B) $B$K$h$j(B
180: @code{newalg()} $B$r8F$Y$P(B, $B?7$7$$Be?tE*?t$ODj5A$5$l$:$K4{$KDj5A$5$l$?(B
181: $B$b$N$,F@$i$l$k(B.
1.2 ! noro 182: \E
! 183: \BEG
! 184: As you see it in the example, a @b{root} is displayed as
! 185: @code{#@var{n}}. But, you cannot input that @b{root} in
! 186: its immediate output form.
! 187: You have to refer to a @b{root} by a program variable assigned
! 188: to the @b{root}, or to get it by @code{alg(@var{n})} function, or by
! 189: several other indirect means.
! 190: A strange use of @code{newalg()}, with a same argument polynomial
! 191: (except for the name of its main variable), will yield the old
! 192: @b{root} instead of a new @b{root} though it is apparently inefficient.
! 193: \E
1.1 noro 194:
195: @example
196: [90] alg(0);
197: (#0)
198: [91] newalg(t^2+1);
199: (#0)
200: @end example
201:
202: @noindent
1.2 ! noro 203: \JP @code{root} $B$NDj5AB?9`<0$O(B, @code{defpoly()} $B$K$h$j<h$j=P$;$k(B.
! 204: \BEG
! 205: The defining polynomial of a @b{root} can be obtained by
! 206: @code{defpoly()} function.
! 207: \E
1.1 noro 208:
209: @example
210: [96] defpoly(A0);
211: t#0^2+1
212: [97] defpoly(A1);
213: t#1^3+t#0*t#1+t#0
214: @end example
215:
216: @noindent
1.2 ! noro 217: \BJP
1.1 noro 218: $B$3$3$G8=$l$?(B, @code{t#0}, @code{t#1} $B$O$=$l$>$l(B @code{#0}, @code{#1} $B$K(B
219: $BBP1~$9$kITDj85$G$"$k(B. $B$3$l$i$b%f!<%6$,F~NO$9$k$3$H$O$G$-$J$$(B.
220: @code{var()} $B$G<h$j=P$9$+(B, $B$"$k$$$O(B @code{algv(@var{n})} $B$K$h$j<h$j=P$9(B.
1.2 ! noro 221: \E
! 222: \BEG
! 223: Here, you see a strange expression, @code{t#0} and @code{t#1}.
! 224: They are a specially indeterminates generated and maintained
! 225: by @b{Asir} internally. Indeterminate @code{t#0} corresponds to
! 226: @b{root} @code{#0}, and @code{t#0} to @code{#1}. These indeterminates
! 227: also cannot be input directly by a user in their immediate forms.
! 228: You can get them by several ways: by @code{var()} function,
! 229: or @code{algv(@var{n})} function.
! 230: \E
1.1 noro 231:
232: @example
233: [98] var(@@);
234: t#1
235: [99] algv(0);
236: t#0
237: [100]
238: @end example
239:
1.2 ! noro 240: \BJP
1.1 noro 241: @node $BBe?tE*?t$N1i;;(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
242: @section $BBe?tE*?t$N1i;;(B
1.2 ! noro 243: \E
! 244: \BEG
! 245: @node Operations over algebraic numbers,,, Algebraic numbers
! 246: @section Operations over algebraic numbers
! 247: \E
1.1 noro 248:
249: @noindent
1.2 ! noro 250: \BJP
1.1 noro 251: $BA0@a$G(B, $BBe?tE*?t$NI=8=(B, $BDj5A$K$D$$$F=R$Y$?(B. $B$3$3$G$O(B, $BBe?tE*?t$rMQ$$$?(B
252: $B1i;;$K$D$$$F=R$Y$k(B. $BBe?tE*?t$K4X$7$F$O(B, $BAH$_9~$_H!?t$H$7$FDs6!$5$l$F$$$k(B
253: $B5!G=$O$4$/>/?t$G(B, $BBgItJ,$O%f!<%6Dj5AH!?t$K$h$j<B8=$5$l$F$$$k(B. $B%U%!%$%k(B
254: $B$O(B, @samp{sp} $B$G(B, @samp{gr} $B$HF1MM(B @b{Asir} $B$NI8=`%i%$%V%i%j%G%#%l%/%H%j(B
255: $B$K$*$+$l$F$$$k(B.
1.2 ! noro 256: \E
! 257: \BEG
! 258: In the previous section, we explained about the
! 259: representation of algebraic numbers and their defining method.
! 260: Here, we describe operations on algebraic numbers.
! 261: Only a few functions are built-in, and almost all functions are provided
! 262: as user defined functions. The file containing their definitions is
! 263: @samp{sp}, and it is placed under the same directory
! 264: as @samp{gr} is placed, i.e., the standard library directory of @b{Asir}.
! 265: \E
1.1 noro 266:
267: @example
268: [0] load("gr")$
269: [1] load("sp")$
270: @end example
271:
272: @noindent
1.2 ! noro 273: \JP $B$"$k$$$O(B, $B>o$KMQ$$$k$J$i$P(B, @samp{$HOME/.asirrc} $B$K=q$$$F$*$/$N$b$h$$(B.
! 274: \BEG
! 275: Or if you always need them, it is more convenient to include the
! 276: @code{load} commands in @samp{$HOME/.asirrc}.
! 277: \E
1.1 noro 278:
279: @noindent
1.2 ! noro 280: \BJP
1.1 noro 281: @code{root} $B$O(B $B$=$NB>$N?t$HF1MM(B, $B;MB'1i;;$,2DG=$H$J$k(B. $B$7$+$7(B, $BDj5AB?(B
282: $B9`<0$K$h$k4JC12=$O<+F0E*$K$O9T$o$l$J$$$N$G(B, $B%f!<%6$NH=CG$GE,599T$o(B
283: $B$J$1$l$P$J$i$J$$(B. $BFC$K(B, $BJ,Jl$,(B 0 $B$K$J$k>l9g$KCWL?E*$J%(%i!<$H$J$k$?$a(B,
284: $B<B:]$KJ,Jl$r;}$DBe?tE*?t$r@8@.$9$k>l9g$K$O:Y?4$NCm0U$,I,MW$H$J$k(B.
1.2 ! noro 285: \E
! 286: \BEG
! 287: Like the other numbers, algebraic numbers can get arithmetic operations
! 288: applied. Simplification, however, by defining polynomials are
! 289: not automatically performed. It is left to users to simplify their
! 290: expressions. A fatal error shall result if the denominator expression
! 291: will be simplified to 0. Therefore, be careful enough when you
! 292: will create and deal with algebraic numbers which may denominators
! 293: in their expressions.
! 294: \E
! 295:
! 296: \JP $BBe?tE*?t$N(B, $BDj5AB?9`<0$K$h$k4JC12=$O(B, @code{simpalg()} $B$G9T$&(B.
! 297: \BEG
! 298: Use @code{simpalg()} function for simplification of algebraic numbers
! 299: by defining polynomials.
! 300: \E
1.1 noro 301:
302: @example
303: [49] T=A0^2+1;
304: (#0^2+1)
305: [50] simpalg(T);
306: 0
307: @end example
308:
309: @noindent
1.2 ! noro 310: \JP @code{simpalg()} $B$OM-M}<0$N7A$r$7$?Be?tE*?t$r(B, $BB?9`<0$N7A$K4JC12=$9$k(B.
! 311: \BEG
! 312: Function @code{simpalg()} simplifies algebraic numbers which have
! 313: the same structures as rational expressions in their appearances.
! 314: \E
1.1 noro 315:
316: @example
317: [39] A0=newalg(x^2+1);
318: (#0)
319: [40] T=(A0^2+A0+1)/(A0+3);
320: ((#0^2+#0+1)/(#0+3))
321: [41] simpalg(T);
322: (3/10*#0+1/10)
323: [42] T=1/(A0^2+1);
324: ((1)/(#0^2+1))
325: [43] simpalg(T);
326: div : division by 0
327: stopped in invalgp at line 258 in file "/usr/local/lib/asir/sp"
328: 258 return 1/A;
329: (debug)
330: @end example
331:
332: @noindent
1.2 ! noro 333: \BJP
1.1 noro 334: $B$3$NNc$G$O(B, $BJ,Jl$,(B 0 $B$NBe?tE*?t$r4JC12=$7$h$&$H$7$F(B 0 $B$K$h$k=|;;$,@8$8(B
335: $B$?$?$a(B, $B%f!<%6Dj5AH!?t$G$"$k(B @code{simpalg()} $B$NCf$G%G%P%C%,$,8F$P$l$?(B
336: $B$3$H$r<($9(B. @code{simpalg()} $B$O(B, $BBe?tE*?t$r78?t$H$9$kB?9`<0$N(B
337: $B3F78?t$r4JC12=$G$-$k(B.
1.2 ! noro 338: \E
! 339: \BEG
! 340: This example shows an error caused by zero division in the course of
! 341: program execution of @code{simpalg()}, which attempted to simplify
! 342: an algebraic number expression of which the denominator is 0.
! 343:
! 344: Function @code{simpalg()} also can take a polynomial as its argument
! 345: and simplifies algebraic numbers in its coefficients.
! 346: \E
1.1 noro 347:
348: @example
349: [43] simpalg(1/A0*x+1/(A0+1));
350: (-#0)*x+(-1/2*#0+1/2)
351: @end example
352:
353: @noindent
1.2 ! noro 354: \BJP
1.1 noro 355: $BBe?tE*?t$r78?t$H$9$kB?9`<0$N4pK\1i;;$O(B, $BE,59(B @code{simpalg()} $B$r8F$V$3$H$r(B
356: $B=|$1$PDL>o$N>l9g$HF1MM$G$"$k$,(B, $B0x?tJ,2r$J$I$GIQHK$KMQ$$$i$l$k%N%k%`$N(B
357: $B7W;;$J$I$K$*$$$F$O(B, @code{root} $B$rITDj85$KCV$-49$($kI,MW$,=P$F$/$k(B.
358: $B$3$N>l9g(B, @code{algptorat()} $B$rMQ$$$k(B.
1.2 ! noro 359: \E
! 360: \BEG
! 361: Thus, you can operate in polynomials which contain algebraic numbers
! 362: as you do usually in ordinary polynomials,
! 363: except for proper simplification by @code{simpalg()}.
! 364: You may sometimes feel needs to convert @b{root}'s into indeterminates,
! 365: especially when you are working for norm computation in algorithms for
! 366: algebraic factorization.
! 367: Function @code{algptorat()} is used for such cases.
! 368: \E
1.1 noro 369:
370: @example
371: [83] A0=newalg(x^2+1);
372: (#0)
373: [84] A1=newalg(x^3+A0*x+A0);
374: (#1)
375: [85] T=(2*A0+A1*A0+A1^2)*x+(1+A1)/(2+A0);
376: (#1^2+#0*#1+2*#0)*x+((#1+1)/(#0+2))
377: [86] S=algptorat(T);
378: (((t#0+2)*t#1^2+(t#0^2+2*t#0)*t#1+2*t#0^2+4*t#0)*x+t#1+1)/(t#0+2)
379: [87] algptorat(coef(T,1));
380: t#1^2+t#0*t#1+2*t#0
381: @end example
382:
383: @noindent
1.2 ! noro 384: \BJP
1.1 noro 385: $B$3$N$h$&$K(B, @code{algptorat()} $B$O(B, $BB?9`<0(B, $B?t$K4^$^$l$k(B @code{root}
386: $B$r(B, $BBP1~$9$kITDj85(B, $B$9$J$o$A(B @code{#@var{n}} $B$KBP$9$k(B @code{t#@var{n}}
387: $B$KCV$-49$($k(B. $B4{$K=R$Y$?$h$&$K(B, $B$3$NITDj85$O%f!<%6$,F~NO$9$k$3$H$O$G$-$J$$(B.
388: $B$3$l$O(B, $B%f!<%6$NF~NO$7$?ITDj85$H(B, @code{root} $B$KBP1~$9$kITDj85$,0lCW(B
389: $B$7$J$$$h$&$K$9$k$?$a$G$"$k(B.
1.2 ! noro 390: \E
! 391: \BEG
! 392: As you see by the example,
! 393: function @code{algptorat()} converts @b{root}'s, @code{#@var{n}},
! 394: in polynomials and numbers into its associated indeterminates,
! 395: @code{t#@var{n}}. As was already mentioned those indeterminates cannot
! 396: be directly input in their immediate form.
! 397: The restriction is adopted to avoid the confusion that might happen
! 398: if the user could input such internally generatable indeterminates.
! 399: \E
1.1 noro 400:
401: @noindent
1.2 ! noro 402: \BJP
1.1 noro 403: $B5U$K(B, @code{root} $B$KBP1~$9$kITDj85$r(B, $BBP1~$9$k(B @code{root} $B$KCV$-49$($k(B
404: $B$?$a$K$O(B @code{rattoalgp()} $B$rMQ$$$k(B.
1.2 ! noro 405: \E
! 406: \BEG
! 407: The associated indeterminate to a @b{root} is reversely converted
! 408: into the @b{root} by @code{rattoalgp()} function.
! 409: \E
1.1 noro 410:
411: @example
412: [88] rattoalgp(S,[alg(0)]);
413: (((#0+2)/(#0+2))*t#1^2+((#0^2+2*#0)/(#0+2))*t#1+((2*#0^2+4*#0)/(#0+2)))*x
414: +((1)/(#0+2))*t#1+((1)/(#0+2))
415: [89] rattoalgp(S,[alg(0),alg(1)]);
416: (((#0^3+6*#0^2+12*#0+8)*#1^2+(#0^4+6*#0^3+12*#0^2+8*#0)*#1+2*#0^4+12*#0^3
417: +24*#0^2+16*#0)/(#0^3+6*#0^2+12*#0+8))*x+(((#0+2)*#1+#0+2)/(#0^2+4*#0+4))
418: [90] rattoalgp(S,[alg(1),alg(0)]);
419: (((#0+2)*#1^2+(#0^2+2*#0)*#1+2*#0^2+4*#0)/(#0+2))*x+((#1+1)/(#0+2))
420: [91] simpalg(@@89);
421: (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
422: [92] simpalg(@@90);
423: (#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
424: @end example
425:
426: @noindent
1.2 ! noro 427: \BJP
1.1 noro 428: @code{rattoalgp()} $B$O(B, $BCV49$NBP>]$H$J$k(B @code{root} $B$N%j%9%H$rBh(B 2 $B0z?t(B
429: $B$K$H$j(B, $B:8$+$i=g$K(B, $BBP1~$9$kITDj85$rCV$-49$($F9T$/(B. $B$3$NNc$O(B,
430: $BCV49$9$k=g=x$r49$($k$H4JC12=$r9T$o$J$$$3$H$K$h$j7k2L$,0l8+0[$J$k$,(B,
431: $B4JC12=$K$h$j<B$O0lCW$9$k$3$H$r<($7$F$$$k(B. @code{algptorat()},
432: @code{rattoalgp()} $B$O(B, $B%f!<%6$,FH<+$N4JC12=$r9T$$$?$$>l9g$J$I$K$b(B
433: $BMQ$$$k$3$H$,$G$-$k(B.
1.2 ! noro 434: \E
! 435: \BEG
! 436: Function @code{rattoalgp()} takes as the second argument
! 437: a list consisting of @b{root}'s that you want to convert,
! 438: and converts them successively from the left.
! 439: This example shows that apparent difference of the results due to
! 440: the order of such conversion will vanish by simplification yielding
! 441: the same result.
! 442: Functions @code{algptorat()} and @code{rattoalgp()} can be conveniently
! 443: used for your own simplification.
! 444: \E
1.1 noro 445:
1.2 ! noro 446: \BJP
1.1 noro 447: @node $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
448: @section $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
1.2 ! noro 449: \E
! 450: \BEG
! 451: @node Operations for uni-variate polynomials over an algebraic number field,,, Algebraic numbers
! 452: @section Operations for uni-variate polynomials over an algebraic number field
! 453: \E
1.1 noro 454:
455: @noindent
1.2 ! noro 456: \BJP
1.1 noro 457: @samp{sp} $B$G$O(B, 1 $BJQ?tB?9`<0$K8B$j(B, GCD, $B0x?tJ,2r$*$h$S$=$l$i$N1~MQ$H$7$F(B
458: $B:G>.J,2rBN$r5a$a$kH!?t$rDs6!$7$F$$$k(B.
1.2 ! noro 459: \E
! 460: \BEG
! 461: In the file @samp{sp} are provided functions for uni-variate polynomial
! 462: factorization and uni-variate polynomial GCD computation
! 463: over algebraic numbers,
! 464: and furthermore, as an application of them,
! 465: functions to compute splitting fields of univariate polynomials.
! 466: \E
1.1 noro 467:
468: @menu
469: * GCD::
1.2 ! noro 470: \BJP
1.1 noro 471: * $BL5J?J}J,2r(B $B0x?tJ,2r(B::
472: * $B:G>.J,2rBN(B::
1.2 ! noro 473: \E
! 474: \BEG
! 475: * Square-free factorization and Factorization::
! 476: * Splitting fields::
! 477: \E
1.1 noro 478: @end menu
479:
1.2 ! noro 480: \JP @node GCD,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
! 481: \EG @node GCD,,, Operations for uni-variate polynomials over an algebraic number field
1.1 noro 482: @subsection GCD
483:
484: @noindent
1.2 ! noro 485: \BJP
! 486: $BBe?tBN>e$G$N(B GCD $B$O(B @code{cr_gcda()} $B$K$h$j7W;;$5$l$k(B.
1.1 noro 487: $B$3$NH!?t$O%b%8%e%i1i;;$*$h$SCf9q>jM>DjM}$K$h$jBe?tBN>e$N(B GCD $B$r(B
488: $B7W;;$9$k$b$N$G(B, $BC`<!3HBg$KBP$7$F$bM-8z$G$"$k(B.
1.2 ! noro 489: \E
! 490: \BEG
! 491: Greatest common divisors (GCD) over algebraic number fields are computed
! 492: by @code{cr_gcda()} function. This function computes GCD by using modular
! 493: computation and Chinese remainder theorem and it works for the case
! 494: where the ground field is a multiple extension.
! 495: \E
1.1 noro 496:
497: @example
498: [63] A=newalg(t^9-15*t^6-87*t^3-125);
499: (#0)
500: [64] B=newalg(75*s^2+(10*A^7-175*A^4-470*A)*s+3*A^8-45*A^5-261*A^2);
501: (#1)
502: [65] P1=75*x^2+(150*B+10*A^7-175*A^4-395*A)*x+(75*B^2+(10*A^7-175*A^4-395*A)*B
503: +13*A^8-220*A^5-581*A^2)$
504: [66] P2=x^2+A*x+A^2$
1.2 ! noro 505: [67] cr_gcda(P1,P2,[B,A]);
1.1 noro 506: 27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)
507: @end example
508:
1.2 ! noro 509: \BJP
1.1 noro 510: @node $BL5J?J}J,2r(B $B0x?tJ,2r(B,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
511: @subsection $BL5J?J}J,2r(B, $B0x?tJ,2r(B
1.2 ! noro 512: \E
! 513: \BEG
! 514: @node Square-free factorization and Factorization,,, Operations for uni-variate polynomials over an algebraic number field
! 515: @subsection Square-free factorization and Factorization
! 516: \E
1.1 noro 517:
518: @noindent
1.2 ! noro 519: \BJP
1.1 noro 520: $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
521: $B%"%k%4%j%:%`$r:NMQ$7$F$$$k(B. $BH!?t$O(B @code{asq()} $B$G$"$k(B.
1.2 ! noro 522: \E
! 523: \BEG
! 524: For square-free factorization (of uni-variate polynomials over algebraic
! 525: number fields), we employ the most fundamental algorithm which begins
! 526: first to compute GCD of a polynomial and its derivative.
! 527: The function to do this factorization is @code{asq()}.
! 528: \E
1.1 noro 529:
530: @example
531: [116] A=newalg(x^2+x+1);
532: (#4)
533: [117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
534: x^11+(#4+1)*x^10+(-4*#4-8)*x^9+(-10*#4-4)*x^8+(16*#4+20)*x^7+(24*#4-6)*x^6
535: +(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3+(#4-23)*x^2+(-21*#4-7)*x
536: +(3*#4+8)
537: [118] asq(T);
538: [[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]
539: @end example
540:
541: @noindent
1.2 ! noro 542: \BJP
1.1 noro 543: $B7k2L$ODL>o$HF1MM$K(B, [@b{$B0x;R(B}, @b{$B=EJ#EY(B}] $B$N%j%9%H$H$J$k$,(B, $BA4$F$N0x;R(B
544: $B$N@Q$O(B, $B$b$H$NB?9`<0$HDj?tG\$N:9$O$"$jF@$k(B. $B$3$l$O(B, $B0x;R$r@0?t78?t$K$7(B
545: $B$F8+$d$9$/$9$k$?$a$G(B, $B0x?tJ,2r$G$bF1MM$G$"$k(B.
1.2 ! noro 546: \E
! 547: \BEG
! 548: Like factorization over the rational number field,
! 549: the result is presented,
! 550: commonly to both square-free factorization and factorization,
! 551: as a list whose elements are pairs (list of two elements) in the form
! 552: [@b{factor}, @b{multiplicity}]
! 553: without the constant multiple part.
! 554:
! 555: Here, it should be noticed that the products of all factors of the
! 556: result may DIFFER from the input polynomial by a constant.
! 557: The reason is that the factors are normalized so that they have
! 558: integral leading coefficients for the sake of readability.
! 559:
! 560: This incongruity may happen to square-free factorization and
! 561: factorization commonly.
! 562: \E
1.1 noro 563:
564: @noindent
1.2 ! noro 565: \BJP
1.1 noro 566: $BBe?tBN>e$G$N0x?tJ,2r$O(B, Trager $B$K$h$k%N%k%`K!$r2~NI$7$?$b$N$G(B, $BFC$K(B
567: $B$"$kB?9`<0$KBP$7(B, $B$=$N:,$rE:2C$7$?BN>e$G$=$NB?9`<0<+?H$r0x?tJ,2r$9$k(B
568: $B>l9g$KFC$KM-8z$G$"$k(B.
1.2 ! noro 569: \E
! 570: \BEG
! 571: The algorithm employed for factorization over algebraic number fields
! 572: is an improvement of the norm method by Trager.
! 573: It is especially very effective to factorize a polynomial over a field
! 574: obtained by adjoining some of its @b{root}'s to the base field.
! 575: \E
1.1 noro 576:
577: @example
578: [119] af(T,[A]);
579: [[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]
580: @end example
581:
582: @noindent
1.2 ! noro 583: \BJP
1.1 noro 584: $B0z?t$O(B 2 $B$D$G(B, $BBh(B 2 $B0z?t$O(B, @code{root} $B$N%j%9%H$G$"$k(B. $B0x?tJ,2r$O(B
585: $BM-M}?tBN$K(B, $B$=$l$i$N(B @code{root} $B$rE:2C$7$?BN>e$G9T$o$l$k(B.
586: @code{root} $B$N=g=x$K$O@)8B$,$"$k(B. $B$9$J$o$A(B, $B8e$GDj5A$5$l$?$b$N$[$I(B
587: $BA0$NJ}$K$3$J$1$l$P(B
588: $B$J$i$J$$(B. $BJB$Y49$($O(B, $B<+F0E*$K$O9T$o$l$J$$(B. $B%f!<%6$N@UG$$H$J$k(B.
1.2 ! noro 589: \E
! 590: \BEG
! 591: The function takes two arguments: The second argument is a list of
! 592: @b{root}'s. Factorization is performed over a field obtained by
! 593: adjoining the @b{root}'s to the rational number field.
! 594: It is important to keep in mind that the ordering of the @b{root}'s
! 595: must obey a restriction: Last defined should come first.
! 596: The automatic re-ordering is not done.
! 597: It should be done by yourself.
! 598: \E
1.1 noro 599:
600: @noindent
1.2 ! noro 601: \BJP
1.1 noro 602: $B%N%k%`$rMQ$$$?0x?tJ,2r$K$*$$$F$O(B, $B%N%k%`$N7W;;$H@0?t78?t(B 1 $BJQ?tB?9`<0$N(B
603: $B0x?tJ,2r$N8zN($,(B, $BA4BN$N8zN($r:81&$9$k(B. $B$3$N$&$A(B, $BFC$K9b<!$NB?9`<0(B
604: $B$N>l9g$K8e<T$K$*$$$FAH9g$;GzH/$K$h$j7W;;ITG=$K$J$k>l9g$,$7$P$7$P@8$:$k(B.
1.2 ! noro 605: \E
! 606: \BEG
! 607: The efficiency of factorization via norm depends on the efficiency
! 608: of the norm computation and univariate factorization over the rationals.
! 609: Especially the latter often causes combinatorial explosion and the
! 610: computation will stick in such a case.
! 611: \E
1.1 noro 612:
613: @example
614: [120] B=newalg(x^2-2*A-3);
615: (#5)
616: [121] af(T,[B,A]);
617: [[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]
618: @end example
619:
1.2 ! noro 620: \BJP
1.1 noro 621: @node $B:G>.J,2rBN(B,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
622: @subsection $B:G>.J,2rBN(B
1.2 ! noro 623: \E
! 624: \BEG
! 625: @node Splitting fields,,, Operations for uni-variate polynomials over an algebraic number field
! 626: @subsection Splitting fields
! 627: \E
1.1 noro 628:
629: @noindent
1.2 ! noro 630: \BJP
1.1 noro 631: $B$d$dFC<l$J1i;;$G$O$"$k$,(B, $BA0@a$N0x?tJ,2r$rH?I|E,MQ$9$k$3$H$K$h$j(B,
632: $BB?9`<0$N:G>.J,2rBN$r5a$a$k$3$H$,$G$-$k(B. $BH!?t$O(B @code{sp()} $B$G$"$k(B.
1.2 ! noro 633: \E
! 634: \BEG
! 635: This operation may be somewhat unusual and for specific interest.
! 636: (Galois Group for example.) Procedurally, however, it is easy to
! 637: obtain the splitting field of a polynomial by repeated application
! 638: of algebraic factorization described in the previous section.
! 639: The function is @code{sp()}.
! 640: \E
1.1 noro 641:
642: @example
643: [103] sp(x^5-2);
644: [[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),2*x
645: +(-#0^3*#1^3),x+(-#0)],[[(#1),t#1^4+t#0*t#1^3+t#0^2*t#1^2+t#0^3*t#1+t#0^4],
646: [(#0),t#0^5-2]]]
647: @end example
648:
649: @noindent
1.2 ! noro 650: \BJP
1.1 noro 651: @code{sp()} $B$O(B 1 $B0z?t$G(B, $B7k2L$O(B @code{[1 $B<!0x;R$N%j%9%H(B, [[root,
652: algptorat($BDj5AB?9`<0(B)] $B$N%j%9%H(B]} $B$J$k%j%9%H$G$"$k(B.
653: $BBh(B 2 $BMWAG$N(B @code{[root,algptorat($BDj5AB?9`<0(B)]} $B$N%j%9%H$O(B,
654: $B1&$+$i=g$K(B, $B:G>.J,2rBN$,F@$i$l$k$^$GE:2C$7$F$$$C$?(B @code{root} $B$r<($9(B.
655: $B$=$NDj5AB?9`<0$O(B, $B$=$ND>A0$^$G$N(B @code{root} $B$rE:2C$7$?BN>e$G4{Ls$G$"$k$3$H(B
656: $B$,J]>Z$5$l$F$$$k(B.
1.2 ! noro 657: \E
! 658: \BEG
! 659: Function @code{sp()} takes only one argument.
! 660: The result is a list of two element: The first element is
! 661: a list of linear factors, and the second one is a list whose elements
! 662: are pairs (list of two elements) in the form
! 663: @code{[@b{root}, algptorat(@b{defining polynomial})]}.
! 664: The second element, a list of pairs of form
! 665: @code{[@b{root},algptorat(@b{defining polynomial})]},
! 666: corresponds to the @b{root}'s which are adjoined to eventually obtain
! 667: the splitting field. They are listed in the reverse order of adjoining.
! 668: Each of the defining polynomials in the list is, of course,
! 669: guaranteed to be irreducible over the field obtained by adjoining all
! 670: @b{root}'s defined before it.
! 671: \E
1.1 noro 672:
673: @noindent
1.2 ! noro 674: \BJP
1.1 noro 675: $B7k2L$NBh(B 1 $BMWAG$G$"$k(B 1 $B<!0x;R$N%j%9%H$O(B, $BBh(B 2 $BMWAG$N(B @code{root} $B$rA4$F(B
676: $BE:2C$7$?BN>e$G$N(B, @code{sp()} $B$N0z?t$NB?9`<0$NA4$F$N0x;R$rI=$9(B. $B$=$NBN$O(B
677: $B:G>.J,2rBN$H$J$C$F$$$k$N$G(B, $B0x;R$OA4$F(B 1 $B<!$H$J$k$o$1$G$"$k(B. @code{af()}
678: $B$HF1MM(B, $BA4$F$N0x;R$N@Q$O(B, $B$b$H$NB?9`<0$HDj?tG\$N:9$O$"$jF@$k(B.
1.2 ! noro 679: \E
! 680: \BEG
! 681: The first element of the result, a list of linear factors, contains
! 682: all irreducible factors of the input polynomial over the field
! 683: obtained by adjoining all @b{root}'s in the second element of the result.
! 684: Because such field is the splitting field of the input polynomial,
! 685: factors in the result are all linear as the consequence.
! 686:
! 687: Similarly to function @code{af()}, the product of all resulting factors
! 688: may yield a polynomial which differs by a constant.
! 689: \E
1.1 noro 690:
1.2 ! noro 691: \BJP
1.1 noro 692: @node $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
693: @section $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
1.2 ! noro 694: \E
! 695: \BEG
! 696: @node Summary of functions for algebraic numbers,,, Algebraic numbers
! 697: @section Summary of functions for algebraic numbers
! 698: \E
1.1 noro 699: @menu
700: * newalg::
701: * defpoly::
702: * alg::
703: * algv::
704: * simpalg::
705: * algptorat::
706: * rattoalgp::
1.2 ! noro 707: * cr_gcda::
1.1 noro 708: * sp_norm::
709: * asq af::
710: * sp::
711: @end menu
712:
1.2 ! noro 713: \JP @node newalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 714: \EG @node newalg,,, Summary of functions for algebraic numbers
1.1 noro 715: @subsection @code{newalg}
716: @findex newalg
717:
718: @table @t
719: @item newalg(@var{defpoly})
1.2 ! noro 720: \JP :: @code{root} $B$r@8@.$9$k(B.
! 721: \EG :: Creates a new @b{root}.
1.1 noro 722: @end table
723:
724: @table @var
725: @item return
1.2 ! noro 726: \JP $BBe?tE*?t(B (@code{root})
! 727: \EG algebraic number (@b{root})
1.1 noro 728: @item defpoly
1.2 ! noro 729: \JP $BB?9`<0(B
! 730: \EG polynomial
1.1 noro 731: @end table
732:
733: @itemize @bullet
734: @item
1.2 ! noro 735: \JP @var{defpoly} $B$rDj5AB?9`<0$H$9$kBe?tE*?t(B (@code{root}) $B$r@8@.$9$k(B.
! 736: \BEG
! 737: Creates a new @b{root} (algebraic number) with its defining
! 738: polynomial @var{defpoly}.
! 739: \E
! 740: @item
! 741: \JP @var{defpoly} $B$KBP$9$k@)8B$K4X$7$F$O(B, @xref{$BBe?tE*?t$NI=8=(B}.
! 742: \BEG
! 743: For constraints on @var{defpoly},
! 744: @xref{Representation of algebraic numbers}.
! 745: \E
1.1 noro 746: @end itemize
747:
748: @example
749: [0] A0=newalg(x^2-2);
750: (#0)
751: @end example
752:
753: @table @t
1.2 ! noro 754: \JP @item $B;2>H(B
! 755: \EG @item Reference
1.1 noro 756: @fref{defpoly}
757: @end table
758:
1.2 ! noro 759: \JP @node defpoly,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 760: \EG @node defpoly,,, Summary of functions for algebraic numbers
1.1 noro 761: @subsection @code{defpoly}
762: @findex defpoly
763:
764: @table @t
765: @item defpoly(@var{alg})
1.2 ! noro 766: \JP :: @code{root} $B$NDj5AB?9`<0$rJV$9(B.
! 767: \EG :: Returns the defining polynomial of @b{root} @var{alg}.
1.1 noro 768: @end table
769:
770: @table @var
771: @item return
1.2 ! noro 772: \JP $BB?9`<0(B
! 773: \EG polynomial
1.1 noro 774: @item alg
1.2 ! noro 775: \JP $BBe?tE*?t(B (@code{root})
! 776: \EG algebraic number (@code{root})
1.1 noro 777: @end table
778:
779: @itemize @bullet
780: @item
1.2 ! noro 781: \JP @code{root} @var{alg} $B$NDj5AB?9`<0$rJV$9(B.
! 782: \EG Returns the defining polynomial of @b{root} @var{alg}.
1.1 noro 783: @item
1.2 ! noro 784: \BJP
1.1 noro 785: @code{root} $B$r(B @code{#@var{n}} $B$H$9$l$P(B, $BDj5AB?9`<0$N<gJQ?t$O(B
786: @code{t#@var{n}} $B$H$J$k(B.
1.2 ! noro 787: \E
! 788: \BEG
! 789: If the argument @var{alg}, a @b{root}, is @code{#@var{n}},
! 790: then the main variable of its defining polynomial is
! 791: @code{t#@var{n}}.
! 792: \E
1.1 noro 793: @end itemize
794:
795: @example
796: [1] defpoly(A0);
797: t#0^2-2
798: @end example
799:
800: @table @t
1.2 ! noro 801: \JP @item $B;2>H(B
! 802: \EG @item Reference
1.1 noro 803: @fref{newalg}, @fref{alg}, @fref{algv}
804: @end table
805:
1.2 ! noro 806: \JP @node alg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 807: \EG @node alg,,, Summary of functions for algebraic numbers
1.1 noro 808: @subsection @code{alg}
809: @findex alg
810:
811: @table @t
812: @item alg(@var{i})
1.2 ! noro 813: \JP :: $B%$%s%G%C%/%9$KBP1~$9$k(B @code{root} $B$rJV$9(B.
! 814: \EG :: Returns a @b{root} which correspond to the index @var{i}.
1.1 noro 815: @end table
816:
817: @table @var
818: @item return
1.2 ! noro 819: \JP $BBe?tE*?t(B (@code{root})
! 820: \EG algebraic number (@code{root})
1.1 noro 821: @item i
1.2 ! noro 822: \JP $B@0?t(B
! 823: \EG integer
1.1 noro 824: @end table
825:
826: @itemize @bullet
827: @item
1.2 ! noro 828: \JP @code{root} @code{#@var{i}} $B$rJV$9(B.
! 829: \EG Returns @code{#@var{i}}, a @b{root}.
1.1 noro 830: @item
1.2 ! noro 831: \BJP
1.1 noro 832: @code{#@var{i}} $B$O%f!<%6$,D>@\F~NO$G$-$J$$$?$a(B, @code{alg(@var{i})} $B$H(B
833: $B$$$&7A$GF~NO$9$k(B.
1.2 ! noro 834: \E
! 835: \BEG
! 836: Because @code{#@var{i}} cannot be input directly,
! 837: this function provides an alternative way: input @code{alg(@var{i})}.
! 838: \E
1.1 noro 839: @end itemize
840:
841: @example
842: [2] x+#0;
843: syntax error
844: 0
845: [3] alg(0);
846: (#0)
847: @end example
848:
849: @table @t
1.2 ! noro 850: \JP @item $B;2>H(B
! 851: \EG @item Reference
1.1 noro 852: @fref{newalg}, @fref{algv}
853: @end table
854:
1.2 ! noro 855: \JP @node algv,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 856: \EG @node algv,,, Summary of functions for algebraic numbers
1.1 noro 857: @subsection @code{algv}
858: @findex algv
859:
860: @table @t
861: @item algv(@var{i})
1.2 ! noro 862: \JP :: @code{alg(@var{i})} $B$KBP1~$9$kITDj85$rJV$9(B.
! 863: \EG :: Returns the associated indeterminate with @code{alg(@var{i})}.
1.1 noro 864: @end table
865:
866: @table @var
867: @item return
1.2 ! noro 868: \JP $BB?9`<0(B
! 869: \EG polynomial
1.1 noro 870: @item i
1.2 ! noro 871: \JP $B@0?t(B
! 872: \EG integer
1.1 noro 873: @end table
874:
875: @itemize @bullet
876: @item
1.2 ! noro 877: \JP $BB?9`<0(B @code{t#@var{i}} $B$rJV$9(B.
! 878: \EG Returns an indeterminate @code{t#@var{i}}
1.1 noro 879: @item
1.2 ! noro 880: \BJP
1.1 noro 881: @code{t#@var{i}} $B$O%f!<%6$,D>@\F~NO$G$-$J$$$?$a(B, @code{algv(@var{i})} $B$H(B
882: $B$$$&7A$GF~NO$9$k(B.
1.2 ! noro 883: \E
! 884: \BEG
! 885: Since indeterminate @code{t#@var{i}} cannot be input directly,
! 886: it is input by @code{algv(@var{i})}.
! 887: \E
1.1 noro 888: @end itemize
889:
890: @example
891: [4] var(defpoly(A0));
892: t#0
893: [5] t#0;
894: syntax error
895: 0
896: [6] algv(0);
897: t#0
898: @end example
899:
900: @table @t
1.2 ! noro 901: \JP @item $B;2>H(B
! 902: \EG @item Reference
1.1 noro 903: @fref{newalg}, @fref{defpoly}, @fref{alg}
904: @end table
905:
1.2 ! noro 906: \JP @node simpalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 907: \EG @node simpalg,,, Summary of functions for algebraic numbers
1.1 noro 908: @subsection @code{simpalg}
909: @findex simpalg
910:
911: @table @t
912: @item simpalg(@var{rat})
1.2 ! noro 913: \JP :: $BM-M}<0$K4^$^$l$kBe?tE*?t$r4JC12=$9$k(B.
! 914: \EG :: Simplifies algebraic numbers in a rational expression.
1.1 noro 915: @end table
916:
917: @table @var
918: @item return
1.2 ! noro 919: \JP $BM-M}<0(B
! 920: \EG rational expression
1.1 noro 921: @item rat
1.2 ! noro 922: \JP $BM-M}<0(B
! 923: \EG rational expression
1.1 noro 924: @end table
925:
926: @itemize @bullet
927: @item
1.2 ! noro 928: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 929: \EG Defined in the file @samp{sp}.
1.1 noro 930: @item
1.2 ! noro 931: \BJP
1.1 noro 932: $B?t(B, $BB?9`<0(B, $BM-M}<0$K4^$^$l$kBe?tE*?t$r(B, $B4^$^$l$k(B @code{root} $B$NDj5A(B
933: $BB?9`<0$K$h$j4JC12=$9$k(B.
1.2 ! noro 934: \E
! 935: \BEG
! 936: Simplifies algebraic numbers contained in numbers,
! 937: polynomials, and rational expressions by the defining
! 938: polynomials of @b{root}'s contained in them.
! 939: \E
! 940: @item
! 941: \JP $B?t$N>l9g(B, $BJ,Jl$,$"$l$PM-M}2=$5$l(B, $B7k2L$O(B @code{root} $B$NB?9`<0$H$J$k(B.
! 942: \BEG
! 943: If the argument is a number having the denominator, it is
! 944: rationalized and the result is a polynomial in @b{root}'s.
! 945: \E
! 946: @item
! 947: \JP $BB?9`<0$N>l9g(B, $B3F78?t$,4JC12=$5$l$k(B.
! 948: \EG If the argument is a polynomial, each coefficient is simplified.
! 949: @item
! 950: \JP $BM-M}<0$N>l9g(B, $BJ,JlJ,;R$,B?9`<0$H$7$F4JC12=$5$l$k(B.
! 951: \BEG
! 952: If the argument is a rational expression, its denominator and
! 953: numerator are simplified as a polynomial.
! 954: \E
1.1 noro 955: @end itemize
956:
957: @example
958: [7] simpalg((1+A0)/(1-A0));
959: simpalg undefined
960: return to toplevel
961: [7] load("sp")$
962: [46] simpalg((1+A0)/(1-A0));
963: (-2*#0-3)
964: [47] simpalg((2-A0)/(2+A0)*x^2-1/(3+A0));
965: (-2*#0+3)*x^2+(1/7*#0-3/7)
966: [48] simpalg((x+1/(A0-1))/(x-1/(A0+1)));
967: (x+(#0+1))/(x+(-#0+1))
968: @end example
969:
1.2 ! noro 970: \JP @node algptorat,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 971: \EG @node algptorat,,, Summary of functions for algebraic numbers
1.1 noro 972: @subsection @code{algptorat}
973: @findex algptorat
974:
975: @table @t
976: @item algptorat(@var{poly})
1.2 ! noro 977: \JP :: $BB?9`<0$K4^$^$l$k(B @code{root} $B$r(B, $BBP1~$9$kITDj85$KCV$-49$($k(B.
! 978: \EG :: Substitutes the associated indeterminate for every @b{root}
1.1 noro 979: @end table
980:
981: @table @var
982: @item return
1.2 ! noro 983: \JP $BB?9`<0(B
! 984: \EG polynomial
1.1 noro 985: @item poly
1.2 ! noro 986: \JP $BB?9`<0(B
! 987: \EG polynomial
1.1 noro 988: @end table
989:
990: @itemize @bullet
991: @item
1.2 ! noro 992: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 993: \EG Defined in the file @samp{sp}.
1.1 noro 994: @item
1.2 ! noro 995: \BJP
1.1 noro 996: $BB?9`<0$K4^$^$l$k(B @code{root} @code{#@var{n}} $B$rA4$F(B @code{t#@var{n}} $B$K(B
997: $BCV$-49$($k(B.
1.2 ! noro 998: \E
! 999: \BEG
! 1000: Substitutes the associated indeterminate @code{t#@var{n}}
! 1001: for every @b{root} @code{#@var{n}} in a polynomial.
! 1002: \E
1.1 noro 1003: @end itemize
1004:
1005: @example
1006: [49] algptorat((-2*alg(0)+3)*x^2+(1/7*alg(0)-3/7));
1007: (-2*t#0+3)*x^2+1/7*t#0-3/7
1008: @end example
1009:
1010: @table @t
1.2 ! noro 1011: \JP @item $B;2>H(B
! 1012: \EG @item Reference
1.1 noro 1013: @fref{defpoly}, @fref{algv}
1014: @end table
1015:
1.2 ! noro 1016: \JP @node rattoalgp,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 1017: \EG @node rattoalgp,,, Summary of functions for algebraic numbers
1.1 noro 1018: @subsection @code{rattoalgp}
1019: @findex rattoalgp
1020:
1021: @table @t
1022: @item rattoalgp(@var{poly},@var{alglist})
1.2 ! noro 1023: \BJP
1.1 noro 1024: :: $BB?9`<0$K4^$^$l$k(B @code{root} $B$KBP1~$9$kITDj85$r(B @code{root} $B$K(B
1025: $BCV$-49$($k(B.
1.2 ! noro 1026: \E
! 1027: \BEG
! 1028: :: Substitutes a @b{root} for the associated indeterminate with the
! 1029: @b{root}.
! 1030: \E
1.1 noro 1031: @end table
1032:
1033: @table @var
1034: @item return
1.2 ! noro 1035: \JP $BB?9`<0(B
! 1036: \EG polynomial
1.1 noro 1037: @item poly
1.2 ! noro 1038: \JP $BB?9`<0(B
! 1039: \EG polynomial
1.1 noro 1040: @item alglist
1.2 ! noro 1041: \JP $B%j%9%H(B
! 1042: \EG list
1.1 noro 1043: @end table
1044:
1045: @itemize @bullet
1046: @item
1.2 ! noro 1047: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 1048: \EG Defined in the file @samp{sp}.
1.1 noro 1049: @item
1.2 ! noro 1050: \BJP
1.1 noro 1051: $BBh(B 2 $B0z?t$O(B @code{root} $B$N%j%9%H$G$"$k(B. @code{rattoalgp()} $B$O(B, $B$3$N(B @code{root}
1052: $B$KBP1~$9$kITDj85$r(B, $B$=$l$>$l(B @code{root} $B$KCV$-49$($k(B.
1.2 ! noro 1053: \E
! 1054: \BEG
! 1055: The second argument is a list of @b{root}'s. Function @code{rattoalgp()}
! 1056: substitutes a @b{root} for the associated indeterminate of the @b{root}.
! 1057: \E
1.1 noro 1058: @end itemize
1059:
1060: @example
1061: [51] rattoalgp((-2*algv(0)+3)*x^2+(1/7*algv(0)-3/7),[alg(0)]);
1062: (-2*#0+3)*x^2+(1/7*#0-3/7)
1063: @end example
1064:
1065: @table @t
1.2 ! noro 1066: \JP @item $B;2>H(B
! 1067: \EG @item Reference
1.1 noro 1068: @fref{alg}, @fref{algv}
1069: @end table
1070:
1.2 ! noro 1071: \JP @node cr_gcda,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 1072: \EG @node cr_gcda,,, Summary of functions for algebraic numbers
! 1073: @subsection @code{cr_gcda}
! 1074: @findex cr_gcda
1.1 noro 1075:
1076: @table @t
1.2 ! noro 1077: @item cr_gcda(@var{poly1},@var{poly2},@var{alist})
! 1078: \JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$N(B GCD
! 1079: \EG :: GCD of two uni-variate polynomials over an algebraic number field.
1.1 noro 1080: @end table
1081:
1082: @table @var
1083: @item return
1.2 ! noro 1084: \JP $BB?9`<0(B
! 1085: \EG polynomial
1.1 noro 1086: @item poly1, poly2
1.2 ! noro 1087: \JP $BB?9`<0(B
! 1088: \EG polynomial
1.1 noro 1089: @item alist
1.2 ! noro 1090: \JP $B%j%9%H(B
! 1091: \EG list
1.1 noro 1092: @end table
1093:
1094: @itemize @bullet
1095: @item
1.2 ! noro 1096: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 1097: \EG Defined in the file @samp{sp}.
1.1 noro 1098: @item
1.2 ! noro 1099: \JP 2 $B$D$N(B 1 $BJQ?tB?9`<0$N(B GCD $B$r5a$a$k(B.
! 1100: \EG Finds the GCD of two uni-variate polynomials.
1.1 noro 1101: @item
1.2 ! noro 1102: \BJP
1.1 noro 1103: @var{alist} $B$OF~NO$K8=$l$k(B @code{root} $B$*$h$S(B, $B$=$l$i$NDj5A$K4^$^$l$k(B
1104: @code{root} $B$r:F5"E*$K<h$j=P$7$FJB$Y$?%j%9%H(B. @var{a} $B$,(B @var{b} $B$N(B
1105: $BDj5A$K4^$^$l$F$$$k>l9g(B, @var{a} $B$O(B @var{b} $B$h$j8e(B ($B1&(B) $B$KJB$P$J$1$l$P(B
1106: $B$J$i$J$$(B.
1.2 ! noro 1107: \E
! 1108: \BEG
! 1109: @var{alist} is a list of @b{root}'s.
! 1110: All the @b{root}'s appearing in the input and those required to define
! 1111: the @b{root}'s in the list must appear in the list. In the list
! 1112: ,if the defining polynomial of @var{a} contains @var{b}
! 1113: then @var{a} must come first.
! 1114: \E
1.1 noro 1115: @end itemize
1116:
1117: @example
1118: [76] X=x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16$
1119: [77] Y=x^6+6*x^5+24*x^4+8*x^3-48*x^2+384*x+1024$
1120: [78] A=newalg(X);
1121: (#0)
1.2 ! noro 1122: [79] cr_gcda(X,subst(Y,x,x+A),[A]);
1.1 noro 1123: x+(-#0)
1124: @end example
1125:
1126: @table @t
1.2 ! noro 1127: \JP @item $B;2>H(B
! 1128: \EG @item Reference
1.1 noro 1129: @fref{gr hgr gr_mod}, @fref{asq af}
1130: @end table
1131:
1.2 ! noro 1132: \JP @node sp_norm,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 1133: \EG @node sp_norm,,, Summary of functions for algebraic numbers
1.1 noro 1134: @subsection @code{sp_norm}
1135: @findex sp_norm
1136:
1137: @table @t
1138: @item sp_norm(@var{alg},@var{var},@var{poly},@var{alglist})
1.2 ! noro 1139: \JP :: $BBe?tBN>e$G$N%N%k%`$N7W;;(B
! 1140: \EG :: Norm computation over an algebraic number field.
1.1 noro 1141: @end table
1142:
1143: @table @var
1144: @item return
1.2 ! noro 1145: \JP $BB?9`<0(B
! 1146: \EG polynomial
1.1 noro 1147: @item var
1.2 ! noro 1148: \JP @var{poly} $B$N<gJQ?t(B
! 1149: \EG The main variable of @var{poly}
1.1 noro 1150: @item poly
1.2 ! noro 1151: \JP 1 $BJQ?tB?9`<0(B
! 1152: \EG univariate polynomial
1.1 noro 1153: @item alg
1154: @code{root}
1155: @item alglist
1.2 ! noro 1156: \JP @code{root} $B$N%j%9%H(B
! 1157: \EG @code{root} list
1.1 noro 1158: @end table
1159:
1160: @itemize @bullet
1161: @item
1.2 ! noro 1162: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 1163: \EG Defined in the file @samp{sp}.
1.1 noro 1164: @item
1.2 ! noro 1165: \BJP
1.1 noro 1166: @var{poly} $B$N(B, @var{alg} $B$K4X$9$k%N%k%`$r$H$k(B. $B$9$J$o$A(B,
1167: @b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}) $B$H$9$k$H$-(B,
1168: @var{poly} $B$K8=$l$k(B @var{alg} $B$r(B, @var{alg} $B$N(B @b{K} $B>e$N6&Lr$KCV$-49$($?$b$N(B
1169: $BA4$F$N@Q$rJV$9(B.
1.2 ! noro 1170: \E
! 1171: \BEG
! 1172: Computes the norm of @var{poly} with respect to @var{alg}.
! 1173: Namely, if we write
! 1174: @b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}),
! 1175: The function returns a product of all conjugates of @var{poly},
! 1176: where the conjugate of polynomial @var{poly} is a polynomial
! 1177: in which the algebraic number @var{alg} is substituted
! 1178: for its conjugate over @b{K}.
! 1179: \E
1.1 noro 1180: @item
1.2 ! noro 1181: \JP $B7k2L$O(B @b{K} $B>e$NB?9`<0$H$J$k(B.
! 1182: \EG The result is a polynomial over @b{K}.
1.1 noro 1183: @item
1.2 ! noro 1184: \BJP
1.1 noro 1185: $B<B:]$K$OF~NO$K$h$j>l9g$o$1$,9T$o$l(B, $B=*7k<0$ND>@\7W;;$dCf9q>jM>DjM}$K(B
1186: $B$h$j7W;;$5$l$k$,(B, $B:GE,$JA*Br$,9T$o$l$F$$$k$H$O8B$i$J$$(B.
1187: $BBg0hJQ?t(B @code{USE_RES} $B$r(B 1 $B$K@_Dj$9$k$3$H$K$h$j(B, $B>o$K=*7k<0$K$h$j7W;;(B
1188: $B$5$;$k$3$H$,$G$-$k(B.
1.2 ! noro 1189: \E
! 1190: \BEG
! 1191: The method of computation depends on the input. Currently
! 1192: direct computation of resultant and Chinese remainder theorem
! 1193: are used but the selection is not necessarily optimal.
! 1194: By setting the global variable @code{USE_RES} to 1, the builtin function
! 1195: @code{res()} is always used.
! 1196: \E
1.1 noro 1197: @end itemize
1198:
1199: @example
1200: [0] load("sp")$
1201: [39] A0=newalg(x^2+1)$
1202: [40] A1=newalg(x^2+A0)$
1203: [41] sp_norm(A1,x,x^3+A0*x+A1,[A1,A0]);
1204: x^6+(2*#0)*x^4+(#0^2)*x^2+(#0)
1205: [42] sp_norm(A0,x,@@@@,[A0]);
1206: x^12+2*x^8+5*x^4+1
1207: @end example
1208:
1209: @table @t
1.2 ! noro 1210: \JP @item $B;2>H(B
! 1211: \EG @item Reference
1.1 noro 1212: @fref{res}, @fref{asq af}
1213: @end table
1214:
1.2 ! noro 1215: \JP @node asq af,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 1216: \EG @node asq af,,, Summary of functions for algebraic numbers
1.1 noro 1217: @subsection @code{asq}, @code{af}
1218: @findex asq
1219: @findex af
1220:
1221: @table @t
1222: @item asq(@var{poly})
1.2 ! noro 1223: \JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$NL5J?J}J,2r(B
! 1224: \BEG
! 1225: :: Square-free factorization of polynomial @var{poly} over an
! 1226: algebraic number field.
! 1227: \E
1.1 noro 1228: @item af(@var{poly},@var{alglist})
1.2 ! noro 1229: \JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
! 1230: \BEG
! 1231: :: Factorization of polynomial @var{poly} over an
! 1232: algebraic number field.
! 1233: \E
1.1 noro 1234: @end table
1235:
1236: @table @var
1237: @item return
1.2 ! noro 1238: \JP $B%j%9%H(B
! 1239: \EG list
1.1 noro 1240: @item poly
1.2 ! noro 1241: \JP $BB?9`<0(B
! 1242: \EG polynomial
1.1 noro 1243: @item alglist
1.2 ! noro 1244: \JP @code{root} $B$N%j%9%H(B
! 1245: \EG @code{root} list
1.1 noro 1246: @end table
1247:
1248: @itemize @bullet
1249: @item
1.2 ! noro 1250: \JP $B$$$:$l$b(B @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 1251: \EG Both defined in the file @samp{sp}.
1.1 noro 1252: @item
1.2 ! noro 1253: \BJP
1.1 noro 1254: @code{root} $B$r4^$^$J$$>l9g$O@0?t>e$NH!?t$,8F$S=P$5$l9bB.$G$"$k$,(B,
1.2 ! noro 1255: @code{root} $B$r4^$`>l9g$K$O(B, @code{cr_gcda()} $B$,5/F0$5$l$k$?$a$7$P$7$P(B
1.1 noro 1256: $B;~4V$,$+$+$k(B.
1.2 ! noro 1257: \E
! 1258: \BEG
! 1259: If the inputs contain no @b{root}'s, these functions run fast
! 1260: since they invoke functions over the integers.
! 1261: In contrast to this, if the inputs contain @b{root}'s, they sometimes
! 1262: take a long time, since @code{cr_gcda()} is invoked.
! 1263: \E
1.1 noro 1264: @item
1.2 ! noro 1265: \BJP
1.1 noro 1266: @code{af()} $B$O(B, $B4pACBN$N;XDj(B, $B$9$J$o$ABh(B 2 $B0z?t$N(B, @code{root} $B$N%j%9%H(B
1267: $B$N;XDj$,I,MW$G$"$k(B.
1.2 ! noro 1268: \E
! 1269: \BEG
! 1270: Function @code{af()} requires the specification of base field,
! 1271: i.e., list of @b{root}'s for its second argument.
! 1272: \E
1.1 noro 1273: @item
1.2 ! noro 1274: \BJP
1.1 noro 1275: @code{alglist} $B$G;XDj$5$l$k(B @code{root} $B$O(B, $B8e$GDj5A$5$l$?$b$N$[$IA0$N(B
1276: $BJ}$KMh$J$1$l$P$J$i$J$$(B.
1.2 ! noro 1277: \E
! 1278: \BEG
! 1279: In the second argument @code{alglist}, @b{root} defined last must come
! 1280: first.
! 1281: \E
! 1282: @item
! 1283: \JP $B7k2L$O(B, $BDL>o$NL5J?J}J,2r(B, $B0x?tJ,2r$HF1MM(B [@b{$B0x;R(B}, @b{$B=EJ#EY(B}] $B$N%j%9%H$G$"$k(B.
! 1284: \BEG
! 1285: The result is a list, as a result of usual factorization, whose elements
! 1286: is of the form [@b{factor}, @b{multiplicity}].
! 1287: \E
! 1288: @item
! 1289: \JP $B=EJ#EY$r9~$a$?0x;R$NA4$F$N@Q$O(B, @var{poly} $B$HDj?tG\$N0c$$$,$"$jF@$k(B.
! 1290: \BEG
! 1291: The product of all factors with multiplicities counted may differ from
! 1292: the input polynomial by a constant.
! 1293: \E
1.1 noro 1294: @end itemize
1295:
1296: @example
1297: [99] asq(-x^4+6*x^3+(2*alg(0)-9)*x^2+(-6*alg(0))*x-2);
1298: [[-x^2+3*x+(#0),2]]
1299: [100] af(-x^2+3*x+alg(0),[alg(0)]);
1300: [[x+(#0-1),1],[-x+(#0+2),1]]
1301: @end example
1302:
1303: @table @t
1.2 ! noro 1304: \JP @item $B;2>H(B
! 1305: \EG @item Reference
! 1306: @fref{cr_gcda}, @fref{fctr sqfr}
1.1 noro 1307: @end table
1308:
1.2 ! noro 1309: \JP @node sp,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
! 1310: \EG @node sp,,, Summary of functions for algebraic numbers
1.1 noro 1311: @subsection @code{sp}
1312: @findex sp
1313:
1314: @table @t
1315: @item sp(@var{poly})
1.2 ! noro 1316: \JP :: $B:G>.J,2rBN$r5a$a$k(B.
! 1317: \EG :: Finds the splitting field of polynomial @var{poly} and splits.
1.1 noro 1318: @end table
1319:
1320: @table @var
1321: @item return
1.2 ! noro 1322: \JP $B%j%9%H(B
! 1323: \EG list
1.1 noro 1324: @item poly
1.2 ! noro 1325: \JP $BB?9`<0(B
! 1326: \EG polynomial
1.1 noro 1327: @end table
1328:
1329: @itemize @bullet
1330: @item
1.2 ! noro 1331: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
! 1332: \EG Defined in the file @samp{sp}.
1.1 noro 1333: @item
1.2 ! noro 1334: \BJP
1.1 noro 1335: $BM-M}?t78?t$N(B 1 $BJQ?tB?9`<0(B @var{poly} $B$N:G>.J,2rBN(B, $B$*$h$S$=$NBN>e$G$N(B
1336: @var{poly} $B$N(B 1 $B<!0x;R$X$NJ,2r$r5a$a$k(B.
1.2 ! noro 1337: \E
! 1338: \BEG
! 1339: Finds the splitting field of @var{poly}, an uni-variate polynomial
! 1340: over with rational coefficients, and splits it into its linear factors
! 1341: over the field.
! 1342: \E
1.1 noro 1343: @item
1.2 ! noro 1344: \BJP
1.1 noro 1345: $B7k2L$O(B, @var{poly} $B$N0x;R$N%j%9%H$H(B, $B:G>.J,2rBN$N(B, $BC`<!3HBg$K$h$kI=8=(B
1346: $B$+$i$J$k%j%9%H$G$"$k(B.
1.2 ! noro 1347: \E
! 1348: \BEG
! 1349: The result consists of a two element list: The first element is
! 1350: the list of all linear factors of @var{poly}; the second element is
! 1351: a list which represents the successive extension of the field.
! 1352: \E
1.1 noro 1353: @item
1.2 ! noro 1354: \BJP
1.1 noro 1355: $B:G>.J,2rBN$O(B, @code{[root,algptorat(defpoly(root))]} $B$N%j%9%H$H$7$F(B
1356: $BI=8=$5$l$F$$$k(B. $B$9$J$o$A(B, $B5a$a$k:G>.J,2rBN$O(B, $BM-M}?tBN$K(B, $B$3$N(B @code{root}
1357: $B$rA4$FE:2C$7$?BN$H$7$FF@$i$l$k(B. $BE:2C$O(B, $B1&$NJ}$N(B @code{root} $B$+$i=g$K(B
1358: $B9T$o$l$k(B.
1.2 ! noro 1359: \E
! 1360: \BEG
! 1361: The splitting field is represented as a list of pairs of form
! 1362: @code{[root,algptorat(defpoly(root))]}.
! 1363: In more detail, the list is interpreted as a representation
! 1364: of successive extension obtained by adjoining @b{root}'s
! 1365: to the rational number field. Adjoining is performed from the right
! 1366: @b{root} to the left.
! 1367: \E
1.1 noro 1368: @item
1.2 ! noro 1369: \BJP
1.1 noro 1370: @code{sp()} $B$O(B, $BFbIt$G%N%k%`$N7W;;$N$?$a$K(B @code{sp_norm()} $B$r$7$P$7$P(B
1371: $B5/F0$9$k(B. $B%N%k%`$N7W;;$O(B, $B>u67$K1~$8$F$5$^$6$^$JJ}K!$G9T$o$l$k$,(B,
1372: $B$=$3$GMQ$$$i$l$kJ}K!$,:GA1$H$O8B$i$:(B, $BC1=c$J=*7k<0$N7W;;$NJ}$,9bB.(B
1373: $B$G$"$k>l9g$b$"$k(B.
1374: $BBg0hJQ?t(B @code{USE_RES} $B$r(B 1 $B$K@_Dj$9$k$3$H$K$h$j(B, $B>o$K=*7k<0$K$h$j7W;;(B
1375: $B$5$;$k$3$H$,$G$-$k(B.
1.2 ! noro 1376: \E
! 1377: \BEG
! 1378: @code{sp()} invokes @code{sp_norm()} internally. Computation of norm
! 1379: is done by several methods according to the situation but the algorithm
! 1380: selection is not always optimal and a simple resultant computation is
! 1381: often superior to the other methods.
! 1382: By setting the global variable @code{USE_RES} to 1,
! 1383: the builtin function @code{res()} is always used.
! 1384: \E
1.1 noro 1385: @end itemize
1386:
1387: @example
1388: [101] L=sp(x^9-54);
1389: [[x+(-#2),-54*x+(#1^6*#2^4),54*x+(#1^6*#2^4+54*#2),54*x+(-#1^8*#2^2),
1390: -54*x+(#1^5*#2^5),54*x+(#1^5*#2^5+#1^8*#2^2),-54*x+(-#1^7*#2^3-54*#1),
1391: 54*x+(-#1^7*#2^3),x+(-#1)],[[(#2),t#2^6+t#1^3*t#2^3+t#1^6],[(#1),t#1^9-54]]]
1392: [102] for(I=0,M=1;I<9;I++)M*=L[0][I];
1393: [111] M=simpalg(M);
1394: -1338925209984*x^9+72301961339136
1395: [112] ptozp(M);
1396: -x^9+54
1397: @end example
1398:
1399: @table @t
1.2 ! noro 1400: \JP @item $B;2>H(B
! 1401: \EG @item Reference
1.1 noro 1402: @fref{asq af}, @fref{defpoly}, @fref{algptorat}, @fref{sp_norm}.
1403: @end table
1404:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to algnum.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