Return to algnum.texi CVS log

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

Now 'asir-doc' can produce both English and Japanese versions of
manuals, help files and HTML files. See README for detail.
Though Takayama-san's effort to enhance 'oxweave', it is still
difficult to use it as is for 'asir-doc', so currently 'extract_man.c'
is used to extract manual sources for a specific language.

@comment $OpenXM: OpenXM/src/asir-doc/parts/algnum.texi,v 1.2 1999/12/21 02:47:30 noro Exp $
\BJP
@node $BBe?tE*?t$K4X$9$k1i;;(B,,, Top
@chapter $BBe?tE*?t$K4X$9$k1i;;(B
\E
\BEG
@node Algebraic numbers,,, Top
@chapter Algebraic numbers
\E

@menu
\BJP
* $BBe?tE*?t$NI=8=(B::
* $BBe?tE*?t$N1i;;(B::
* $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B::
* $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B::
\E
\BEG
* Representation of algebraic numbers::
* Operations over algebraic numbers::
* Operations for uni-variate polynomials over an algebraic number field::
* Summary of functions for algebraic numbers::
\E
@end menu

\BJP
@node $BBe?tE*?t$NI=8=(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
@section $BBe?tE*?t$NI=8=(B
\E
\BEG
@node Representation of algebraic numbers,,, Algebraic numbers
@section Representation of algebraic numbers
\E

@noindent
\BJP
@b{Asir} $B$K$*$$$F$O(B, $BBe?tBN$H$$$&BP>]$ODj5A$5$l$J$$(B. 
$BFHN)$7$?BP>]$H$7$FDj5A$5$l$k$N$O(B, $BBe?tE*?t$G$"$k(B. 
$BBe?tBN$O(B, $BM-M}?tBN$K(B, $BBe?tE*?t$rM-8B8D(B
$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
$B$3$l$^$GDj5A$5$l$?Be?tE*?t$NB?9`<0$r78?t$H$9$k(B 1 $BJQ?tB?9`<0(B
$B$rDj5AB?9`<0$H$7$FDj5A$5$l$k(B. $B0J2<(B, $B$"$kDj5AB?9`<0$N:,$H$7$F(B
$BDj5A$5$l$?Be?tE*?t$r(B, @code{root} $B$H8F$V$3$H$K$9$k(B. 
\E
\BEG
In @b{Asir} algebraic number fields are not defined 
as independent objects.
Instead, individual algebraic numbers are defined by some
means. In @b{Asir} an algebraic number field is
defined virtually as a number field obtained by adjoining a finite number
of algebraic numbers to the rational number field.
      
A new algebraic number is introduced in @b{Asir} in such a way where
it is defined as a root of an uni-variate polynomial
whose coefficients include already defined algebraic numbers
as well as rational numbers.
We shall call such a newly defined algebraic number a @b{root}.
Also, we call such an uni-variate polynomial the defining polynomial
of that @b{root}.
\E

@example
[0] A0=newalg(x^2+1);
(#0)
[1] A1=newalg(x^3+A0*x+A0);
(#1)
[2]  [type(A0),ntype(A0)];
[1,2]
@end example

@noindent
\BJP
$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}
$B$r78?t$K4^$`(B @code{x^3+A0*x+A0=0} $B$N:,$H$7$FDj5A$5$l$F$$$k(B. 
\E
\BEG
In this example, the algebraic number assigned to @code{A0} is defined
as a @b{root} of a polynomial @code{x^2+1};
that of @code{A1} is defined as a @b{root} of a polynomial
@code{x^3+A0*x+A0}, which you see contains the previously defined
@b{root} (@code{A0}) in its coefficients.
\E

@noindent
\JP @code{newalg()} $B$N0z?t$9$J$o$ADj5AB?9`<0$K$O<!$N$h$&$J@)8B$,$"$k(B. 
\BEG
The argument to @code{newalg()}, i.e., the defining polynomial,
must satisfy the following conditions.
\E

@enumerate
@item
\JP $BDj5AB?9`<0$O(B 1 $BJQ?tB?9`<0$G$J$1$l$P$J$i$J$$(B. 
\EG A defining polynomial must be an uni-variate polynomial.

@item
\BJP
@code{newalg()} $B$N0z?t$G$"$kDj5AB?9`<0$O(B, $BBe?tE*?t$r4^$`<0$N4JC12=$N$?(B
$B$a$KMQ$$$i$l$k(B. $B$3$N4JC12=$O(B, $BAH$_9~$_H!?t(B @code{srem()} $B$KAjEv$9$kFb(B
$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
$B$J$C$F$$$kI,MW$,$"$k(B.
\E
\BEG
A defining polynomial is used
to simplify expressions containing that algebraic number.
The procedure of such simplification is performed by an internal routine
similar to the built-in function @code{srem()}, where the defining
polynomial is used for the second argument, the divisor.
By this reason, the leading coefficient of the defining polynomial
must be a rational number (must not be an algebraic number.)
\E

@item
\BJP
$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
$B$G$J$1$l$P$J$i$J$$(B. 
\E
\BEG
Every coefficients of a defining polynomial must be
a `(multi-variate) polynomial' in already defined @b{root}'s.
Here, `(multi-variate) polynomial' means a mathematical concept,
not the object type `polynomial' in @b{Asir}.
\E
@item
\BJP
$BDj5AB?9`<0$O(B, $B$=$N78?t$K4^$^$l$kA4$F$N(B @code{root} $B$rM-M}?t$KE:2C$7$?(B
$BBN>e$G4{Ls$G$J$1$l$P$J$i$J$$(B. 
\E
\BEG
A defining polynomial must be irreducible over the field that is obtained
by adjoining all @b{root}'s contained in its coefficients
to the rational number field.
\E
@end enumerate

@noindent
\BJP
@code{newalg()} $B$,9T$&0z?t%A%'%C%/$O(B, 1 $B$*$h$S(B 2 $B$N$_$G$"$k(B. 
$BFC$K(B, $B0z?t$NDj5AB?9`<0$N4{Ls@-$OA4$/%A%'%C%/$5$l$J$$(B. $B$3$l$O(B
$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, 
$B%f!<%6$N@UG$$KG$$5$l$F$$$k(B. 
\E
\BEG
Only the first two conditions (1 and 2) are checked
by function @code{newalg()}.
Among all, it should be emphasized that no check is done for the
irreducibility at all.
The reason is that the irreducibility test requires enormously much
computation time.  You are trusted whether to check it at your own risk.
\E

@noindent
\BJP
$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, 
$B$^$?(B, $B?t$NCf$G$OBe?tE*?t$H$7$F$N<1JL;R$r;}$D(B. (@code{type()}, @code{vtype()}
$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. 
\E
\BEG
Once a @b{root} has been defined by @code{newalg()} function,
it is given the type identifier for a number, and furthermore,
the sub-type identifier for an algebraic number.
(@xref{type}, @ref{ntype}.)
Also, any rational combination of rational numbers and @b{root}'s
is an algebraic number.
\E

@example
[87] N=(A0^2+A1)/(A1^2-A0-1);
((#1+#0^2)/(#1^2-#0-1))
[88] [type(N),ntype(N)];     
[1,2]
@end example

@noindent
\BJP
$BNc$+$i$o$+$k$h$&$K(B, @code{root}$B$O(B @code{#@var{n}}
$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
$BJQ?t$K3JG<$7$FMQ$$$k$+(B, $B$"$k$$$O(B @code{alg(@var{n})} $B$K$h$j<h$j=P$9(B. 
$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
@code{newalg()} $B$r8F$Y$P(B, $B?7$7$$Be?tE*?t$ODj5A$5$l$:$K4{$KDj5A$5$l$?(B
$B$b$N$,F@$i$l$k(B. 
\E
\BEG
As you see it in the example, a @b{root} is displayed as
@code{#@var{n}}.  But, you cannot input that @b{root} in
its immediate output form.
You have to refer to a @b{root} by a program variable assigned
to the @b{root}, or to get it by @code{alg(@var{n})} function, or by
several other indirect means.
A strange use of @code{newalg()}, with a same argument polynomial
(except for the name of its main variable), will yield the old
@b{root} instead of a new @b{root} though it is apparently inefficient.
\E

@example
[90] alg(0);
(#0)
[91] newalg(t^2+1);
(#0)
@end example

@noindent
\JP @code{root} $B$NDj5AB?9`<0$O(B, @code{defpoly()} $B$K$h$j<h$j=P$;$k(B. 
\BEG
The defining polynomial of a @b{root} can be obtained by
@code{defpoly()} function.
\E

@example
[96] defpoly(A0);     
t#0^2+1
[97] defpoly(A1);
t#1^3+t#0*t#1+t#0
@end example

@noindent
\BJP
$B$3$3$G8=$l$?(B, @code{t#0}, @code{t#1} $B$O$=$l$>$l(B @code{#0}, @code{#1} $B$K(B
$BBP1~$9$kITDj85$G$"$k(B. $B$3$l$i$b%f!<%6$,F~NO$9$k$3$H$O$G$-$J$$(B. 
@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. 
\E
\BEG
Here, you see a strange expression, @code{t#0} and @code{t#1}.
They are a specially indeterminates generated and maintained
by @b{Asir} internally.  Indeterminate @code{t#0} corresponds to
@b{root} @code{#0}, and @code{t#0} to @code{#1}.  These indeterminates
also cannot be input directly by a user in their immediate forms.
You can get them by several ways: by @code{var()} function,
or @code{algv(@var{n})} function.
\E

@example
[98] var(@@);
t#1
[99] algv(0);
t#0
[100] 
@end example

\BJP
@node $BBe?tE*?t$N1i;;(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
@section $BBe?tE*?t$N1i;;(B
\E
\BEG
@node Operations over algebraic numbers,,, Algebraic numbers
@section Operations over algebraic numbers
\E

@noindent
\BJP
$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
$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
$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
$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
$B$K$*$+$l$F$$$k(B. 
\E
\BEG
In the previous section, we explained about the
representation of algebraic numbers and their defining method.
Here, we describe operations on algebraic numbers.
Only a few functions are built-in, and almost all functions are provided
as user defined functions.  The file containing their definitions is
@samp{sp}, and it is placed under the same directory
as @samp{gr} is placed, i.e., the standard library directory of @b{Asir}.
\E

@example
[0] load("gr")$
[1] load("sp")$
@end example

@noindent
\JP $B$"$k$$$O(B, $B>o$KMQ$$$k$J$i$P(B, @samp{$HOME/.asirrc} $B$K=q$$$F$*$/$N$b$h$$(B. 
\BEG
Or if you always need them, it is more convenient to include the
@code{load} commands in @samp{$HOME/.asirrc}.
\E

@noindent
\BJP
@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
$B9`<0$K$h$k4JC12=$O<+F0E*$K$O9T$o$l$J$$$N$G(B, $B%f!<%6$NH=CG$GE,599T$o(B
$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, 
$B<B:]$KJ,Jl$r;}$DBe?tE*?t$r@8@.$9$k>l9g$K$O:Y?4$NCm0U$,I,MW$H$J$k(B.
\E
\BEG
Like the other numbers, algebraic numbers can get arithmetic operations
applied. Simplification, however, by defining polynomials are
not automatically performed.  It is left to users to simplify their
expressions.  A fatal error shall result if the denominator expression
will be simplified to 0.  Therefore, be careful enough when you
will create and deal with algebraic numbers which may denominators
in their expressions.
\E

\JP $BBe?tE*?t$N(B, $BDj5AB?9`<0$K$h$k4JC12=$O(B, @code{simpalg()} $B$G9T$&(B. 
\BEG
Use @code{simpalg()} function for simplification of algebraic numbers
by defining polynomials.
\E

@example
[49] T=A0^2+1;
(#0^2+1)
[50] simpalg(T);
0
@end example

@noindent
\JP @code{simpalg()} $B$OM-M}<0$N7A$r$7$?Be?tE*?t$r(B, $BB?9`<0$N7A$K4JC12=$9$k(B. 
\BEG
Function @code{simpalg()} simplifies algebraic numbers which have
the same structures as rational expressions in their appearances.
\E

@example
[39] A0=newalg(x^2+1);      
(#0)
[40] T=(A0^2+A0+1)/(A0+3);
((#0^2+#0+1)/(#0+3))
[41] simpalg(T);
(3/10*#0+1/10)
[42] T=1/(A0^2+1);
((1)/(#0^2+1))
[43] simpalg(T);
div : division by 0
stopped in invalgp at line 258 in file "/usr/local/lib/asir/sp"
258                     return 1/A;
(debug) 
@end example

@noindent
\BJP
$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
$B$?$?$a(B, $B%f!<%6Dj5AH!?t$G$"$k(B @code{simpalg()} $B$NCf$G%G%P%C%,$,8F$P$l$?(B
$B$3$H$r<($9(B. @code{simpalg()} $B$O(B, $BBe?tE*?t$r78?t$H$9$kB?9`<0$N(B
$B3F78?t$r4JC12=$G$-$k(B. 
\E
\BEG
This example shows an error caused by zero division in the course of
program execution of @code{simpalg()}, which attempted to simplify
an algebraic number expression of which the denominator is 0.

Function @code{simpalg()} also can take a polynomial as its argument
and simplifies algebraic numbers in its coefficients.
\E

@example
[43] simpalg(1/A0*x+1/(A0+1));
(-#0)*x+(-1/2*#0+1/2)
@end example

@noindent
\BJP
$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
$B=|$1$PDL>o$N>l9g$HF1MM$G$"$k$,(B, $B0x?tJ,2r$J$I$GIQHK$KMQ$$$i$l$k%N%k%`$N(B
$B7W;;$J$I$K$*$$$F$O(B, @code{root} $B$rITDj85$KCV$-49$($kI,MW$,=P$F$/$k(B. 
$B$3$N>l9g(B, @code{algptorat()} $B$rMQ$$$k(B. 
\E
\BEG
Thus, you can operate in polynomials which contain algebraic numbers
as you do usually in ordinary polynomials,
except for proper simplification by @code{simpalg()}.
You may sometimes feel needs to convert @b{root}'s into indeterminates,
especially when you are working for norm computation in algorithms for
algebraic factorization.
Function @code{algptorat()} is used for such cases.
\E

@example
[83] A0=newalg(x^2+1);
(#0)
[84] A1=newalg(x^3+A0*x+A0);
(#1)
[85] T=(2*A0+A1*A0+A1^2)*x+(1+A1)/(2+A0);
(#1^2+#0*#1+2*#0)*x+((#1+1)/(#0+2))
[86] S=algptorat(T);
(((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)
[87] algptorat(coef(T,1));
t#1^2+t#0*t#1+2*t#0
@end example

@noindent
\BJP
$B$3$N$h$&$K(B, @code{algptorat()} $B$O(B, $BB?9`<0(B, $B?t$K4^$^$l$k(B @code{root}
$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}}
$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. 
$B$3$l$O(B, $B%f!<%6$NF~NO$7$?ITDj85$H(B, @code{root} $B$KBP1~$9$kITDj85$,0lCW(B
$B$7$J$$$h$&$K$9$k$?$a$G$"$k(B. 
\E
\BEG
As you see by the example,
function @code{algptorat()} converts @b{root}'s, @code{#@var{n}},
in polynomials and numbers into its associated indeterminates,
@code{t#@var{n}}.  As was already mentioned those indeterminates cannot
be directly input in their immediate form.
The restriction is adopted to avoid the confusion that might happen
if the user could input such internally generatable indeterminates.
\E

@noindent
\BJP
$B5U$K(B, @code{root} $B$KBP1~$9$kITDj85$r(B, $BBP1~$9$k(B @code{root} $B$KCV$-49$($k(B
$B$?$a$K$O(B @code{rattoalgp()} $B$rMQ$$$k(B. 
\E
\BEG
The associated indeterminate to a @b{root} is reversely converted
into the @b{root} by @code{rattoalgp()} function.
\E

@example
[88] rattoalgp(S,[alg(0)]);
(((#0+2)/(#0+2))*t#1^2+((#0^2+2*#0)/(#0+2))*t#1+((2*#0^2+4*#0)/(#0+2)))*x
+((1)/(#0+2))*t#1+((1)/(#0+2))
[89] rattoalgp(S,[alg(0),alg(1)]);
(((#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
+24*#0^2+16*#0)/(#0^3+6*#0^2+12*#0+8))*x+(((#0+2)*#1+#0+2)/(#0^2+4*#0+4))
[90] rattoalgp(S,[alg(1),alg(0)]);
(((#0+2)*#1^2+(#0^2+2*#0)*#1+2*#0^2+4*#0)/(#0+2))*x+((#1+1)/(#0+2))
[91] simpalg(@@89);
(#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
[92] simpalg(@@90);
(#1^2+#0*#1+2*#0)*x+((-1/5*#0+2/5)*#1-1/5*#0+2/5)
@end example

@noindent
\BJP
@code{rattoalgp()} $B$O(B, $BCV49$NBP>]$H$J$k(B @code{root} $B$N%j%9%H$rBh(B 2 $B0z?t(B
$B$K$H$j(B, $B:8$+$i=g$K(B, $BBP1~$9$kITDj85$rCV$-49$($F9T$/(B. $B$3$NNc$O(B, 
$BCV49$9$k=g=x$r49$($k$H4JC12=$r9T$o$J$$$3$H$K$h$j7k2L$,0l8+0[$J$k$,(B, 
$B4JC12=$K$h$j<B$O0lCW$9$k$3$H$r<($7$F$$$k(B. @code{algptorat()}, 
@code{rattoalgp()} $B$O(B, $B%f!<%6$,FH<+$N4JC12=$r9T$$$?$$>l9g$J$I$K$b(B
$BMQ$$$k$3$H$,$G$-$k(B. 
\E
\BEG
Function @code{rattoalgp()} takes as the second argument
a list consisting of @b{root}'s that you want to convert,
and converts them successively from the left.
This example shows that apparent difference of the results due to
the order of such conversion will vanish by simplification yielding
the same result.
Functions @code{algptorat()} and @code{rattoalgp()} can be conveniently
used for your own simplification.
\E

\BJP
@node $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
@section $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
\E
\BEG
@node Operations for uni-variate polynomials over an algebraic number field,,, Algebraic numbers
@section Operations for uni-variate polynomials over an algebraic number field
\E

@noindent
\BJP
@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
$B:G>.J,2rBN$r5a$a$kH!?t$rDs6!$7$F$$$k(B. 
\E
\BEG
In the file @samp{sp} are provided functions for uni-variate polynomial
factorization and uni-variate polynomial GCD computation
over algebraic numbers,
and furthermore, as an application of them,
functions to compute splitting fields of univariate polynomials.
\E

@menu
* GCD::
\BJP
* $BL5J?J}J,2r(B $B0x?tJ,2r(B::
* $B:G>.J,2rBN(B::
\E
\BEG
* Square-free factorization and Factorization::
* Splitting fields::
\E
@end menu

\JP @node GCD,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
\EG @node GCD,,, Operations for uni-variate polynomials over an algebraic number field
@subsection GCD

@noindent
\BJP
$BBe?tBN>e$G$N(B GCD $B$O(B @code{cr_gcda()} $B$K$h$j7W;;$5$l$k(B. 
$B$3$NH!?t$O%b%8%e%i1i;;$*$h$SCf9q>jM>DjM}$K$h$jBe?tBN>e$N(B GCD $B$r(B
$B7W;;$9$k$b$N$G(B, $BC`<!3HBg$KBP$7$F$bM-8z$G$"$k(B. 
\E
\BEG
Greatest common divisors (GCD) over algebraic number fields are computed
by @code{cr_gcda()} function. This function computes GCD by using modular
computation and Chinese remainder theorem and it works for the case
where the ground field is a multiple extension.
\E

@example
[63] A=newalg(t^9-15*t^6-87*t^3-125);
(#0)
[64] B=newalg(75*s^2+(10*A^7-175*A^4-470*A)*s+3*A^8-45*A^5-261*A^2);
(#1)
[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
+13*A^8-220*A^5-581*A^2)$
[66] P2=x^2+A*x+A^2$
[67] cr_gcda(P1,P2,[B,A]);
27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)
@end example

\BJP
@node $BL5J?J}J,2r(B $B0x?tJ,2r(B,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
@subsection $BL5J?J}J,2r(B, $B0x?tJ,2r(B
\E
\BEG
@node Square-free factorization and Factorization,,, Operations for uni-variate polynomials over an algebraic number field
@subsection Square-free factorization and Factorization
\E

@noindent
\BJP
$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
$B%"%k%4%j%:%`$r:NMQ$7$F$$$k(B. $BH!?t$O(B @code{asq()} $B$G$"$k(B. 
\E
\BEG
For square-free factorization (of uni-variate polynomials over algebraic
number fields), we employ the most fundamental algorithm which begins
first to compute GCD of a polynomial and its derivative.
The function to do this factorization is @code{asq()}.
\E

@example
[116] A=newalg(x^2+x+1);                           
(#4)
[117] T=simpalg((x+A+1)*(x^2-2*A-3)^2*(x^3-x-A)^2);
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
+(-29*#4-31)*x^5+(-15*#4+28)*x^4+(38*#4+29)*x^3+(#4-23)*x^2+(-21*#4-7)*x
+(3*#4+8)
[118] asq(T);
[[x^5+(-2*#4-4)*x^3+(-#4)*x^2+(2*#4+3)*x+(#4-2),2],[x+(#4+1),1]]
@end example

@noindent
\BJP
$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
$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
$B$F8+$d$9$/$9$k$?$a$G(B, $B0x?tJ,2r$G$bF1MM$G$"$k(B.
\E
\BEG
Like factorization over the rational number field,
the result is presented,
commonly to both square-free factorization and factorization,
as a list whose elements are pairs (list of two elements) in the form
 [@b{factor}, @b{multiplicity}]
without the constant multiple part.

Here, it should be noticed that the products of all factors of the
result may DIFFER from the input polynomial by a constant.
The reason is that the factors are normalized so that they have
integral leading coefficients for the sake of readability.

This incongruity may happen to square-free factorization and
factorization commonly.
\E

@noindent
\BJP
$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
$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
$B>l9g$KFC$KM-8z$G$"$k(B. 
\E
\BEG
The algorithm employed for factorization over algebraic number fields
is an improvement of the norm method by Trager.
It is especially very effective to factorize a polynomial over a field
obtained by adjoining some of its @b{root}'s to the base field.
\E

@example
[119] af(T,[A]);
[[x^3-x+(-#4),2],[x^2+(-2*#4-3),2],[x+(#4+1),1]]
@end example

@noindent
\BJP
$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
$BM-M}?tBN$K(B, $B$=$l$i$N(B @code{root} $B$rE:2C$7$?BN>e$G9T$o$l$k(B. 
@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
$BA0$NJ}$K$3$J$1$l$P(B
$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. 
\E
\BEG
The function takes two arguments: The second argument is a list of
@b{root}'s.  Factorization is performed over a field obtained by
adjoining the @b{root}'s to the rational number field.
It is important to keep in mind that the ordering of the @b{root}'s
must obey a restriction: Last defined should come first.
The automatic re-ordering is not done.
It should be done by yourself.
\E

@noindent
\BJP
$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
$B0x?tJ,2r$N8zN($,(B, $BA4BN$N8zN($r:81&$9$k(B. $B$3$N$&$A(B, $BFC$K9b<!$NB?9`<0(B
$B$N>l9g$K8e<T$K$*$$$FAH9g$;GzH/$K$h$j7W;;ITG=$K$J$k>l9g$,$7$P$7$P@8$:$k(B. 
\E
\BEG
The efficiency of factorization via norm depends on the efficiency
of the norm computation and univariate factorization over the rationals.
Especially the latter often causes combinatorial explosion and the
computation will stick in such a case.
\E

@example
[120] B=newalg(x^2-2*A-3);
(#5)
[121] af(T,[B,A]);
[[x+(#5),2],[x^3-x+(-#4),2],[x+(-#5),2],[x+(#4+1),1]]
@end example

\BJP
@node $B:G>.J,2rBN(B,,, $BBe?tBN>e$G$N(B 1 $BJQ?tB?9`<0$N1i;;(B
@subsection $B:G>.J,2rBN(B
\E
\BEG
@node Splitting fields,,, Operations for uni-variate polynomials over an algebraic number field
@subsection Splitting fields
\E

@noindent
\BJP
$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, 
$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. 
\E
\BEG
This operation may be somewhat unusual and for specific interest.
(Galois Group for example.)  Procedurally, however, it is easy to
obtain the splitting field of a polynomial by repeated application
of algebraic factorization described in the previous section.
The function is @code{sp()}.
\E

@example
[103] sp(x^5-2);
[[x+(-#1),2*x+(#0^3*#1^3+#0^4*#1^2+2*#1+2*#0),2*x+(-#0^4*#1^2),2*x
+(-#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],
[(#0),t#0^5-2]]]
@end example

@noindent
\BJP
@code{sp()} $B$O(B 1 $B0z?t$G(B, $B7k2L$O(B @code{[1 $B<!0x;R$N%j%9%H(B, [[root,
algptorat($BDj5AB?9`<0(B)] $B$N%j%9%H(B]} $B$J$k%j%9%H$G$"$k(B. 
$BBh(B 2 $BMWAG$N(B @code{[root,algptorat($BDj5AB?9`<0(B)]} $B$N%j%9%H$O(B, 
$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. 
$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
$B$,J]>Z$5$l$F$$$k(B. 
\E
\BEG
Function @code{sp()} takes only one argument.
The result is a list of two element: The first element is
a list of linear factors, and the second one is a list whose elements
are pairs (list of two elements) in the form
@code{[@b{root}, algptorat(@b{defining polynomial})]}.
The second element, a list of pairs of form
@code{[@b{root},algptorat(@b{defining polynomial})]},
corresponds to the @b{root}'s which are adjoined to eventually obtain
the splitting field.  They are listed in the reverse order of adjoining.
Each of the defining polynomials in the list is, of course,
guaranteed to be irreducible over the field obtained by adjoining all
@b{root}'s defined before it.
\E

@noindent
\BJP
$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
$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
$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()}
$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. 
\E
\BEG
The first element of the result, a list of linear factors, contains
all irreducible factors of the input polynomial over the field
obtained by adjoining all @b{root}'s in the second element of the result.
Because such field is the splitting field of the input polynomial,
factors in the result are all linear as the consequence.

Similarly to function @code{af()}, the product of all resulting factors
may yield a polynomial which differs by a constant.
\E

\BJP
@node $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B,,, $BBe?tE*?t$K4X$9$k1i;;(B
@section $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\E
\BEG
@node Summary of functions for algebraic numbers,,, Algebraic numbers
@section Summary of functions for algebraic numbers
\E
@menu
* newalg::
* defpoly::
* alg::
* algv::
* simpalg::
* algptorat::
* rattoalgp::
* cr_gcda::
* sp_norm::
* asq af::
* sp::
@end menu

\JP @node newalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node newalg,,, Summary of functions for algebraic numbers
@subsection @code{newalg}
@findex newalg

@table @t
@item newalg(@var{defpoly})
\JP :: @code{root} $B$r@8@.$9$k(B. 
\EG :: Creates a new @b{root}.
@end table

@table @var
@item return
\JP $BBe?tE*?t(B (@code{root})
\EG algebraic number (@b{root})
@item defpoly
\JP $BB?9`<0(B
\EG polynomial
@end table

@itemize @bullet
@item
\JP @var{defpoly} $B$rDj5AB?9`<0$H$9$kBe?tE*?t(B (@code{root}) $B$r@8@.$9$k(B. 
\BEG
Creates a new @b{root} (algebraic number) with its defining
polynomial @var{defpoly}.
\E
@item
\JP @var{defpoly} $B$KBP$9$k@)8B$K4X$7$F$O(B, @xref{$BBe?tE*?t$NI=8=(B}.
\BEG
For constraints on @var{defpoly},
@xref{Representation of algebraic numbers}.
\E
@end itemize

@example
[0] A0=newalg(x^2-2);
(#0)
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{defpoly}
@end table

\JP @node defpoly,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node defpoly,,, Summary of functions for algebraic numbers
@subsection @code{defpoly}
@findex defpoly

@table @t
@item defpoly(@var{alg})
\JP :: @code{root} $B$NDj5AB?9`<0$rJV$9(B. 
\EG :: Returns the defining polynomial of @b{root} @var{alg}.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item alg
\JP $BBe?tE*?t(B (@code{root})
\EG algebraic number (@code{root})
@end table

@itemize @bullet
@item
\JP @code{root} @var{alg} $B$NDj5AB?9`<0$rJV$9(B. 
\EG Returns the defining polynomial of @b{root} @var{alg}.
@item
\BJP
@code{root} $B$r(B @code{#@var{n}} $B$H$9$l$P(B, $BDj5AB?9`<0$N<gJQ?t$O(B
@code{t#@var{n}} $B$H$J$k(B. 
\E
\BEG
If the argument @var{alg}, a @b{root}, is @code{#@var{n}},
then the main variable of its defining polynomial is
@code{t#@var{n}}.
\E
@end itemize

@example
[1] defpoly(A0);
t#0^2-2
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{newalg}, @fref{alg}, @fref{algv}
@end table

\JP @node alg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node alg,,, Summary of functions for algebraic numbers
@subsection @code{alg}
@findex alg

@table @t
@item alg(@var{i})
\JP :: $B%$%s%G%C%/%9$KBP1~$9$k(B @code{root} $B$rJV$9(B. 
\EG :: Returns a @b{root} which correspond to the index @var{i}.
@end table

@table @var
@item return
\JP $BBe?tE*?t(B (@code{root})
\EG algebraic number (@code{root})
@item i
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
@item
\JP @code{root} @code{#@var{i}} $B$rJV$9(B. 
\EG Returns @code{#@var{i}}, a @b{root}.
@item
\BJP
@code{#@var{i}} $B$O%f!<%6$,D>@\F~NO$G$-$J$$$?$a(B, @code{alg(@var{i})} $B$H(B
$B$$$&7A$GF~NO$9$k(B. 
\E
\BEG
Because @code{#@var{i}} cannot be input directly,
this function provides an alternative way: input @code{alg(@var{i})}.
\E
@end itemize

@example
[2] x+#0;
syntax error
0
[3] alg(0);
(#0)
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{newalg}, @fref{algv}
@end table

\JP @node algv,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node algv,,, Summary of functions for algebraic numbers
@subsection @code{algv}
@findex algv

@table @t
@item algv(@var{i})
\JP :: @code{alg(@var{i})} $B$KBP1~$9$kITDj85$rJV$9(B. 
\EG :: Returns the associated indeterminate with @code{alg(@var{i})}.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item i
\JP $B@0?t(B
\EG integer
@end table

@itemize @bullet
@item
\JP $BB?9`<0(B @code{t#@var{i}} $B$rJV$9(B. 
\EG Returns an indeterminate @code{t#@var{i}}
@item
\BJP
@code{t#@var{i}} $B$O%f!<%6$,D>@\F~NO$G$-$J$$$?$a(B, @code{algv(@var{i})} $B$H(B
$B$$$&7A$GF~NO$9$k(B. 
\E
\BEG
Since indeterminate @code{t#@var{i}} cannot be input directly,
it is input by @code{algv(@var{i})}.
\E
@end itemize

@example
[4] var(defpoly(A0));
t#0
[5] t#0;
syntax error
0
[6] algv(0);
t#0
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{newalg}, @fref{defpoly}, @fref{alg}
@end table

\JP @node simpalg,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node simpalg,,, Summary of functions for algebraic numbers
@subsection @code{simpalg}
@findex simpalg

@table @t
@item simpalg(@var{rat})
\JP :: $BM-M}<0$K4^$^$l$kBe?tE*?t$r4JC12=$9$k(B. 
\EG :: Simplifies algebraic numbers in a rational expression.
@end table

@table @var
@item return
\JP $BM-M}<0(B
\EG rational expression
@item rat
\JP $BM-M}<0(B
\EG rational expression
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B. 
\EG Defined in the file @samp{sp}.
@item
\BJP
$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
$BB?9`<0$K$h$j4JC12=$9$k(B. 
\E
\BEG
Simplifies algebraic numbers contained in numbers,
polynomials, and rational expressions by the defining
polynomials of @b{root}'s contained in them.
\E
@item
\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. 
\BEG
If the argument is a number having the denominator, it is
rationalized and the result is a polynomial in @b{root}'s.
\E
@item
\JP $BB?9`<0$N>l9g(B, $B3F78?t$,4JC12=$5$l$k(B. 
\EG If the argument is a polynomial, each coefficient is simplified.
@item
\JP $BM-M}<0$N>l9g(B, $BJ,JlJ,;R$,B?9`<0$H$7$F4JC12=$5$l$k(B. 
\BEG
If the argument is a rational expression, its denominator and
numerator are simplified as a polynomial.
\E
@end itemize

@example
[7] simpalg((1+A0)/(1-A0));
simpalg undefined
return to toplevel
[7] load("sp")$
[46] simpalg((1+A0)/(1-A0));
(-2*#0-3)
[47] simpalg((2-A0)/(2+A0)*x^2-1/(3+A0));
(-2*#0+3)*x^2+(1/7*#0-3/7)
[48] simpalg((x+1/(A0-1))/(x-1/(A0+1))); 
(x+(#0+1))/(x+(-#0+1))
@end example

\JP @node algptorat,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node algptorat,,, Summary of functions for algebraic numbers
@subsection @code{algptorat}
@findex algptorat

@table @t
@item algptorat(@var{poly})
\JP :: $BB?9`<0$K4^$^$l$k(B @code{root} $B$r(B, $BBP1~$9$kITDj85$KCV$-49$($k(B. 
\EG :: Substitutes the associated indeterminate for every @b{root}
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly
\JP $BB?9`<0(B
\EG polynomial
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B. 
\EG Defined in the file @samp{sp}.
@item
\BJP
$BB?9`<0$K4^$^$l$k(B @code{root} @code{#@var{n}} $B$rA4$F(B @code{t#@var{n}} $B$K(B
$BCV$-49$($k(B. 
\E
\BEG
Substitutes the associated indeterminate @code{t#@var{n}}
for every @b{root} @code{#@var{n}} in a polynomial.
\E
@end itemize

@example
[49] algptorat((-2*alg(0)+3)*x^2+(1/7*alg(0)-3/7));
(-2*t#0+3)*x^2+1/7*t#0-3/7
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{defpoly}, @fref{algv}
@end table

\JP @node rattoalgp,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node rattoalgp,,, Summary of functions for algebraic numbers
@subsection @code{rattoalgp}
@findex rattoalgp

@table @t
@item rattoalgp(@var{poly},@var{alglist})
\BJP
:: $BB?9`<0$K4^$^$l$k(B @code{root} $B$KBP1~$9$kITDj85$r(B @code{root} $B$K(B
$BCV$-49$($k(B. 
\E
\BEG
:: Substitutes a @b{root} for the associated indeterminate with the
 @b{root}.
\E
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item alglist
\JP $B%j%9%H(B
\EG list
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B. 
\EG Defined in the file @samp{sp}.
@item
\BJP
$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}
$B$KBP1~$9$kITDj85$r(B, $B$=$l$>$l(B @code{root} $B$KCV$-49$($k(B. 
\E
\BEG
The second argument is a list of @b{root}'s. Function @code{rattoalgp()}
substitutes a @b{root} for the associated indeterminate of the @b{root}.
\E
@end itemize

@example
[51] rattoalgp((-2*algv(0)+3)*x^2+(1/7*algv(0)-3/7),[alg(0)]);
(-2*#0+3)*x^2+(1/7*#0-3/7)
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{alg}, @fref{algv}
@end table

\JP @node cr_gcda,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node cr_gcda,,, Summary of functions for algebraic numbers
@subsection @code{cr_gcda}
@findex cr_gcda

@table @t
@item cr_gcda(@var{poly1},@var{poly2},@var{alist})
\JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$N(B GCD
\EG :: GCD of two uni-variate polynomials over an algebraic number field.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly1, poly2
\JP $BB?9`<0(B
\EG polynomial
@item alist
\JP $B%j%9%H(B
\EG list
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B. 
\EG Defined in the file @samp{sp}.
@item
\JP 2 $B$D$N(B 1 $BJQ?tB?9`<0$N(B GCD $B$r5a$a$k(B. 
\EG Finds the GCD of two uni-variate polynomials.
@item
\BJP
@var{alist} $B$OF~NO$K8=$l$k(B @code{root} $B$*$h$S(B, $B$=$l$i$NDj5A$K4^$^$l$k(B
@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
$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
$B$J$i$J$$(B. 
\E
\BEG
@var{alist} is a list of @b{root}'s.
All the @b{root}'s appearing in the input and those required to define
the @b{root}'s in the list  must appear in the list. In the list
,if the defining polynomial of @var{a} contains @var{b}
then @var{a} must come first.
\E
@end itemize

@example
[76] X=x^6+3*x^5+6*x^4+x^3-3*x^2+12*x+16$
[77] Y=x^6+6*x^5+24*x^4+8*x^3-48*x^2+384*x+1024$
[78] A=newalg(X);
(#0)
[79] cr_gcda(X,subst(Y,x,x+A),[A]);
x+(-#0)
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{gr hgr gr_mod}, @fref{asq af}
@end table

\JP @node sp_norm,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node sp_norm,,, Summary of functions for algebraic numbers
@subsection @code{sp_norm}
@findex sp_norm

@table @t
@item sp_norm(@var{alg},@var{var},@var{poly},@var{alglist})
\JP :: $BBe?tBN>e$G$N%N%k%`$N7W;;(B
\EG :: Norm computation over an algebraic number field.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item var
\JP @var{poly} $B$N<gJQ?t(B
\EG The main variable of @var{poly}
@item poly
\JP 1 $BJQ?tB?9`<0(B
\EG univariate polynomial
@item alg
@code{root}
@item alglist
\JP @code{root} $B$N%j%9%H(B
\EG @code{root} list
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B. 
\EG Defined in the file @samp{sp}.
@item
\BJP
@var{poly} $B$N(B, @var{alg} $B$K4X$9$k%N%k%`$r$H$k(B. $B$9$J$o$A(B, 
@b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}) $B$H$9$k$H$-(B, 
@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
$BA4$F$N@Q$rJV$9(B. 
\E
\BEG
Computes the norm of @var{poly} with respect to @var{alg}.
Namely, if we write
@b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}),
The function returns a product of all conjugates of @var{poly},
where the conjugate of polynomial @var{poly} is a polynomial
in which the algebraic number @var{alg} is substituted
for its conjugate over @b{K}.
\E
@item
\JP $B7k2L$O(B @b{K} $B>e$NB?9`<0$H$J$k(B. 
\EG The result is a polynomial over @b{K}.
@item
\BJP
$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
$B$h$j7W;;$5$l$k$,(B, $B:GE,$JA*Br$,9T$o$l$F$$$k$H$O8B$i$J$$(B. 
$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
$B$5$;$k$3$H$,$G$-$k(B. 
\E
\BEG
The method of computation depends on the input. Currently
direct computation of resultant and Chinese remainder theorem
are used but the selection is not necessarily optimal.
By setting the global variable @code{USE_RES} to 1, the builtin function
@code{res()} is always used.
\E
@end itemize

@example
[0] load("sp")$
[39] A0=newalg(x^2+1)$                 
[40] A1=newalg(x^2+A0)$
[41] sp_norm(A1,x,x^3+A0*x+A1,[A1,A0]);
x^6+(2*#0)*x^4+(#0^2)*x^2+(#0)
[42] sp_norm(A0,x,@@@@,[A0]);            
x^12+2*x^8+5*x^4+1
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{res}, @fref{asq af}
@end table

\JP @node asq af,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node asq af,,, Summary of functions for algebraic numbers
@subsection @code{asq}, @code{af}
@findex asq
@findex af

@table @t
@item asq(@var{poly})
\JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$NL5J?J}J,2r(B
\BEG
:: Square-free factorization of polynomial @var{poly} over an
algebraic number field.
\E
@item af(@var{poly},@var{alglist})
\JP :: $BBe?tBN>e$N(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
\BEG
:: Factorization of polynomial @var{poly} over an
algebraic number field.
\E
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item alglist
\JP @code{root} $B$N%j%9%H(B
\EG @code{root} list
@end table

@itemize @bullet
@item
\JP $B$$$:$l$b(B @samp{sp} $B$GDj5A$5$l$F$$$k(B.
\EG Both defined in the file @samp{sp}.
@item
\BJP
@code{root} $B$r4^$^$J$$>l9g$O@0?t>e$NH!?t$,8F$S=P$5$l9bB.$G$"$k$,(B, 
@code{root} $B$r4^$`>l9g$K$O(B, @code{cr_gcda()} $B$,5/F0$5$l$k$?$a$7$P$7$P(B
$B;~4V$,$+$+$k(B. 
\E
\BEG
If the inputs contain no @b{root}'s, these functions run fast
since they invoke functions over the integers.
In contrast to this, if the inputs contain @b{root}'s, they sometimes
take a long time, since @code{cr_gcda()} is invoked.
\E
@item
\BJP
@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
$B$N;XDj$,I,MW$G$"$k(B. 
\E
\BEG
Function @code{af()} requires the specification of base field,
i.e., list of @b{root}'s for its second argument.
\E
@item
\BJP
@code{alglist} $B$G;XDj$5$l$k(B @code{root} $B$O(B, $B8e$GDj5A$5$l$?$b$N$[$IA0$N(B
$BJ}$KMh$J$1$l$P$J$i$J$$(B. 
\E
\BEG
In the second argument @code{alglist}, @b{root} defined last must come
first.
\E
@item
\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. 
\BEG
The result is a list, as a result of usual factorization, whose elements
is of the form [@b{factor}, @b{multiplicity}].
\E
@item
\JP $B=EJ#EY$r9~$a$?0x;R$NA4$F$N@Q$O(B, @var{poly} $B$HDj?tG\$N0c$$$,$"$jF@$k(B. 
\BEG
The product of all factors with multiplicities counted may differ from
the input polynomial by a constant.
\E
@end itemize

@example
[99] asq(-x^4+6*x^3+(2*alg(0)-9)*x^2+(-6*alg(0))*x-2);
[[-x^2+3*x+(#0),2]]
[100] af(-x^2+3*x+alg(0),[alg(0)]);
[[x+(#0-1),1],[-x+(#0+2),1]]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{cr_gcda}, @fref{fctr sqfr}
@end table

\JP @node sp,,, $BBe?tE*?t$K4X$9$kH!?t$N$^$H$a(B
\EG @node sp,,, Summary of functions for algebraic numbers
@subsection @code{sp}
@findex sp

@table @t
@item sp(@var{poly})
\JP :: $B:G>.J,2rBN$r5a$a$k(B. 
\EG :: Finds the splitting field of polynomial @var{poly} and splits.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BB?9`<0(B
\EG polynomial
@end table

@itemize @bullet
@item
\JP @samp{sp} $B$GDj5A$5$l$F$$$k(B.
\EG Defined in the file @samp{sp}.
@item
\BJP
$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
@var{poly} $B$N(B 1 $B<!0x;R$X$NJ,2r$r5a$a$k(B. 
\E
\BEG
Finds the splitting field of @var{poly}, an uni-variate polynomial
over with rational coefficients, and splits it into its linear factors
over the field.
\E
@item
\BJP
$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
$B$+$i$J$k%j%9%H$G$"$k(B. 
\E
\BEG
The result consists of a two element list: The first element is
the list of all linear factors of @var{poly}; the second element is
a list which represents the successive extension of the field.
\E
@item
\BJP
$B:G>.J,2rBN$O(B, @code{[root,algptorat(defpoly(root))]} $B$N%j%9%H$H$7$F(B
$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}
$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
$B9T$o$l$k(B. 
\E
\BEG
The splitting field is represented as a list of pairs of form
@code{[root,algptorat(defpoly(root))]}.
In more detail, the list is interpreted as a representation
of successive extension obtained by adjoining @b{root}'s
to the rational number field.  Adjoining is performed from the right
@b{root} to the left.
\E
@item
\BJP
@code{sp()} $B$O(B, $BFbIt$G%N%k%`$N7W;;$N$?$a$K(B @code{sp_norm()} $B$r$7$P$7$P(B
$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, 
$B$=$3$GMQ$$$i$l$kJ}K!$,:GA1$H$O8B$i$:(B, $BC1=c$J=*7k<0$N7W;;$NJ}$,9bB.(B
$B$G$"$k>l9g$b$"$k(B. 
$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
$B$5$;$k$3$H$,$G$-$k(B. 
\E
\BEG
@code{sp()} invokes @code{sp_norm()} internally. Computation of norm
is done by several methods according to the situation but the algorithm
selection is not always optimal and a simple resultant computation is
often superior to the other methods.
By setting the global variable @code{USE_RES} to 1,
the builtin function @code{res()} is always used.
\E
@end itemize

@example
[101] L=sp(x^9-54);
[[x+(-#2),-54*x+(#1^6*#2^4),54*x+(#1^6*#2^4+54*#2),54*x+(-#1^8*#2^2),
-54*x+(#1^5*#2^5),54*x+(#1^5*#2^5+#1^8*#2^2),-54*x+(-#1^7*#2^3-54*#1),
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]]]
[102] for(I=0,M=1;I<9;I++)M*=L[0][I];
[111] M=simpalg(M);
-1338925209984*x^9+72301961339136
[112] ptozp(M);
-x^9+54
@end example

@table @t
\JP @item $B;2>H(B
\EG @item Reference
@fref{asq af}, @fref{defpoly}, @fref{algptorat}, @fref{sp_norm}.
@end table