@comment $OpenXM: OpenXM/src/asir-doc/parts/algnum.texi,v 1.4 2000/03/17 02:17:03 noro Exp $
\BJP
@node 代数的数に関する演算,,, Top
@chapter 代数的数に関する演算
\E
\BEG
@node Algebraic numbers,,, Top
@chapter Algebraic numbers
\E

@menu
\BJP
* 代数的数の表現::
* 代数的数の演算::
* 代数体上での 1 変数多項式の演算::
* 代数的数に関する函数のまとめ::
\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 代数的数の表現,,, 代数的数に関する演算
@section 代数的数の表現
\E
\BEG
@node Representation of algebraic numbers,,, Algebraic numbers
@section Representation of algebraic numbers
\E

@noindent
\BJP
@b{Asir} においては, 代数体という対象は定義されない. 
独立した対象として定義されるのは, 代数的数である. 
代数体は, 有理数体に, 代数的数を有限個
順次添加した体として仮想的に定義される. 新たな代数的数は, 有理数および
これまで定義された代数的数の多項式を係数とする 1 変数多項式
を定義多項式として定義される. 以下, ある定義多項式の根として
定義された代数的数を, @code{root} と呼ぶことにする. 
\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
この例では, @code{A0} は @code{x^2+1=0} の根, @code{A1} は, その @code{A0}
を係数に含む @code{x^3+A0*x+A0=0} の根として定義されている. 
\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()} の引数すなわち定義多項式には次のような制限がある. 
\BEG
The argument to @code{newalg()}, i.e., the defining polynomial,
must satisfy the following conditions.
\E

@enumerate
@item
\JP 定義多項式は 1 変数多項式でなければならない. 
\EG A defining polynomial must be an uni-variate polynomial.

