Return to algnum.texi CVS log

Up to [local] / OpenXM / src / asir-doc / parts

Annotation of OpenXM/src/asir-doc/parts/algnum.texi, Revision 1.6

1.6     ! noro        1: @comment $OpenXM: OpenXM/src/asir-doc/parts/algnum.texi,v 1.5 2000/09/23 07:53:24 noro Exp $
1.2       noro        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.3       noro      505: [67] cr_gcda(P1,P2);
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::
1.4       noro      709: * asq af af_noalg::
                    710: * sp sp_noalg::
1.1       noro      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.3       noro     1077: @item cr_gcda(@var{poly1},@var{poly2})
1.2       noro     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.6     ! noro     1086: @item poly1  poly2
1.2       noro     1087: \JP $BB?9`<0(B
                   1088: \EG polynomial
1.1       noro     1089: @end table
                   1090:
                   1091: @itemize @bullet
                   1092: @item
1.2       noro     1093: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
                   1094: \EG Defined in the file @samp{sp}.
1.1       noro     1095: @item
1.2       noro     1096: \JP 2 $B$D$N(B 1 $BJQ?tB?9`<0$N(B GCD $B$r5a$a$k(B.
                   1097: \EG Finds the GCD of two uni-variate polynomials.
1.1       noro     1098: @end itemize
                   1099:
                   1100: @example
                   1101: [76] X=x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16$
                   1102: [77] Y=x^6+6*x^5+24*x^4+8*x^3-48*x^2+384*x+1024$
                   1103: [78] A=newalg(X);
                   1104: (#0)
1.3       noro     1105: [79] cr_gcda(X,subst(Y,x,x+A));
1.1       noro     1106: x+(-#0)
                   1107: @end example
                   1108:
                   1109: @table @t
1.2       noro     1110: \JP @item $B;2>H(B
                   1111: \EG @item Reference
1.4       noro     1112: @fref{gr hgr gr_mod}, @fref{asq af af_noalg}
1.1       noro     1113: @end table
                   1114:
1.2       noro     1115: \JP @node sp_norm,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
                   1116: \EG @node sp_norm,,, Summary of functions for algebraic numbers
1.1       noro     1117: @subsection @code{sp_norm}
                   1118: @findex sp_norm
                   1119:
                   1120: @table @t
                   1121: @item sp_norm(@var{alg},@var{var},@var{poly},@var{alglist})
1.2       noro     1122: \JP :: $BBe?tBN>e$G$N%N%k%`$N7W;;(B
                   1123: \EG :: Norm computation over an algebraic number field.
1.1       noro     1124: @end table
                   1125:
                   1126: @table @var
                   1127: @item return
1.2       noro     1128: \JP $BB?9`<0(B
                   1129: \EG polynomial
1.1       noro     1130: @item var
1.2       noro     1131: \JP @var{poly} $B$N<gJQ?t(B
                   1132: \EG The main variable of @var{poly}
1.1       noro     1133: @item poly
1.2       noro     1134: \JP 1 $BJQ?tB?9`<0(B
                   1135: \EG univariate polynomial
1.1       noro     1136: @item alg
                   1137: @code{root}
                   1138: @item alglist
1.2       noro     1139: \JP @code{root} $B$N%j%9%H(B
                   1140: \EG @code{root} list
1.1       noro     1141: @end table
                   1142:
                   1143: @itemize @bullet
                   1144: @item
1.2       noro     1145: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
                   1146: \EG Defined in the file @samp{sp}.
1.1       noro     1147: @item
1.2       noro     1148: \BJP
1.1       noro     1149: @var{poly} $B$N(B, @var{alg} $B$K4X$9$k%N%k%`$r$H$k(B. $B$9$J$o$A(B,
                   1150: @b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}) $B$H$9$k$H$-(B,
                   1151: @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
                   1152: $BA4$F$N@Q$rJV$9(B.
1.2       noro     1153: \E
                   1154: \BEG
                   1155: Computes the norm of @var{poly} with respect to @var{alg}.
                   1156: Namely, if we write
                   1157: @b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}),
                   1158: The function returns a product of all conjugates of @var{poly},
                   1159: where the conjugate of polynomial @var{poly} is a polynomial
                   1160: in which the algebraic number @var{alg} is substituted
                   1161: for its conjugate over @b{K}.
                   1162: \E
1.1       noro     1163: @item
1.2       noro     1164: \JP $B7k2L$O(B @b{K} $B>e$NB?9`<0$H$J$k(B.
                   1165: \EG The result is a polynomial over @b{K}.
1.1       noro     1166: @item
1.2       noro     1167: \BJP
1.1       noro     1168: $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
                   1169: $B$h$j7W;;$5$l$k$,(B, $B:GE,$JA*Br$,9T$o$l$F$$$k$H$O8B$i$J$$(B.
                   1170: $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
                   1171: $B$5$;$k$3$H$,$G$-$k(B.
1.2       noro     1172: \E
                   1173: \BEG
                   1174: The method of computation depends on the input. Currently
                   1175: direct computation of resultant and Chinese remainder theorem
                   1176: are used but the selection is not necessarily optimal.
                   1177: By setting the global variable @code{USE_RES} to 1, the builtin function
                   1178: @code{res()} is always used.
                   1179: \E
1.1       noro     1180: @end itemize
                   1181:
                   1182: @example
                   1183: [0] load("sp")$
                   1184: [39] A0=newalg(x^2+1)$
                   1185: [40] A1=newalg(x^2+A0)$
                   1186: [41] sp_norm(A1,x,x^3+A0*x+A1,[A1,A0]);
                   1187: x^6+(2*#0)*x^4+(#0^2)*x^2+(#0)
                   1188: [42] sp_norm(A0,x,@@@@,[A0]);
                   1189: x^12+2*x^8+5*x^4+1
                   1190: @end example
                   1191:
                   1192: @table @t
1.2       noro     1193: \JP @item $B;2>H(B
                   1194: \EG @item Reference
1.4       noro     1195: @fref{res}, @fref{asq af af_noalg}
1.1       noro     1196: @end table
                   1197:
1.4       noro     1198: \JP @node asq af af_noalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
                   1199: \EG @node asq af af_noalg,,, Summary of functions for algebraic numbers
                   1200: @subsection @code{asq}, @code{af}, @code{af_noalg}
1.1       noro     1201: @findex asq
                   1202: @findex af
1.4       noro     1203: @findex af_noalg
1.1       noro     1204:
                   1205: @table @t
                   1206: @item asq(@var{poly})
1.2       noro     1207: \JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$NL5J?J}J,2r(B
                   1208: \BEG
                   1209: :: Square-free factorization of polynomial @var{poly} over an
                   1210: algebraic number field.
                   1211: \E
1.1       noro     1212: @item af(@var{poly},@var{alglist})
1.4       noro     1213: @itemx af_noalg(@var{poly},@var{defpolylist})
1.2       noro     1214: \JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
                   1215: \BEG
                   1216: :: Factorization of polynomial @var{poly} over an
                   1217: algebraic number field.
                   1218: \E
1.1       noro     1219: @end table
                   1220:
                   1221: @table @var
                   1222: @item return
1.2       noro     1223: \JP $B%j%9%H(B
                   1224: \EG list
1.1       noro     1225: @item poly
1.2       noro     1226: \JP $BB?9`<0(B
                   1227: \EG polynomial
1.1       noro     1228: @item alglist
1.2       noro     1229: \JP @code{root} $B$N%j%9%H(B
                   1230: \EG @code{root} list
1.4       noro     1231: @item defpolylist
                   1232: \JP @code{root} $B$rI=$9ITDj85$HDj5AB?9`<0$N%Z%"$N%j%9%H(B
                   1233: \EG @code{root} list of pairs of an indeterminate and a polynomial
1.1       noro     1234: @end table
                   1235:
                   1236: @itemize @bullet
                   1237: @item
1.2       noro     1238: \JP $B$$$:$l$b(B @samp{sp} $B$GDj5A$5$l$F$$$k(B.
                   1239: \EG Both defined in the file @samp{sp}.
1.1       noro     1240: @item
1.2       noro     1241: \BJP
1.1       noro     1242: @code{root} $B$r4^$^$J$$>l9g$O@0?t>e$NH!?t$,8F$S=P$5$l9bB.$G$"$k$,(B,
1.2       noro     1243: @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     1244: $B;~4V$,$+$+$k(B.
1.2       noro     1245: \E
                   1246: \BEG
                   1247: If the inputs contain no @b{root}'s, these functions run fast
                   1248: since they invoke functions over the integers.
                   1249: In contrast to this, if the inputs contain @b{root}'s, they sometimes
                   1250: take a long time, since @code{cr_gcda()} is invoked.
                   1251: \E
1.1       noro     1252: @item
1.2       noro     1253: \BJP
1.1       noro     1254: @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
                   1255: $B$N;XDj$,I,MW$G$"$k(B.
1.2       noro     1256: \E
                   1257: \BEG
                   1258: Function @code{af()} requires the specification of base field,
                   1259: i.e., list of @b{root}'s for its second argument.
                   1260: \E
1.1       noro     1261: @item
1.2       noro     1262: \BJP
1.1       noro     1263: @code{alglist} $B$G;XDj$5$l$k(B @code{root} $B$O(B, $B8e$GDj5A$5$l$?$b$N$[$IA0$N(B
                   1264: $BJ}$KMh$J$1$l$P$J$i$J$$(B.
1.2       noro     1265: \E
                   1266: \BEG
                   1267: In the second argument @code{alglist}, @b{root} defined last must come
                   1268: first.
                   1269: \E
                   1270: @item
1.4       noro     1271: \BJP
1.5       noro     1272: @code{af(F,AL)} $B$K$*$$$F(B, @code{AL} $B$OBe?tE*?t$N%j%9%H$G$"$j(B, $BM-M}?tBN$N(B
                   1273: $BBe?t3HBg$rI=$9(B. @code{AL=[An,...,A1]} $B$H=q$/$H$-(B, $B3F(B @code{Ak} $B$O(B, $B$=$l$h$j(B
                   1274: $B1&$K$"$kBe?tE*?t$r78?t$H$7$?(B, $B%b%K%C%/$JDj5AB?9`<0$GDj5A$5$l$F$$$J$1$l$P(B
                   1275: $B$J$i$J$$(B.
                   1276: \E
                   1277: \BEG
                   1278: In @code{af(F,AL)}, @code{AL} denotes a list of @code{roots} and it
                   1279: represents an algebraic number field. In @code{AL=[An,...,A1]} each
                   1280: @code{Ak} should be defined as a root of a defining polynomial
                   1281: whose coefficients are in @code{Q(A(k+1),...,An)}.
                   1282: \E
                   1283:
                   1284: @example
                   1285: [1] A1 = newalg(x^2+1);
                   1286: [2] A2 = newalg(x^2+A1);
                   1287: [3] A3 = newalg(x^2+A2*x+A1);
                   1288: [4] af(x^2+A2*x+A1,[A2,A1]);
                   1289: [[x^2+(#1)*x+(#0),1]]
                   1290: @end example
                   1291:
                   1292: \BJP
                   1293: @code{af_noalg} $B$G$O(B, @var{poly} $B$K4^$^$l$kBe?tE*?t(B @var{ai} $B$rITDj85(B @var{vi}
1.6     ! noro     1294: $B$GCV$-49$($k(B. @code{defpolylist} $B$O(B, [[vn,dn(vn,...,v1)],...,[v1,d(v1)]]
        !          1295: $B$J$k%j%9%H$G$"$k(B. $B$3$3$G(B @var{di}(vi,...,v1) $B$O(B @var{ai} $B$NDj5AB?9`<0$K$*$$$F(B
1.4       noro     1296: $BBe?tE*?t$rA4$F(B @var{vj} $B$KCV$-49$($?$b$N$G$"$k(B.
                   1297: \E
                   1298: \BEG
                   1299: To call @code{sp_noalg}, one should replace each algebraic number
                   1300: @var{ai} in @var{poly} with an indeterminate @var{vi}. @code{defpolylist}
1.6     ! noro     1301: is a list [[vn,dn(vn,...,v1)],...,[v1,d(v1)]]. In this expression
        !          1302: @var{di}(vi,...,v1) is a defining polynomial of @var{ai} represented
1.4       noro     1303: as a multivariate polynomial.
                   1304: \E
1.5       noro     1305:
                   1306: @example
                   1307: [1] af_noalg(x^2+a2*x+a1,[[a2,a2^2+a1],[a1,a1^2+1]]);
                   1308: [[x^2+a2*x+a1,1]]
                   1309: @end example
                   1310:
1.4       noro     1311: @item
                   1312: \BJP
                   1313: $B7k2L$O(B, $BDL>o$NL5J?J}J,2r(B, $B0x?tJ,2r$HF1MM(B [@b{$B0x;R(B}, @b{$B=EJ#EY(B}]
                   1314: $B$N%j%9%H$G$"$k(B. @code{af_noalg} $B$N>l9g(B, @b{$B0x;R(B} $B$K8=$l$kBe?tE*?t$O(B,
                   1315: @var{defpolylist} $B$K=>$C$FITDj85$KCV$-49$($i$l$k(B.
                   1316: \E
1.2       noro     1317: \BEG
                   1318: The result is a list, as a result of usual factorization, whose elements
1.4       noro     1319: is of the form [@b{factor}, @b{multiplicity}].
                   1320: In the result of @code{af_noalg}, algebraic numbers in @v{factor} are
                   1321: replaced by the indeterminates according to @var{defpolylist}.
1.2       noro     1322: \E
                   1323: @item
                   1324: \JP $B=EJ#EY$r9~$a$?0x;R$NA4$F$N@Q$O(B, @var{poly} $B$HDj?tG\$N0c$$$,$"$jF@$k(B.
                   1325: \BEG
                   1326: The product of all factors with multiplicities counted may differ from
                   1327: the input polynomial by a constant.
                   1328: \E
1.1       noro     1329: @end itemize
                   1330:
                   1331: @example
1.5       noro     1332: [98] A = newalg(t^2-2);
                   1333: (#0)
1.1       noro     1334: [99] asq(-x^4+6*x^3+(2*alg(0)-9)*x^2+(-6*alg(0))*x-2);
                   1335: [[-x^2+3*x+(#0),2]]
                   1336: [100] af(-x^2+3*x+alg(0),[alg(0)]);
                   1337: [[x+(#0-1),1],[-x+(#0+2),1]]
1.5       noro     1338: [101] af_noalg(-x^2+3*x+a,[[a,x^2-2]]);
                   1339: [[x+a-1,1],[-x+a+2,1]]
1.1       noro     1340: @end example
                   1341:
                   1342: @table @t
1.2       noro     1343: \JP @item $B;2>H(B
                   1344: \EG @item Reference
                   1345: @fref{cr_gcda}, @fref{fctr sqfr}
1.1       noro     1346: @end table
                   1347:
1.4       noro     1348: \JP @node sp sp_noalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
                   1349: \EG @node sp sp_noalg,,, Summary of functions for algebraic numbers
                   1350: @subsection @code{sp}, @code{sp_noalg}
1.1       noro     1351: @findex sp
                   1352:
                   1353: @table @t
                   1354: @item sp(@var{poly})
1.4       noro     1355: @itemx sp_noalg(@var{poly})
1.2       noro     1356: \JP :: $B:G>.J,2rBN$r5a$a$k(B.
                   1357: \EG :: Finds the splitting field of polynomial @var{poly} and splits.
1.1       noro     1358: @end table
                   1359:
                   1360: @table @var
                   1361: @item return
1.2       noro     1362: \JP $B%j%9%H(B
                   1363: \EG list
1.1       noro     1364: @item poly
1.2       noro     1365: \JP $BB?9`<0(B
                   1366: \EG polynomial
1.1       noro     1367: @end table
                   1368:
                   1369: @itemize @bullet
                   1370: @item
1.2       noro     1371: \JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
                   1372: \EG Defined in the file @samp{sp}.
1.1       noro     1373: @item
1.2       noro     1374: \BJP
1.1       noro     1375: $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
                   1376: @var{poly} $B$N(B 1 $B<!0x;R$X$NJ,2r$r5a$a$k(B.
1.2       noro     1377: \E
                   1378: \BEG
                   1379: Finds the splitting field of @var{poly}, an uni-variate polynomial
                   1380: over with rational coefficients, and splits it into its linear factors
                   1381: over the field.
                   1382: \E
1.1       noro     1383: @item
1.2       noro     1384: \BJP
1.1       noro     1385: $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
1.4       noro     1386: $B$+$i$J$k%j%9%H$G$"$k(B. @code{sp_noalg} $B$G$O(B, $BA4$F$NBe?tE*?t$,(B, $BBP1~$9$k(B
                   1387: $BITDj85(B ($BB($A(B @code{#i} $B$KBP$9$k(B @code{t#i}) $B$KCV$-49$($i$l$k(B. $B$3$l$K(B
                   1388: $B$h$j(B, @code{sp_noalg} $B$N=PNO$O(B, $B@0?t78?tB?JQ?tB?9`<0$N%j%9%H$H$J$k(B.
1.2       noro     1389: \E
                   1390: \BEG
                   1391: The result consists of a two element list: The first element is
                   1392: the list of all linear factors of @var{poly}; the second element is
                   1393: a list which represents the successive extension of the field.
1.4       noro     1394: In the result of @code{sp_noalg} all the algebraic numbers are replaced
                   1395: by the special indeterminate associated with it, that is @code{t#i}
                   1396: for @code{#i}. By this operation the result of @code{sp_noalg}
                   1397: is a list containing only integral polynomials.
1.2       noro     1398: \E
1.1       noro     1399: @item
1.2       noro     1400: \BJP
1.1       noro     1401: $B:G>.J,2rBN$O(B, @code{[root,algptorat(defpoly(root))]} $B$N%j%9%H$H$7$F(B
                   1402: $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}
                   1403: $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
                   1404: $B9T$o$l$k(B.
1.2       noro     1405: \E
                   1406: \BEG
                   1407: The splitting field is represented as a list of pairs of form
                   1408: @code{[root,algptorat(defpoly(root))]}.
                   1409: In more detail, the list is interpreted as a representation
                   1410: of successive extension obtained by adjoining @b{root}'s
                   1411: to the rational number field.  Adjoining is performed from the right
                   1412: @b{root} to the left.
                   1413: \E
1.1       noro     1414: @item
1.2       noro     1415: \BJP
1.1       noro     1416: @code{sp()} $B$O(B, $BFbIt$G%N%k%`$N7W;;$N$?$a$K(B @code{sp_norm()} $B$r$7$P$7$P(B
                   1417: $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,
                   1418: $B$=$3$GMQ$$$i$l$kJ}K!$,:GA1$H$O8B$i$:(B, $BC1=c$J=*7k<0$N7W;;$NJ}$,9bB.(B
                   1419: $B$G$"$k>l9g$b$"$k(B.
                   1420: $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
                   1421: $B$5$;$k$3$H$,$G$-$k(B.
1.2       noro     1422: \E
                   1423: \BEG
                   1424: @code{sp()} invokes @code{sp_norm()} internally. Computation of norm
                   1425: is done by several methods according to the situation but the algorithm
                   1426: selection is not always optimal and a simple resultant computation is
                   1427: often superior to the other methods.
                   1428: By setting the global variable @code{USE_RES} to 1,
                   1429: the builtin function @code{res()} is always used.
                   1430: \E
1.1       noro     1431: @end itemize
                   1432:
                   1433: @example
                   1434: [101] L=sp(x^9-54);
                   1435: [[x+(-#2),-54*x+(#1^6*#2^4),54*x+(#1^6*#2^4+54*#2),54*x+(-#1^8*#2^2),
                   1436: -54*x+(#1^5*#2^5),54*x+(#1^5*#2^5+#1^8*#2^2),-54*x+(-#1^7*#2^3-54*#1),
                   1437: 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]]]
                   1438: [102] for(I=0,M=1;I<9;I++)M*=L[0][I];
                   1439: [111] M=simpalg(M);
                   1440: -1338925209984*x^9+72301961339136
                   1441: [112] ptozp(M);
                   1442: -x^9+54
                   1443: @end example
                   1444:
                   1445: @table @t
1.2       noro     1446: \JP @item $B;2>H(B
                   1447: \EG @item Reference
1.4       noro     1448: @fref{asq af af_noalg}, @fref{defpoly}, @fref{algptorat}, @fref{sp_norm}.
1.1       noro     1449: @end table
                   1450: