代数的数に関する演算
**********

Algebraic numbers
*****************

代数的数の表現
=======

Representation of algebraic numbers
===================================

Asir においては, 代数体という対象は定義されない. 独立した対象として定義されるのは, 代数的数である. 代数体は, 有理数体に, 代数的数を有限個順次添加した体として仮想的に定義される. 新たな代数的数は, 有理数およびこれまで定義された代数的数の多項式を係数とする 1 変数多項式を定義多項式として定義される. 以下, ある定義多項式の根として定義された代数的数を, root と呼ぶことにする.

In Asir algebraic number fields are not defined as independent objects. Instead, individual algebraic numbers are defined by some means. In 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 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 root. Also, we call such an uni-variate polynomial the defining polynomial of that root.

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

この例では, A0 は x^2+1=0 の根, A1 は, その A0 を係数に含む x^3+A0*x+A0=0 の根として定義されている.

In this example, the algebraic number assigned to A0 is defined as a root of a polynomial x^2+1; that of A1 is defined as a root of a polynomial x^3+A0*x+A0, which you see contains the previously defined root (A0) in its coefficients.

newalg() の引数すなわち定義多項式には次のような制限がある.

The argument to newalg(), i.e., the defining polynomial, must satisfy the following conditions.

 1. 定義多項式は 1 変数多項式でなければならない.

     A defining polynomial must be an uni-variate polynomial.

 2. newalg() の引数である定義多項式は, 代数的数を含む式の簡単化のために用いられる. この簡単化は, 組み込み函数 srem() に相当する内部ルーチンを用いて行われる. このため, 定義多項式の主係数は, 有理数になっている必要がある.

     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 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.)

 3. 定義多項式の係数は すでに定義されている root の有理数係数多項式でなければならない.

     Every coefficients of a defining polynomial must be a `(multi-variate) polynomial' in already defined root's. Here, `(multi-variate) polynomial' means a mathematical concept, not the object type `polynomial' in Asir.

 4. 定義多項式は, その係数に含まれる全ての root を有理数に添加した体上で既約でなければならない.

     A defining polynomial must be irreducible over the field that is obtained by adjoining all root's contained in its coefficients to the rational number field.

newalg() が行う引数チェックは, 1 および 2 のみである. 特に, 引数の定義多項式の既約性は全くチェックされない. これは既約性のチェックが多大な計算量を必要とするためで, この点に関しては, ユーザの責任に任されている.

Only the first two conditions (1 and 2) are checked by function 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.

一旦 newalg() によって定義された代数的数は, 数としての識別子を持ち, また, 数の中では代数的数としての識別子を持つ. (type(), vtype() 参照.) さらに, 有理数と, root の有理式も同様に代数的数となる.

Once a root has been defined by newalg() function, it is given the type identifier for a number, and furthermore, the sub-type identifier for an algebraic number. (see type, ntype.) Also, any rational combination of rational numbers and root's is an algebraic number.

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

例からわかるように, rootは #N と表示される. しかし, ユーザはこの形では入力できない. root は変数に格納して用いるか, あるいは alg(N) により取り出す. また, 効率は落ちるが, 全く同じ引数 (変数は異なっていてもよい) により newalg() を呼べば, 新しい代数的数は定義されずに既に定義されたものが得られる.

As you see it in the example, a root is displayed as #N.  But, you cannot input that root in its immediate output form. You have to refer to a root by a program variable assigned to the root, or to get it by alg(N) function, or by several other indirect means. A strange use of newalg(), with a same argument polynomial (except for the name of its main variable), will yield the old root instead of a new root though it is apparently inefficient.

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

root の定義多項式は, defpoly() により取り出せる.

The defining polynomial of a root can be obtained by defpoly() function.

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

ここで現れた, t#0, t#1 はそれぞれ #0, #1 に対応する不定元である. これらもユーザが入力することはできない. var() で取り出すか, あるいは algv(N) により取り出す.

Here, you see a strange expression, t#0 and t#1. They are a specially indeterminates generated and maintained by Asir internally.  Indeterminate t#0 corresponds to root #0, and t#0 to #1.  These indeterminates also cannot be input directly by a user in their immediate forms. You can get them by several ways: by var() function, or algv(N) function.

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

代数的数の演算
=======

Operations over algebraic numbers
=================================

前節で, 代数的数の表現, 定義について述べた. ここでは, 代数的数を用いた演算について述べる. 代数的数に関しては, 組み込み函数として提供されている機能はごく少数で, 大部分はユーザ定義函数により実現されている. ファイルは, sp で, gr と同様 Asir の標準ライブラリディレクトリにおかれている.

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 sp, and it is placed under the same directory as gr is placed, i.e., the standard library directory of Asir.

     [0] load("gr")$
     [1] load("sp")$

あるいは, 常に用いるならば, $HOME/.asirrc に書いておくのもよい.

Or if you always need them, it is more convenient to include the load commands in $HOME/.asirrc.

root は その他の数と同様, 四則演算が可能となる. しかし, 定義多項式による簡単化は自動的には行われないので, ユーザの判断で適宜行わなければならない. 特に, 分母が 0 になる場合に致命的なエラーとなるため, 実際に分母を持つ代数的数を生成する場合には細心の注意が必要となる.

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.

代数的数の, 定義多項式による簡単化は, simpalg() で行う.

Use simpalg() function for simplification of algebraic numbers by defining polynomials.

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

simpalg() は有理式の形をした代数的数を, 多項式の形に簡単化する.

Function simpalg() simplifies algebraic numbers which have the same structures as rational expressions in their appearances.

     [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)

この例では, 分母が 0 の代数的数を簡単化しようとして 0 による除算が生じたため, ユーザ定義函数である simpalg() の中でデバッガが呼ばれたことを示す. simpalg() は, 代数的数を係数とする多項式の各係数を簡単化できる.

This example shows an error caused by zero division in the course of program execution of simpalg(), which attempted to simplify an algebraic number expression of which the denominator is 0.

Function simpalg() also can take a polynomial as its argument and simplifies algebraic numbers in its coefficients.

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

代数的数を係数とする多項式の基本演算は, 適宜 simpalg() を呼ぶことを除けば通常の場合と同様であるが, 因数分解などで頻繁に用いられるノルムの計算などにおいては, root を不定元に置き換える必要が出てくる. この場合, algptorat() を用いる.

Thus, you can operate in polynomials which contain algebraic numbers as you do usually in ordinary polynomials, except for proper simplification by simpalg(). You may sometimes feel needs to convert root's into indeterminates, especially when you are working for norm computation in algorithms for algebraic factorization. Function algptorat() is used for such cases.

     [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

このように, algptorat() は, 多項式, 数に含まれる root を, 対応する不定元, すなわち #N に対する t#N に置き換える. 既に述べたように, この不定元はユーザが入力することはできない. これは, ユーザの入力した不定元と, root に対応する不定元が一致しないようにするためである.

As you see by the example, function algptorat() converts root's, #N, in polynomials and numbers into its associated indeterminates, t#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.

逆に, root に対応する不定元を, 対応する root に置き換えるためには rattoalgp() を用いる.

The associated indeterminate to a root is reversely converted into the root by rattoalgp() function.

     [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)

rattoalgp() は, 置換の対象となる root のリストを第 2 引数にとり, 左から順に, 対応する不定元を置き換えて行く. この例は, 置換する順序を換えると簡単化を行わないことにより結果が一見異なるが, 簡単化により実は一致することを示している. algptorat(), rattoalgp() は, ユーザが独自の簡単化を行いたい場合などにも用いることができる.

Function rattoalgp() takes as the second argument a list consisting of 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 algptorat() and rattoalgp() can be conveniently used for your own simplification.

代数体上での 1 変数多項式の演算
=================

Operations for uni-variate polynomials over an algebraic number field
=====================================================================

sp では, 1 変数多項式に限り, GCD, 因数分解およびそれらの応用として最小分解体を求める函数を提供している.

In the file 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.

GCD
---

代数体上での GCD は cr_gcda() により計算される. この函数はモジュラ演算および中国剰余定理により代数体上の GCD を計算するもので, 逐次拡大に対しても有効である.

Greatest common divisors (GCD) over algebraic number fields are computed by 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.

     [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)

無平方分解, 因数分解
-----------

Square-free factorization and Factorization
-------------------------------------------

無平方分解は, 多項式とその微分との GCD の計算から始まるもっとも一般的なアルゴリズムを採用している. 函数は asq() である.

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 asq().

     [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]]

結果は通常と同様に, [因子, 重複度] のリストとなるが, 全ての因子の積は, もとの多項式と定数倍の差はあり得る. これは, 因子を整数係数にして見やすくするためで, 因数分解でも同様である.

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 [factor, 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.

代数体上での因数分解は, Trager によるノルム法を改良したもので, 特にある多項式に対し, その根を添加した体上でその多項式自身を因数分解する場合に特に有効である.

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 root's to the base field.

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

引数は 2 つで, 第 2 引数は, root のリストである. 因数分解は有理数体に, それらの root を添加した体上で行われる. root の順序には制限がある. すなわち, 後で定義されたものほど前の方にこなければならない. 並べ換えは, 自動的には行われない. ユーザの責任となる.

The function takes two arguments: The second argument is a list of root's.  Factorization is performed over a field obtained by adjoining the root's to the rational number field. It is important to keep in mind that the ordering of the root's must obey a restriction: Last defined should come first. The automatic re-ordering is not done. It should be done by yourself.

ノルムを用いた因数分解においては, ノルムの計算と整数係数 1 変数多項式の因数分解の効率が, 全体の効率を左右する. このうち, 特に高次の多項式の場合に後者において組合せ爆発により計算不能になる場合がしばしば生ずる.

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.

     [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]]

最小分解体
-----

Splitting fields
----------------

やや特殊な演算ではあるが, 前節の因数分解を反復適用することにより, 多項式の最小分解体を求めることができる. 函数は sp() である.

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 sp().

     [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]]]

sp() は 1 引数で, 結果は [1 次因子のリスト, [[root, algptorat(定義多項式)] のリスト] なるリストである. 第 2 要素の [root,algptorat(定義多項式)] のリストは, 右から順に, 最小分解体が得られるまで添加していった root を示す. その定義多項式は, その直前までの root を添加した体上で既約であることが保証されている.

Function 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 [root, algptorat(defining polynomial)]. The second element, a list of pairs of form [root,algptorat(defining polynomial)], corresponds to the 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 root's defined before it.

結果の第 1 要素である 1 次因子のリストは, 第 2 要素の root を全て添加した体上での, sp() の引数の多項式の全ての因子を表す. その体は最小分解体となっているので, 因子は全て 1 次となるわけである. af() と同様, 全ての因子の積は, もとの多項式と定数倍の差はあり得る.

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 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 af(), the product of all resulting factors may yield a polynomial which differs by a constant.

代数的数に関する函数のまとめ
==============

Summary of functions for algebraic numbers
==========================================

newalg
------

newalg(DEFPOLY)
     :: root を生成する.

     :: Creates a new root.

return
     代数的数 (root)

     algebraic number (root)

defpoly
     多項式

     polynomial

  * DEFPOLY を定義多項式とする代数的数 (root) を生成する.

     Creates a new root (algebraic number) with its defining polynomial DEFPOLY.

  * DEFPOLY に対する制限に関しては, see 代数的数の表現.

     For constraints on DEFPOLY, see Representation of algebraic numbers.

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

参照

Reference
     defpoly

defpoly
-------

defpoly(ALG)
     :: root の定義多項式を返す.

     :: Returns the defining polynomial of root ALG.

return
     多項式

     polynomial

alg
     代数的数 (root)

     algebraic number (root)

  * root ALG の定義多項式を返す.

     Returns the defining polynomial of root ALG.

  * root を #N とすれば, 定義多項式の主変数は t#N となる.

     If the argument ALG, a root, is #N, then the main variable of its defining polynomial is t#N.

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

参照

Reference
     newalg, alg, algv

alg
---

alg(I)
     :: インデックスに対応する root を返す.

     :: Returns a root which correspond to the index I.

return
     代数的数 (root)

     algebraic number (root)

i
     整数

     integer

  * root #I を返す.

     Returns #I, a root.

  * #I はユーザが直接入力できないため, alg(I) という形で入力する.

     Because #I cannot be input directly, this function provides an alternative way: input alg(I).

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

参照

Reference
     newalg, algv

algv
----

algv(I)
     :: alg(I) に対応する不定元を返す.

     :: Returns the associated indeterminate with alg(I).

return
     多項式

     polynomial

i
     整数

     integer

  * 多項式 t#I を返す.

     Returns an indeterminate t#I

  * t#I はユーザが直接入力できないため, algv(I) という形で入力する.

     Since indeterminate t#I cannot be input directly, it is input by algv(I).

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

参照

Reference
     newalg, defpoly, alg

simpalg
-------

simpalg(RAT)
     :: 有理式に含まれる代数的数を簡単化する.

     :: Simplifies algebraic numbers in a rational expression.

return
     有理式

     rational expression

rat
     有理式

     rational expression

  * sp で定義されている.

     Defined in the file sp.

  * 数, 多項式, 有理式に含まれる代数的数を, 含まれる root の定義多項式により簡単化する.

     Simplifies algebraic numbers contained in numbers, polynomials, and rational expressions by the defining polynomials of root's contained in them.

  * 数の場合, 分母があれば有理化され, 結果は root の多項式となる.

     If the argument is a number having the denominator, it is rationalized and the result is a polynomial in root's.

  * 多項式の場合, 各係数が簡単化される.

     If the argument is a polynomial, each coefficient is simplified.

  * 有理式の場合, 分母分子が多項式として簡単化される.

     If the argument is a rational expression, its denominator and numerator are simplified as a polynomial.

     [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))