@item
\BJP
@code{newalg()} の引数である定義多項式は, 代数的数を含む式の簡単化のた
めに用いられる. この簡単化は, 組み込み函数 @code{srem()} に相当する内
部ルーチンを用いて行われる. このため, 定義多項式の主係数は, 有理数に
なっている必要がある.
\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
定義多項式の係数は すでに定義されている @code{root} の有理数係数多項式
でなければならない. 
\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
定義多項式は, その係数に含まれる全ての @code{root} を有理数に添加した
体上で既約でなければならない. 
\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()} が行う引数チェックは, 1 および 2 のみである. 
特に, 引数の定義多項式の既約性は全くチェックされない. これは
既約性のチェックが多大な計算量を必要とするためで, この点に関しては, 
ユーザの責任に任されている. 
\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
一旦 @code{newalg()} によって定義された代数的数は, 数としての識別子を持ち, 
また, 数の中では代数的数としての識別子を持つ. (@code{type()}, @code{vtype()}
参照.) さらに, 有理数と, @code{root} の有理式も同様に代数的数となる. 
\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
例からわかるように, @code{root}は @code{#@var{n}}
と表示される. しかし, ユーザはこの形では入力できない. @code{root} は
変数に格納して用いるか, あるいは @code{alg(@var{n})} により取り出す. 
また, 効率は落ちるが, 全く同じ引数 (変数は異なっていてもよい) により
@code{newalg()} を呼べば, 新しい代数的数は定義されずに既に定義された
ものが得られる. 
\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} の定義多項式は, @code{defpoly()} により取り出せる. 
\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
ここで現れた, @code{t#0}, @code{t#1} はそれぞれ @code{#0}, @code{#1} に
対応する不定元である. これらもユーザが入力することはできない. 
@code{var()} で取り出すか, あるいは @code{algv(@var{n})} により取り出す. 
\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 代数的数の演算,,, 代数的数に関する演算
@section 代数的数の演算
\E
\BEG
@node Operations over algebraic numbers,,, Algebraic numbers
@section Operations over algebraic numbers
\E

@noindent
\BJP
前節で, 代数的数の表現, 定義について述べた. ここでは, 代数的数を用いた
演算について述べる. 代数的数に関しては, 組み込み函数として提供されている
機能はごく少数で, 大部分はユーザ定義函数により実現されている. ファイル
は, @samp{sp} で, @samp{gr} と同様 @b{Asir} の標準ライブラリディレクトリ
におかれている. 
\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 あるいは, 常に用いるならば, @samp{$HOME/.asirrc} に書いておくのもよい. 
\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} は その他の数と同様, 四則演算が可能となる. しかし, 定義多
項式による簡単化は自動的には行われないので, ユーザの判断で適宜行わ
なければならない. 特に, 分母が 0 になる場合に致命的なエラーとなるため, 
実際に分母を持つ代数的数を生成する場合には細心の注意が必要となる.
\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 代数的数の, 定義多項式による簡単化は, @code{simpalg()} で行う. 
\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()} は有理式の形をした代数的数を, 多項式の形に簡単化する. 
\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
この例では, 分母が 0 の代数的数を簡単化しようとして 0 による除算が生じ
たため, ユーザ定義函数である @code{simpalg()} の中でデバッガが呼ばれた
ことを示す. @code{simpalg()} は, 代数的数を係数とする多項式の
各係数を簡単化できる. 
\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
代数的数を係数とする多項式の基本演算は, 適宜 @code{simpalg()} を呼ぶことを
除けば通常の場合と同様であるが, 因数分解などで頻繁に用いられるノルムの
計算などにおいては, @code{root} を不定元に置き換える必要が出てくる. 
この場合, @code{algptorat()} を用いる. 
\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
このように, @code{algptorat()} は, 多項式, 数に含まれる @code{root}
を, 対応する不定元, すなわち @code{#@var{n}} に対する @code{t#@var{n}}
に置き換える. 既に述べたように, この不定元はユーザが入力することはできない. 
これは, ユーザの入力した不定元と, @code{root} に対応する不定元が一致
しないようにするためである. 
\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
逆に, @code{root} に対応する不定元を, 対応する @code{root} に置き換える
ためには @code{rattoalgp()} を用いる. 
\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()} は, 置換の対象となる @code{root} のリストを第 2 引数
にとり, 左から順に, 対応する不定元を置き換えて行く. この例は, 
置換する順序を換えると簡単化を行わないことにより結果が一見異なるが, 
簡単化により実は一致することを示している. @code{algptorat()}, 
@code{rattoalgp()} は, ユーザが独自の簡単化を行いたい場合などにも
用いることができる. 
\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 代数体上での 1 変数多項式の演算,,, 代数的数に関する演算
@section 代数体上での 1 変数多項式の演算
\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} では, 1 変数多項式に限り, GCD, 因数分解およびそれらの応用として
最小分解体を求める函数を提供している. 
\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
* 無平方分解 因数分解::
* 最小分解体::
\E
\BEG
* Square-free factorization and Factorization::
* Splitting fields::
\E
@end menu

\JP @node GCD,,, 代数体上での 1 変数多項式の演算
\EG @node GCD,,, Operations for uni-variate polynomials over an algebraic number field
@subsection GCD

@noindent
\BJP
代数体上での GCD は @code{cr_gcda()} により計算される. 
この函数はモジュラ演算および中国剰余定理により代数体上の GCD を
計算するもので, 逐次拡大に対しても有効である. 
\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);
27*x+((#0^6-19*#0^3-65)*#1-#0^7+19*#0^4+38*#0)
@end example

\BJP
@node 無平方分解 因数分解,,, 代数体上での 1 変数多項式の演算
@subsection 無平方分解, 因数分解
\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
無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的な
アルゴリズムを採用している. 函数は @code{asq()} である. 
\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
結果は通常と同様に, [@b{因子}, @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
代数体上での因数分解は, Trager によるノルム法を改良したもので, 特に
ある多項式に対し, その根を添加した体上でその多項式自身を因数分解する
場合に特に有効である. 
\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
引数は 2 つで, 第 2 引数は, @code{root} のリストである. 因数分解は
有理数体に, それらの @code{root} を添加した体上で行われる. 
@code{root} の順序には制限がある. すなわち, 後で定義されたものほど
前の方にこなければ
ならない. 並べ換えは, 自動的には行われない. ユーザの責任となる. 
\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
ノルムを用いた因数分解においては, ノルムの計算と整数係数 1 変数多項式の
因数分解の効率が, 全体の効率を左右する. このうち, 特に高次の多項式
の場合に後者において組合せ爆発により計算不能になる場合がしばしば生ずる. 
\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 最小分解体,,, 代数体上での 1 変数多項式の演算
@subsection 最小分解体
\E
\BEG
@node Splitting fields,,, Operations for uni-variate polynomials over an algebraic number field
@subsection Splitting fields
\E

@noindent
\BJP
やや特殊な演算ではあるが, 前節の因数分解を反復適用することにより, 
多項式の最小分解体を求めることができる. 函数は @code{sp()} である. 
\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()} は 1 引数で, 結果は @code{[1 次因子のリスト, [[root,
algptorat(定義多項式)] のリスト]} なるリストである. 
第 2 要素の @code{[root,algptorat(定義多項式)]} のリストは, 
右から順に, 最小分解体が得られるまで添加していった @code{root} を示す. 
その定義多項式は, その直前までの @code{root} を添加した体上で既約であること
が保証されている. 
\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
結果の第 1 要素である 1 次因子のリストは, 第 2 要素の @code{root} を全て
添加した体上での, @code{sp()} の引数の多項式の全ての因子を表す. その体は
最小分解体となっているので, 因子は全て 1 次となるわけである. @code{af()}
と同様, 全ての因子の積は, もとの多項式と定数倍の差はあり得る. 
\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 代数的数に関する函数のまとめ,,, 代数的数に関する演算
@section 代数的数に関する函数のまとめ
\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 af_noalg::
* sp sp_noalg::
@end menu

\JP @node newalg,,, 代数的数に関する函数のまとめ
\EG @node newalg,,, Summary of functions for algebraic numbers
@subsection @code{newalg}
@findex newalg

@table @t
@item newalg(@var{defpoly})
\JP :: @code{root} を生成する. 
\EG :: Creates a new @b{root}.
@end table

@table @var
@item return
\JP 代数的数 (@code{root})
\EG algebraic number (@b{root})
@item defpoly
\JP 多項式
\EG polynomial
@end table

@itemize @bullet
@item
\JP @var{defpoly} を定義多項式とする代数的数 (@code{root}) を生成する. 
\BEG
Creates a new @b{root} (algebraic number) with its defining
polynomial @var{defpoly}.
\E
@item
\JP @var{defpoly} に対する制限に関しては, @xref{代数的数の表現}.
\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 参照
\EG @item Reference
@fref{defpoly}
@end table

\JP @node defpoly,,, 代数的数に関する函数のまとめ
\EG @node defpoly,,, Summary of functions for algebraic numbers
@subsection @code{defpoly}
@findex defpoly

@table @t
@item defpoly(@var{alg})
\JP :: @code{root} の定義多項式を返す. 
\EG :: Returns the defining polynomial of @b{root} @var{alg}.
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item alg
\JP 代数的数 (@code{root})
\EG algebraic number (@code{root})
@end table

@itemize @bullet
@item
\JP @code{root} @var{alg} の定義多項式を返す. 
\EG Returns the defining polynomial of @b{root} @var{alg}.
@item
\BJP
@code{root} を @code{#@var{n}} とすれば, 定義多項式の主変数は
@code{t#@var{n}} となる. 
\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 参照
\EG @item Reference
@fref{newalg}, @fref{alg}, @fref{algv}
@end table

\JP @node alg,,, 代数的数に関する函数のまとめ
\EG @node alg,,, Summary of functions for algebraic numbers
@subsection @code{alg}
@findex alg

@table @t
@item alg(@var{i})
\JP :: インデックスに対応する @code{root} を返す. 
\EG :: Returns a @b{root} which correspond to the index @var{i}.
@end table

@table @var
@item return
\JP 代数的数 (@code{root})
\EG algebraic number (@code{root})
@item i
\JP 整数
\EG integer
@end table

@itemize @bullet
@item
\JP @code{root} @code{#@var{i}} を返す. 
\EG Returns @code{#@var{i}}, a @b{root}.
@item
\BJP
@code{#@var{i}} はユーザが直接入力できないため, @code{alg(@var{i})} と
いう形で入力する. 
\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 参照
\EG @item Reference
@fref{newalg}, @fref{algv}
@end table

\JP @node algv,,, 代数的数に関する函数のまとめ
\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})} に対応する不定元を返す. 
\EG :: Returns the associated indeterminate with @code{alg(@var{i})}.
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item i
\JP 整数
\EG integer
@end table

@itemize @bullet
@item
\JP 多項式 @code{t#@var{i}} を返す. 
\EG Returns an indeterminate @code{t#@var{i}}
@item
\BJP
@code{t#@var{i}} はユーザが直接入力できないため, @code{algv(@var{i})} と
いう形で入力する. 
\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 参照
\EG @item Reference
@fref{newalg}, @fref{defpoly}, @fref{alg}
@end table

\JP @node simpalg,,, 代数的数に関する函数のまとめ
\EG @node simpalg,,, Summary of functions for algebraic numbers
@subsection @code{simpalg}
@findex simpalg

@table @t
@item simpalg(@var{rat})
\JP :: 有理式に含まれる代数的数を簡単化する. 
\EG :: Simplifies algebraic numbers in a rational expression.
@end table

@table @var
@item return
\JP 有理式
\EG rational expression
@item rat
\JP 有理式
\EG rational expression
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている. 
\EG Defined in the file @samp{sp}.
@item
\BJP
数, 多項式, 有理式に含まれる代数的数を, 含まれる @code{root} の定義
多項式により簡単化する. 
\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 数の場合, 分母があれば有理化され, 結果は @code{root} の多項式となる. 
\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 多項式の場合, 各係数が簡単化される. 
\EG If the argument is a polynomial, each coefficient is simplified.
@item
\JP 有理式の場合, 分母分子が多項式として簡単化される. 
\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,,, 代数的数に関する函数のまとめ
\EG @node algptorat,,, Summary of functions for algebraic numbers
@subsection @code{algptorat}
@findex algptorat

@table @t
@item algptorat(@var{poly})
\JP :: 多項式に含まれる @code{root} を, 対応する不定元に置き換える. 
\EG :: Substitutes the associated indeterminate for every @b{root}
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item poly
\JP 多項式
\EG polynomial
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている. 
\EG Defined in the file @samp{sp}.
@item
\BJP
多項式に含まれる @code{root} @code{#@var{n}} を全て @code{t#@var{n}} に
置き換える. 
\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 参照
\EG @item Reference
@fref{defpoly}, @fref{algv}
@end table

\JP @node rattoalgp,,, 代数的数に関する函数のまとめ
\EG @node rattoalgp,,, Summary of functions for algebraic numbers
@subsection @code{rattoalgp}
@findex rattoalgp

@table @t
@item rattoalgp(@var{poly},@var{alglist})
\BJP
:: 多項式に含まれる @code{root} に対応する不定元を @code{root} に
置き換える. 
\E
\BEG
:: Substitutes a @b{root} for the associated indeterminate with the
 @b{root}.
\E
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item poly
\JP 多項式
\EG polynomial
@item alglist
\JP リスト
\EG list
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている. 
\EG Defined in the file @samp{sp}.
@item
\BJP
第 2 引数は @code{root} のリストである. @code{rattoalgp()} は, この @code{root}
に対応する不定元を, それぞれ @code{root} に置き換える. 
\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 参照
\EG @item Reference
@fref{alg}, @fref{algv}
@end table

\JP @node cr_gcda,,, 代数的数に関する函数のまとめ
\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})
\JP :: 代数体上の 1 変数多項式の GCD
\EG :: GCD of two uni-variate polynomials over an algebraic number field.
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item poly1, poly2
\JP 多項式
\EG polynomial
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている. 
\EG Defined in the file @samp{sp}.
@item
\JP 2 つの 1 変数多項式の GCD を求める. 
\EG Finds the GCD of two uni-variate polynomials.
@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));
x+(-#0)
@end example

@table @t
\JP @item 参照
\EG @item Reference
@fref{gr hgr gr_mod}, @fref{asq af af_noalg}
@end table

\JP @node sp_norm,,, 代数的数に関する函数のまとめ
\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 :: 代数体上でのノルムの計算
\EG :: Norm computation over an algebraic number field.
@end table

@table @var
@item return
\JP 多項式
\EG polynomial
@item var
\JP @var{poly} の主変数
\EG The main variable of @var{poly}
@item poly
\JP 1 変数多項式
\EG univariate polynomial
@item alg
@code{root}
@item alglist
\JP @code{root} のリスト
\EG @code{root} list
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている. 
\EG Defined in the file @samp{sp}.
@item
\BJP
@var{poly} の, @var{alg} に関するノルムをとる. すなわち, 
@b{K} = @b{Q}(@var{alglist} \ @{@var{alg}@}) とするとき, 
@var{poly} に現れる @var{alg} を, @var{alg} の @b{K} 上の共役に置き換えたもの
全ての積を返す. 
\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 結果は @b{K} 上の多項式となる. 
\EG The result is a polynomial over @b{K}.
@item
\BJP
実際には入力により場合わけが行われ, 終結式の直接計算や中国剰余定理に
より計算されるが, 最適な選択が行われているとは限らない. 
大域変数 @code{USE_RES} を 1 に設定することにより, 常に終結式により計算
させることができる. 
\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 参照
\EG @item Reference
@fref{res}, @fref{asq af af_noalg}
@end table

\JP @node asq af af_noalg,,, 代数的数に関する函数のまとめ
\EG @node asq af af_noalg,,, Summary of functions for algebraic numbers
@subsection @code{asq}, @code{af}, @code{af_noalg}
@findex asq
@findex af
@findex af_noalg

@table @t
@item asq(@var{poly})
\JP :: 代数体上の 1 変数多項式の無平方分解
\BEG
:: Square-free factorization of polynomial @var{poly} over an
algebraic number field.
\E
@item af(@var{poly},@var{alglist})
@itemx af_noalg(@var{poly},@var{defpolylist})
\JP :: 代数体上の 1 変数多項式の因数分解
\BEG
:: Factorization of polynomial @var{poly} over an
algebraic number field.
\E
@end table

@table @var
@item return
\JP リスト
\EG list
@item poly
\JP 多項式
\EG polynomial
@item alglist
\JP @code{root} のリスト
\EG @code{root} list
@item defpolylist
\JP @code{root} を表す不定元と定義多項式のペアのリスト
\EG @code{root} list of pairs of an indeterminate and a polynomial
@end table

@itemize @bullet
@item
\JP いずれも @samp{sp} で定義されている.
\EG Both defined in the file @samp{sp}.
@item
\BJP
@code{root} を含まない場合は整数上の函数が呼び出され高速であるが, 
@code{root} を含む場合には, @code{cr_gcda()} が起動されるためしばしば
時間がかかる. 
\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()} は, 基礎体の指定, すなわち第 2 引数の, @code{root} のリスト
の指定が必要である. 
\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} で指定される @code{root} は, 後で定義されたものほど前の
方に来なければならない. 
\E
\BEG
In the second argument @code{alglist}, @b{root} defined last must come
first.
\E
@item
\BJP
@code{sp_noalg} では, @var{poly} に含まれる代数的数 @var{ai} を不定元 @var{vi}
で置き換える. @code{defpolylist} は, @var{[[vn,dn(vn,...,v1)],...,[v1,d(v1)]]}
なるリストである. ここで @var{di(vi,...,v1)} は @var{ai} の定義多項式において
代数的数を全て @var{vj} に置き換えたものである. 
\E
\BEG
To call @code{sp_noalg}, one should replace each algebraic number 
@var{ai} in @var{poly} with an indeterminate @var{vi}. @code{defpolylist}
is a list @var{[[vn,dn(vn,...,v1)],...,[v1,d(v1)]]}. In this expression
@var{di(vi,...,v1)} is a defining polynomial of @var{ai} represented
as a multivariate polynomial.
\E
@item
\BJP
結果は, 通常の無平方分解, 因数分解と同様 [@b{因子}, @b{重複度}] 
のリストである. @code{af_noalg} の場合, @b{因子} に現れる代数的数は, 
@var{defpolylist} に従って不定元に置き換えられる. 
\E
\BEG
The result is a list, as a result of usual factorization, whose elements
is of the form [@b{factor}, @b{multiplicity}]. 
In the result of @code{af_noalg}, algebraic numbers in @v{factor} are 
replaced by the indeterminates according to @var{defpolylist}.
\E
@item
\JP 重複度を込めた因子の全ての積は, @var{poly} と定数倍の違いがあり得る. 
\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 参照
\EG @item Reference
@fref{cr_gcda}, @fref{fctr sqfr}
@end table

\JP @node sp sp_noalg,,, 代数的数に関する函数のまとめ
\EG @node sp sp_noalg,,, Summary of functions for algebraic numbers
@subsection @code{sp}, @code{sp_noalg}
@findex sp

@table @t
@item sp(@var{poly})
@itemx sp_noalg(@var{poly})
\JP :: 最小分解体を求める. 
\EG :: Finds the splitting field of polynomial @var{poly} and splits.
@end table

@table @var
@item return
\JP リスト
\EG list
@item poly
\JP 多項式
\EG polynomial
@end table

@itemize @bullet
@item
\JP @samp{sp} で定義されている.
\EG Defined in the file @samp{sp}.
@item
\BJP
有理数係数の 1 変数多項式 @var{poly} の最小分解体, およびその体上での
@var{poly} の 1 次因子への分解を求める. 
\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
結果は, @var{poly} の因子のリストと, 最小分解体の, 逐次拡大による表現
からなるリストである. @code{sp_noalg} では, 全ての代数的数が, 対応する
不定元 (即ち @code{#i} に対する @code{t#i}) に置き換えられる. これに
より, @code{sp_noalg} の出力は, 整数係数多変数多項式のリストとなる. 
\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.
In the result of @code{sp_noalg} all the algebraic numbers are replaced
by the special indeterminate associated with it, that is @code{t#i}
for @code{#i}. By this operation the result of @code{sp_noalg}
is a list containing only integral polynomials.
\E
@item
\BJP
最小分解体は, @code{[root,algptorat(defpoly(root))]} のリストとして
表現されている. すなわち, 求める最小分解体は, 有理数体に, この @code{root}
を全て添加した体として得られる. 添加は, 右の方の @code{root} から順に
行われる. 
\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()} は, 内部でノルムの計算のために @code{sp_norm()} をしばしば
起動する. ノルムの計算は, 状況に応じてさまざまな方法で行われるが, 
そこで用いられる方法が最善とは限らず, 単純な終結式の計算の方が高速
である場合もある. 
大域変数 @code{USE_RES} を 1 に設定することにより, 常に終結式により計算
させることができる. 
\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 参照
\EG @item Reference
@fref{asq af af_noalg}, @fref{defpoly}, @fref{algptorat}, @fref{sp_norm}.
@end table