algptorat
---------

algptorat(POLY)
     :: 多項式に含まれる root を, 対応する不定元に置き換える.

     :: Substitutes the associated indeterminate for every root

return
     多項式

     polynomial

poly
     多項式

     polynomial

  * sp で定義されている.

     Defined in the file sp.

  * 多項式に含まれる root #N を全て t#N に置き換える.

     Substitutes the associated indeterminate t#N for every root #N in a polynomial.

     [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

参照

Reference
     defpoly, algv

rattoalgp
---------

rattoalgp(POLY,ALGLIST)

     :: 多項式に含まれる root に対応する不定元を root に置き換える.

     :: Substitutes a root for the associated indeterminate with the root.

return
     多項式

     polynomial

poly
     多項式

     polynomial

alglist
     リスト

     list

  * sp で定義されている.

     Defined in the file sp.

  * 第 2 引数は root のリストである. rattoalgp() は, この root に対応する不定元を, それぞれ root に置き換える.

     The second argument is a list of root's. Function rattoalgp() substitutes a root for the associated indeterminate of the root.

     [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)

参照

Reference
     alg, algv

cr_gcda
-------

cr_gcda(POLY1,POLY2,ALIST)
     :: 代数体上の 1 変数多項式の GCD

     :: GCD of two uni-variate polynomials over an algebraic number field.

return
     多項式

     polynomial

poly1, poly2
     多項式

     polynomial

alist
     リスト

     list

  * sp で定義されている.

     Defined in the file sp.

  * 2 つの 1 変数多項式の GCD を求める.

     Finds the GCD of two uni-variate polynomials.

  * ALIST は入力に現れる root および, それらの定義に含まれる root を再帰的に取り出して並べたリスト. A が B の定義に含まれている場合, A は B より後 (右) に並ばなければならない.

     ALIST is a list of root's. All the root's appearing in the input and those required to define the root's in the list  must appear in the list. In the list ,if the defining polynomial of A contains B then A must come first.

     [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)

参照

Reference
     gr hgr gr_mod, asq af

sp_norm
-------

sp_norm(ALG,VAR,POLY,ALGLIST)
     :: 代数体上でのノルムの計算

     :: Norm computation over an algebraic number field.

return
     多項式

     polynomial

var
     POLY の主変数

     The main variable of POLY

poly
     1 変数多項式

     univariate polynomial

alg
     root

alglist
     root のリスト

     root list

  * sp で定義されている.

     Defined in the file sp.

  * POLY の, ALG に関するノルムをとる. すなわち, K = Q(ALGLIST \ {ALG}) とするとき, POLY に現れる ALG を, ALG の K 上の共役に置き換えたもの全ての積を返す.

     Computes the norm of POLY with respect to ALG. Namely, if we write K = Q(ALGLIST \ {ALG}), The function returns a product of all conjugates of POLY, where the conjugate of polynomial POLY is a polynomial in which the algebraic number ALG is substituted for its conjugate over K.

  * 結果は K 上の多項式となる.

     The result is a polynomial over K.

  * 実際には入力により場合わけが行われ, 終結式の直接計算や中国剰余定理により計算されるが, 最適な選択が行われているとは限らない. 大域変数 USE_RES を 1 に設定することにより, 常に終結式により計算させることができる.

     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 USE_RES to 1, the builtin function res() is always used.

     [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

参照

Reference
     res, asq af

asq, af
-------

asq(POLY)
     :: 代数体上の 1 変数多項式の無平方分解

     :: Square-free factorization of polynomial POLY over an algebraic number field.

af(POLY,ALGLIST)
     :: 代数体上の 1 変数多項式の因数分解

     :: Factorization of polynomial POLY over an algebraic number field.

return
     リスト

     list

poly
     多項式

     polynomial

alglist
     root のリスト

     root list

  * いずれも sp で定義されている.

     Both defined in the file sp.

  * root を含まない場合は整数上の函数が呼び出され高速であるが, root を含む場合には, cr_gcda() が起動されるためしばしば時間がかかる.

     If the inputs contain no root's, these functions run fast since they invoke functions over the integers. In contrast to this, if the inputs contain root's, they sometimes take a long time, since cr_gcda() is invoked.

  * af() は, 基礎体の指定, すなわち第 2 引数の, root のリストの指定が必要である.

     Function af() requires the specification of base field, i.e., list of root's for its second argument.

  * alglist で指定される root は, 後で定義されたものほど前の方に来なければならない.

     In the second argument alglist, root defined last must come first.

  * 結果は, 通常の無平方分解, 因数分解と同様 [因子, 重複度] のリストである.

     The result is a list, as a result of usual factorization, whose elements is of the form [factor, multiplicity].

  * 重複度を込めた因子の全ての積は, POLY と定数倍の違いがあり得る.

     The product of all factors with multiplicities counted may differ from the input polynomial by a constant.

     [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]]

参照

Reference
     cr_gcda, fctr sqfr

sp
--

sp(POLY)
     :: 最小分解体を求める.

     :: Finds the splitting field of polynomial POLY and splits.

return
     リスト

     list

poly
     多項式

     polynomial

  * sp で定義されている.

     Defined in the file sp.

  * 有理数係数の 1 変数多項式 POLY の最小分解体, およびその体上での POLY の 1 次因子への分解を求める.

     Finds the splitting field of POLY, an uni-variate polynomial over with rational coefficients, and splits it into its linear factors over the field.

  * 結果は, POLY の因子のリストと, 最小分解体の, 逐次拡大による表現からなるリストである.

     The result consists of a two element list: The first element is the list of all linear factors of POLY; the second element is a list which represents the successive extension of the field.

  * 最小分解体は, [root,algptorat(defpoly(root))] のリストとして表現されている. すなわち, 求める最小分解体は, 有理数体に, この root を全て添加した体として得られる. 添加は, 右の方の root から順に行われる.

     The splitting field is represented as a list of pairs of form [root,algptorat(defpoly(root))]. In more detail, the list is interpreted as a representation of successive extension obtained by adjoining root's to the rational number field.  Adjoining is performed from the right root to the left.

  * sp() は, 内部でノルムの計算のために sp_norm() をしばしば起動する. ノルムの計算は, 状況に応じてさまざまな方法で行われるが, そこで用いられる方法が最善とは限らず, 単純な終結式の計算の方が高速である場合もある. 大域変数 USE_RES を 1 に設定することにより, 常に終結式により計算させることができる.

     sp() invokes 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 USE_RES to 1, the builtin function res() is always used.

     [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

参照

Reference
     asq af, defpoly, algptorat, sp_norm.