多項式, 有理式の演算
===========

operations with polynomials and rational expressions
====================================================

var
---

var(RAT)
     :: RAT の主変数.

     :: Main variable (indeterminate) of RAT.

return
     不定元

     indeterminate

rat
     有理式

     rational expression

  * 主変数に関しては, see Asir で使用可能な型.

  * デフォルトの変数順序は次のようになっている.

     x, y, z, u, v, w, p, q, r, s, t, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o,以後は変数の現れた順.

  * See Types in Asir for main variable.

  * Indeterminates (variables) are ordered by default as follows.

     x, y, z, u, v, w, p, q, r, s, t, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o. The other variables will be ordered after the above noted variables so that the first comer will be ordered prior to the followers.

     [0] var(x^2+y^2+a^2);
     x
     [1] var(a*b*c*d*e);
     a
     [2] var(3/abc+2*xy/efg);
     abc

参照

References
     ord, vars.

vars
----

vars(OBJ)
     :: OBJ に含まれる変数のリスト.

     :: A list of variables (indeterminates) in an expression OBJ.

return
     リスト

     list

obj
     任意

     arbitrary

  * 与えられた式に含まれる変数のリストを返す.

  * 変数順序の高いものから順に並べる.

  * Returns a list of variables (indeterminates) contained in a given expression.

  * Lists variables according to the variable ordering.

     [0] vars(x^2+y^2+a^2);
     [x,y,a]
     [1] vars(3/abc+2*xy/efg);
     [abc,xy,efg]
     [2] vars([x,y,z]);
     [x,y,z]

参照

References
     var, uc, ord.

uc
--

uc()
     :: 未定係数法のための不定元を生成する.

     :: Create a new indeterminate for an undermined coeficient.

return
     vtype が 1 の不定元

     indeterminate with its vtype 1.

  * uc() を実行するたびに, _0, _1, _2,... という不定元を生成する.

  * uc() で生成された不定元は, 直接キーボードから入力することができない. これは, プログラム中で未定係数を自動生成する場合, 入力などに含まれる不定元と同一のものが生成されることを防ぐためである.

  * 通常の不定元 (vtype が 0) の自動生成には rtostr(), strtov() を用いる.

  * uc() で生成された不定元の不定元としての型 (vtype) は 1 である. (see 不定元の型.)

  * At every evaluation of command uc(), a new indeterminate in the sequence of indeterminates _0, _1, _2, ... is created successively.

  * Indeterminates created by uc() cannot be input on the keyboard. By this property, you are free, no matter how many indeterminates you will create dynamically by a program, from collision of created names with indeterminates input from the keyboard or from program files.

  * Functions, rtostr() and strtov(), are used to create ordinary indeterminates (indeterminates having 0 for their vtype).

  * Kernel sub-type of indeterminates created by uc() is 1. (vtype(uc())=1)

     [0] A=uc();
     _0
     [1] B=uc();
     _1
     [2] (uc()+uc())^2;
     _2^2+2*_3*_2+_3^2
     [3] (A+B)^2;
     _0^2+2*_1*_0+_1^2

参照

References
     vtype, rtostr, strtov.

coef
----

coef(POLY,DEG[,VAR])
     :: POLY の VAR (省略時は主変数) に関する DEG 次の係数.

     :: The coefficient of a polynomial POLY at degree DEG with respect to the variable VAR (main variable if unspecified).

return
     多項式

     polynomial

poly
     多項式

     polynomial

var
     不定元

     indeterminate

deg
     自然数

     non-negative integer

  * POLY の VAR に関する DEG 次の係数を出力する.

  * VAR は, 省略すると主変数 var(POLY) だとみなされる.

  * VAR が主変数でない時, VAR が主変数の場合に比較して効率が落ちる.

  * The coefficient of a polynomial POLY at degree DEG with respect to the variable VAR.

  * The default value for VAR is the main variable, i.e., var(POLY).

  * For multi-variate polynomials, access to coefficients depends on the specified indeterminates.  For example, taking coef for the main variable is much faster than for other variables.

     [0] A = (x+y+z)^3;
     x^3+(3*y+3*z)*x^2+(3*y^2+6*z*y+3*z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
     [1] coef(A,1,y);
     3*x^2+6*z*x+3*z^2
     [2] coef(A,0);
     y^3+3*z*y^2+3*z^2*y+z^3

参照

References
     var, deg mindeg.

deg, mindeg
-----------

deg(POLY,VAR)
     :: POLY の, 変数 VAR に関する最高次数.

     :: The degree of a polynomial POLY with respect to variable.

mindeg(POLY,VAR)
     :: POLY の, 変数 VAR に関する最低次数.

     :: The least exponent of the terms with non-zero coefficients in a polynomial POLY with respect to the variable VAR. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.

return
     自然数

     non-negative integer

poly
     多項式

     polynomial

var
     不定元

     indeterminate

  * 与えられた多項式の変数 VAR に関する最高次数, 最低次数を出力する.

  * 変数 VAR を省略することは出来ない.

  * The least exponent of the terms with non-zero coefficients in a polynomial POLY with respect to the variable VAR. In this manual, this quantity is sometimes referred to the minimum degree of a polynomial for short.

  * Variable VAR must be specified.

     [0] deg((x+y+z)^10,x);
     10
     [1] deg((x+y+z)^10,w);
     0
     [75] mindeg(x^2+3*x*y,x);
     1

nmono
-----

nmono(RAT)
     :: RAT の単項式の項数.

     :: Number of monomials in rational expression RAT.

return
     自然数

     non-negative integer

rat
     有理式

     rational expression

  * 多項式を展開した状態での 0 でない係数を持つ単項式の項数を求める.

  * 有理式の場合は, 分子と分母の項数の和が返される.

  * 函数形式 (不定元の型) は, 引数が何であっても単項とみなされる. (1 個の不定元と同じ. )

  * Number of monomials with non-zero number coefficients in the full expanded form of the given polynomial.

  * For a rational expression, the sum of the numbers of monomials of the numerator and denominator.

  * A function form is regarded as a single indeterminate no matter how complex arguments it has.

     [0] nmono((x+y)^10);
     11
     [1] nmono((x+y)^10/(x+z)^10);
     22
     [2] nmono(sin((x+y)^10));
     1

参照

References
     vtype.

ord
---

ord([VARLIST])
     :: 変数順序の設定

     :: It sets the ordering of indeterminates (variables).

return
     変数のリスト

     list of indeterminates

varlist
     変数のリスト

     list of indeterminates

  * 引数があるとき, 引数の変数リストを先頭に出し, 残りの変数がその後に続くように変数順序を設定する. 引数のあるなしに関わらず, ord() の終了時における変数順序リストを返す.

  * この函数による変数順序の変更を行っても, 既にプログラム変数などに代入されている式の内部形式は新しい順序に従っては変更されない. 従って, この函数による順序の変更は, Asir の起動直後, あるいは, 新たな変数が現れた時点に行われるべきである. 異なる変数順序のもとで生成された式どうしの演算が行われた場合, 予期せぬ結果が生ずることもあり得る.

  * When an argument is given, this function rearranges the ordering of variables (indeterminates) so that the indeterminates in the argument VARLIST precede and the other indeterminates follow in the system's variable ordering. Regardless of the existence of an argument, it always returns the final variable ordering.

  * Note that no change will be made to the variable ordering of internal forms of objects which already exists in the system, no matter what reordering you specify.  Therefore, the reordering should be limited to the time just after starting Asir, or to the time when one has decided himself to start a totally new computation which has no relation with the previous results. Note that unexpected results may be obtained from operations between objects which are created under different variable ordering.

     [0] ord();
     [x,y,z,u,v,w,p,q,r,s,t,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,_z,_u,_v,
     _w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,_o,
     exp(_x),(_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),
     (-_x^2+1)^(-1/2),cosh(_x),sinh(_x),tanh(_x),
     (_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]
     [1] ord([dx,dy,dz,a,b,c]);
     [dx,dy,dz,a,b,c,x,y,z,u,v,w,p,q,r,s,t,d,e,f,g,h,i,j,k,l,m,n,o,_x,_y,
     _z,_u,_v,_w,_p,_q,_r,_s,_t,_a,_b,_c,_d,_e,_f,_g,_h,_i,_j,_k,_l,_m,_n,
     _o,exp(_x),(_x)^(_y),log(_x),(_x)^(_y-1),cos(_x),sin(_x),tan(_x),
     (-_x^2+1)^(-1/2),cosh(_x),sinh(_x),tanh(_x),
     (_x^2+1)^(-1/2),(_x^2-1)^(-1/2)]

sdiv, sdivm, srem, sremm, sqr, sqrm
-----------------------------------

sdiv(POLY1,POLY2[,V])
sdivm(POLY1,POLY2,MOD[,V])
     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に商を求める.

     :: Quotient of POLY1 divided by POLY2 provided that the division can be performed within polynomial arithmetic over the rationals.

srem(POLY1,POLY2[,V])

sremm(POLY1,POLY2,MOD[,V])
     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に剰余を求める.

     :: Remainder of POLY1 divided by POLY2 provided that the division can be performed within polynomial arithmetic over the rationals.

sqr(POLY1,POLY2[,V])

sqrm(POLY1,POLY2,MOD[,V])

     :: POLY1 を POLY2 で割る除算が最後まで実行できる場合に商, 剰余を求める.

     :: Quotient and remainder of POLY1 divided by POLY2 provided that the division can be performed within polynomial arithmetic over the rationals.

return
     sdiv(), sdivm(), srem(), sremm() : 多項式, sqr(), sqrm() : [商,剰余] なるリスト

     sdiv(), sdivm(), srem(), sremm() : polynomial sqr(), sqrm() : a list [quotient,remainder]

poly1 poly2
     多項式

     polynomial

v
     不定元

     indeterminate

mod
     素数

     prime

  * POLY1 を POLY2 の主変数 var(POLY2) ( 引数 V がある場合には V) に関する多項式と見て, POLY2 で, 割り算を行う.

  * sdivm(), sremm(), sqrm() は GF(MOD) 上で計算する.

  * 多項式の除算は, 主係数どうしの割算により得られた商と, 主変数の適当な冪の積を POLY2 に掛けて, POLY1 から引くという操作を POLY1 の次数が POLY2 の次数より小さくなるまで繰り返して行う. この操作が, 多項式の範囲内で行われるためには, 各ステップにおいて主係数どうしの除算が, 多項式としての整除である必要がある. これが, 「除算が最後まで実行できる」ことの意味である.

  * 典型的な場合として, POLY2 の主係数が, 有理数である場合, あるいは, POLY2 が POLY1 の因子であることがわかっている場合などがある.

  * sqr() は商と剰余を同時に求めたい時に用いる.

  * 整数除算の商, 剰余は idiv, irem を用いる.

  * 係数に対する剰余演算は % を用いる.

  * Regarding POLY1 as an uni-variate polynomial in the main variable of POLY2, i.e. var(POLY2) (V if specified), sdiv() and srem() compute the polynomial quotient and remainder of POLY1 divided by POLY2.

  * sdivm(), sremm(), sqrm() execute the same operation over GF(MOD).

  * Division operation of polynomials is performed by the following steps: (1) obtain the quotient of leading coefficients; let it be Q; (2) remove the leading term of POLY1 by subtracting, from POLY1, the product of Q with some powers of main variable and POLY2; obtain a new POLY1; (3) repeat the above step until the degree of POLY1 become smaller than that of POLY2. For fulfillment, by operating in polynomials, of this procedure, the divisions at step (1) in every repetition must be an exact division of polynomials.  This is the true meaning of what we say ``division can be performed within polynomial arithmetic over the rationals.''

  * There are typical cases where the division is possible: leading coefficient of POLY2 is a rational number; POLY2 is a factor of POLY1.

  * Use sqr() to get both the quotient and remainder at once.

  * Use idiv(), irem() for integer quotient.

  * For remainder operation on all integer coefficients, use %.

     [0] sdiv((x+y+z)^3,x^2+y+a);
     x+3*y+3*z
     [1] srem((x+y+z)^2,x^2+y+a);
     (2*y+2*z)*x+y^2+(2*z-1)*y+z^2-a
     [2] X=(x+y+z)*(x-y-z)^2;
     x^3+(-y-z)*x^2+(-y^2-2*z*y-z^2)*x+y^3+3*z*y^2+3*z^2*y+z^3
     [3] Y=(x+y+z)^2*(x-y-z);
     x^3+(y+z)*x^2+(-y^2-2*z*y-z^2)*x-y^3-3*z*y^2-3*z^2*y-z^3
     [4] G=gcd(X,Y);
     x^2-y^2-2*z*y-z^2
     [5] sqr(X,G);
     [x-y-z,0]
     [6] sqr(Y,G);
     [x+y+z,0]
     [7] sdiv(y*x^3+x+1,y*x+1);
     divsp: cannot happen
     return to toplevel

参照

References
     idiv irem, %.

tdiv
----

tdiv(POLY1,POLY2)
     :: POLY1 が POLY2 で割り切れるかどうか調べる.

     :: Tests whether POLY2 divides POLY1.

return
     割り切れるならば商, 割り切れなければ 0

     Quotient if POLY2 divides POLY1, 0 otherwise.

poly1 poly2
     多項式

     polynomial

  * POLY2 が POLY1 を多項式として割り切るかどうか調べる.

  * ある多項式が既約因子であることはわかっているが, その重複度がわからない場合に, tdiv() を繰り返し呼ぶことにより重複度がわかる.

  * Tests whether POLY2 divides POLY1 in polynomial ring.

  * One application of this function: Consider the case where a polynomial is certainly an irreducible factor of the other polynomial, but the multiplicity of the factor is unknown.  Application of tdiv() to the polynomials repeatedly yields the multiplicity.

     [11] Y=(x+y+z)^5*(x-y-z)^3;
     x^8+(2*y+2*z)*x^7+(-2*y^2-4*z*y-2*z^2)*x^6
     +(-6*y^3-18*z*y^2-18*z^2*y-6*z^3)*x^5
     +(6*y^5+30*z*y^4+60*z^2*y^3+60*z^3*y^2+30*z^4*y+6*z^5)*x^3
     +(2*y^6+12*z*y^5+30*z^2*y^4+40*z^3*y^3+30*z^4*y^2+12*z^5*y+2*z^6)*x^2
     +(-2*y^7-14*z*y^6-42*z^2*y^5-70*z^3*y^4-70*z^4*y^3-42*z^5*y^2
     -14*z^6*y-2*z^7)*x-y^8-8*z*y^7-28*z^2*y^6-56*z^3*y^5-70*z^4*y^4
     -56*z^5*y^3-28*z^6*y^2-8*z^7*y-z^8
     [12] for(I=0,F=x+y+z,T=Y; T=tdiv(T,F); I++);
     [13] I;
     5

参照

References
     sdiv sdivm srem sremm sqr sqrm.

%
-

POLY % M
     :: 整数による剰余

     :: integer remainder to all integer coefficients of the polynomial.

return
     整数または多項式

     integer or polynomial

poly
     整数または整数係数多項式

     integer or polynomial with integer coefficients

m
     整数

     intger

  * POLY の各係数を M で割った剰余で置き換えた多項式を返す.

  * 結果の係数は全て正の整数となる.

  * POLY は整数でもよい. この場合, 結果が正に正規化されることを除けば irem() と同様に用いることができる.

  * POLY の係数, M とも整数である必要があるが, チェックは行なわれない.

  * Returns a polynomial whose coefficients are remainders of the coefficients of the input polynomial divided by M.

  * The resulting coefficients are all normalized to non-negative integers.

  * An integer is allowed for POLY.  This can be used for an alternative for irem() except that the result is normalized to a non-negative integer.

  * Coefficients of POLY and M must all be integers, though the type checking is not done.

     [0] (x+2)^5 % 3;
     x^5+x^4+x^3+2*x^2+2*x+2
     [1] (x-2)^5 % 3;
     x^5+2*x^4+x^3+x^2+2*x+1
     [2] (-5) % 4;
     3
     [3] irem(-5,4);
     -1

参照

References
     idiv irem.

subst, psubst
-------------

subst(RAT[,VARN,RATN]*)

psubst(RAT[,VAR,RAT]*)

     :: RAT の VARN に RATN を代入 (N=1,2,... で左から右に順次代入する).

     :: Substitute RATN for VARN in expression RAT. (N=1,2,.... Substitution will be done successively from left to right if arguments are repeated.)

return
     有理式

     rational expression

rat ratn
     有理式

     rational expression

varn
     不定元

     indeterminate

  * 有理式の特定の不定元に, 定数あるいは多項式, 有理式などを代入するのに用いる.

  * subst(RAT,VAR1,RAT1,VAR2,RAT2,...) は, subst(subst(RAT,VAR1,RAT1),VAR2,RAT2,...) と同じ意味である.

  * 入力の左側から順に代入を繰り返すために, 入力の順によって結果が変わることがある.

  * subst() は, sin() などの函数の引数に対しても代入を行う. psubst() は, このような函数を一つの独立した不定元と見なして, その引数には代入は行わない. (partial substitution のつもり)

  * Asir では, 有理式の約分は自動的には行わないため, 有理式の代入は, 思わぬ計算時間の増大を引き起こす場合がある. 有理式を代入する場合には, 問題に応じた独自の函数を書いて, なるべく分母, 分子が大きくならないように配慮することもしばしば必要となる.

  * 分数を代入する場合も同様である.

  * substの引数RATがリスト,配列,行列,あるいは分散表現多項式であった場合には, それぞれの要素または係数に対して再帰的にsubstを行う.

  * Substitutes rational expressions for specified kernels in a rational expression.

  * subst(R,V1,R1,V2,R2,...) has the same effect as subst(subst(R,V1,R1),V2,R2,...).

  * Note that repeated substitution is done from left to right successively. You may get different result by changing the specification order.

  * Ordinary subst() performs substitution at all levels of a scalar algebraic expression creeping into arguments of function forms recursively. Function psubst() regards such a function form as an independent indeterminate, and does not attempt to apply substitution to its arguments.  (The name comes after Partial SUBSTitution.)

  * Since Asir does not reduce common divisors of a rational expression automatically, substitution of a rational expression to an expression may cause unexpected increase of computation time. Thus, it is often necessary to write a special function to meet the individual problem so that the denominator and the numerator do not become too large.

  * The same applies to substitution by rational numbers.

     [0] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2);
     x^3-6*x^2+12*x-8
     [1] subst(@@,x,-1);
     -27
     [2] subst(x^3-3*y*x^2+3*y^2*x-y^3,y,2,x,-1);
     -27
     [3] subst(x*y^3,x,y,y,x);
     x^4
     [4] subst(x*y^3,y,x,x,y);
     y^4
     [5] subst(x*y^3,x,t,y,x,t,y);
     y*x^3
     [6] subst(x*sin(x),x,t);
     sint(t)*t
     [7] psubst(x*sin(x),x,t);
     sin(x)*t

diff
----

diff(RAT[,VARN]*)

diff(RAT,VARLIST)
     :: RAT を VARN あるいは VARLIST の中の変数で順次微分する.

     :: Differentiate RAT successively by VAR's for the first form, or by variables in VARLIST for the second form.

return
     式

     expression

rat
     有理式 (初等函数を含んでもよい)

     rational expression which contains elementary functions.

varn
     不定元

     indeterminate

varlist
     不定元のリスト

     list of indeterminates

  * 与えられた初等函数を VARN あるいは VARLIST の中の変数で順次微分する.

  * 左側の不定元より, 順に微分していく. つまり, diff(RAT,x,y) は, diff(diff(RAT,x),y) と同じである.

  * Differentiate RAT successively by VAR's for the first form, or by variables in VARLIST for the second form.

  * differentiation is performed by the specified indeterminates (variables) from left to right. diff(RAT,x,y) is the same as diff(diff(RAT,x),y).

     [0] diff((x+2*y)^2,x);
     2*x+4*y
     [1] diff((x+2*y)^2,x,y);
     4
     [2] diff(x/sin(log(x)+1),x);
     (sin(log(x)+1)-cos(log(x)+1))/(sin(log(x)+1)^2)
     [3] diff(sin(x),[x,x,x,x]);
     sin(x)

res
---

res(VAR,POLY1,POLY2[,MOD])
     :: VAR に関する POLY1 と POLY2 の終結式.

     :: Resultant of POLY1 and POLY2 with respect to VAR.

return
     多項式

     polynomial

var
     不定元

     indeterminate

poly1 poly2
     多項式

     polynomial

mod
     素数

     prime

  * 二つの多項式 POLY1 と POLY2 の, 変数 VAR に関する終結式を求める.

  * 部分終結式アルゴリズムによる.

  * 引数 MOD がある時, GF(MOD) 上での計算を行う.

  * Resultant of two polynomials POLY1 and POLY2 with respect to VAR.

  * Sub-resultant algorithm is used to compute the resultant.

  * The computation is done over GF(MOD) if MOD is specified.

     [0] res(t,(t^3+1)*x+1,(t^3+1)*y+t);
     -x^3-x^2-y^3

fctr, sqfr
----------

fctr(POLY)
     :: POLY を既約因子に分解する.

     :: Factorize polynomial POLY over the rationals.

sqfr(POLY)
     :: POLY を無平方分解する.

     :: Gets a square-free factorization of polynomial POLY.

return
     リスト

     list

poly
     有理数係数の多項式

     polynomial with rational coefficients

  * 有理数係数の多項式 POLY を因数分解する. fctr() は既約因子分解, sqfr() は無平方因子分解.

  * 結果は [[数係数,1],[因子,重複度],...] なるリスト.

  * 数係数 と 全ての 因子^重複度 の積が POLY と等しい.

  * 数係数 は, (POLY/数係数) が, 整数係数で, 係数の GCD が 1 となるような多項式になるように選ばれている. (ptozp() 参照)

  * Factorizes polynomial POLY over the rationals. fctr() for irreducible factorization; sqfr() for square-free factorization.

  * The result is represented by a list, whose elements are a pair represented as

     [[num,1],[factor,multiplicity],...].

  * Products of all factor^multiplicity and num is equal to POLY.

  * The number num is determined so that (POLY/num) is an integral polynomial and its content (GCD of all coefficients) is 1. (see ptozp.)

     [0] fctr(x^10-1);
     [[1,1],[x-1,1],[x+1,1],[x^4+x^3+x^2+x+1,1],[x^4-x^3+x^2-x+1,1]]
     [1] fctr(x^3+y^3+(z/3)^3-x*y*z);
     [[1/27,1],[9*x^2+(-9*y-3*z)*x+9*y^2-3*z*y+z^2,1],[3*x+3*y+z,1]]
     [2] A=(a+b+c+d)^2;
     a^2+(2*b+2*c+2*d)*a+b^2+(2*c+2*d)*b+c^2+2*d*c+d^2
     [3] fctr(A);
     [[1,1],[a+b+c+d,2]]
     [4] A=(x+1)*(x^2-y^2)^2;
     x^5+x^4-2*y^2*x^3-2*y^2*x^2+y^4*x+y^4
     [5] sqfr(A);
     [[1,1],[x+1,1],[-x^2+y^2,2]]
     [6] fctr(A);
     [[1,1],[x+1,1],[-x-y,2],[x-y,2]]

参照

References
     ufctrhint.

ufctrhint
---------

ufctrhint(POLY,HINT)
     :: 次数情報を用いた 1 変数多項式の因数分解

     :: Factorizes uni-variate polynomial POLY over the rational number field when the degrees of its factors are known to be some integer multiples of HINT.

return
     リスト

     list

poly
     有理数係数の 1 変数多項式

     uni-variate polynomial with rational coefficients

hint
     自然数

     non-negative integer

  * 各既約因子の次数が HINT の倍数であることがわかっている場合に POLY の既約因子分解を fctr() より効率良く行う. POLY が, D 次の拡大体上におけるある多項式のノルム (代数的数に関する演算) で無平方である場合, 各既約因子の次数は D の倍数となる. このような場合に用いられる.

  * By any reason, if the degree of all the irreducible factors of POLY is known to be some multiples of HINT, factors can be computed more efficiently by the knowledge than fctr().

  * When HINT is 1, ufctrhint() is the same as fctr() for uni-variate polynomials. An typical application where ufctrhint() is effective: Consider the case where POLY is a norm (Algebraic numbers) of a certain polynomial over an extension field with its extension degree D, and it is square free;  Then, every irreducible factor has a degree that is a multiple of D.

     [10] A=t^9-15*t^6-87*t^3-125;
     t^9-15*t^6-87*t^3-125
     0msec
     [11] N=res(t,subst(A,t,x-2*t),A);
     -x^81+1215*x^78-567405*x^75+139519665*x^72-19360343142*x^69
     +1720634125410*x^66-88249977024390*x^63-4856095669551930*x^60
     +1999385245240571421*x^57-15579689952590251515*x^54
     +15956967531741971462865*x^51
     ...
     +140395588720353973535526123612661444550659875*x^6
     +10122324287343155430042768923500799484375*x^3
     +139262743444407310133459021182733314453125
     980msec + gc : 250msec
     [12] sqfr(N);
     [[-1,1],[x^81-1215*x^78+567405*x^75-139519665*x^72+19360343142*x^69
     -1720634125410*x^66+88249977024390*x^63+4856095669551930*x^60
     -1999385245240571421*x^57+15579689952590251515*x^54
     ...
     -10122324287343155430042768923500799484375*x^3
     -139262743444407310133459021182733314453125,1]]
     20msec
     [13] fctr(N);
     [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
     [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
     +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
     [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3
     +31524548679,1],
     [x^18+10773*x^12+2784051*x^6+307546875,1]]
     167.050sec + gc : 1.890sec
     [14] ufctrhint(N,9);
     [[-1,1],[x^9-405*x^6-63423*x^3-2460375,1],
     [x^18-486*x^15+98739*x^12-9316620*x^9+945468531*x^6-12368049246*x^3
     +296607516309,1],[x^18-8667*x^12+19842651*x^6+19683,1],
     [x^18-324*x^15+44469*x^12-1180980*x^9+427455711*x^6+2793253896*x^3
     +31524548679,1],
     [x^18+10773*x^12+2784051*x^6+307546875,1]]
     119.340sec + gc : 1.300sec

参照

References
     fctr sqfr.

modfctr
-------

modfctr(POLY,MOD)
     :: 有限体上での多項式の因数分解

     :: Factorizer over small finite fields

return
     リスト

     list

poly
     整数係数の多項式

     Polynomial with integer coefficients

mod
     自然数

     non-negative integer

  * 2^29 未満の自然数 MOD を標数とする素体上で多項式 POLY を既約因子に分解する.

  * 結果は [[数係数,1],[因子,重複度],...] なるリスト.

  * 数係数 と 全ての 因子^重複度 の積が POLY と等しい.

  * 大きな位数を持つ有限体上の因数分解には fctr_ff を用いる. (有限体に関する演算,see fctr_ff).

  * This function factorizes a polynomial POLY over the finite prime field of characteristic MOD, where MOD must be smaller than 2^29.

  * The result is represented by a list, whose elements are a pair represented as

     [[num,1],[factor,multiplicity],...].

  * Products of all factor^multiplicity and num is equal to POLY.

  * To factorize polynomials over large finite fields, use fctr_ff (see Finite fields,fctr_ff).

     [0] modfctr(x^10+x^2+1,2147483647);
     [[1,1],[x+1513477736,1],[x+2055628767,1],[x+91854880,1],
     [x+634005911,1],[x+1513477735,1],[x+634005912,1],
     [x^4+1759639395*x^2+2045307031,1]]
     [1] modfctr(2*x^6+(y^2+z*y)*x^4+2*z*y^3*x^2+(2*z^2*y^2+z^3*y)*x+z^4,3);
     [[2,1],[2*x^3+z*y*x+z^2,1],[2*x^3+y^2*x+2*z^2,1]]

参照

References
     fctr sqfr.

ptozp
-----

ptozp(POLY)
     :: POLY を有理数倍して整数係数多項式にする.

     :: Converts a polynomial POLY with rational coefficients into an integral polynomial such that GCD of all its coefficients is 1.

return
     多項式

     polynomial

poly
     多項式

     polynomial

  * 与えられた多項式 POLY に適当な有理数を掛けて, 整数係数かつ係数の GCD が 1 になるようにする.

  * 分数の四則演算は, 整数の演算に比較して遅いため, 種々の多項式演算の前に, 多項式を整数係数にしておくことが望ましい.

  * 有理式を約分する red() で分数係数有理式を約分しても, 分子多項式の係数は有理数のままであり, 有理式の分子を求める nm() では, 分数係数多項式は, 分数係数のままの形で出力されるため, 直ちに整数係数多項式を得る事は出来ない.

  * Converts the given polynomial by multiplying some rational number into an integral polynomial such that GCD of all its coefficients is 1.

  * In general, operations on polynomials can be performed faster for integer coefficients than for rational number coefficients.  Therefore, this function is conveniently used to improve efficiency.

  * Function red does not convert rational coefficients of the numerator. You cannot obtain an integral polynomial by direct use of the function nm().  The function nm() returns the numerator of its argument, and a polynomial with rational coefficients is the numerator of itself and will be returned as it is.

     [0] ptozp(2*x+5/3);
     6*x+5
     [1] nm(2*x+5/3);
     2*x+5/3

参照

References
     nm dn.

prim, cont
----------

prim(POLY[,V])
     :: POLY の原始的部分 (primitive part).

     :: Primitive part of POLY.

cont(POLY[,V])
     :: POLY の容量 (content).

     :: Content of POLY.

return poly
     有理数係数多項式

     polynomial over the rationals

v
     不定元

     indeterminate

  * POLY の主変数 (引数 V がある場合には V) に関する原始的部分, 容量を求める.

  * The primitive part and the content of a polynomial POLY with respect to its main variable (V if specified).

     [0] E=(y-z)*(x+y)*(x-z)*(2*x-y);
     (2*y-2*z)*x^3+(y^2-3*z*y+2*z^2)*x^2+(-y^3+z^2*y)*x+z*y^3-z^2*y^2
     [1] prim(E);
     2*x^3+(y-2*z)*x^2+(-y^2-z*y)*x+z*y^2
     [2] cont(E);
     y-z
     [3] prim(E,z);
     (y-z)*x-z*y+z^2

参照

References
     var, ord.

gcd, gcdz
---------

gcd(POLY1,POLY2[,MOD])

gcdz(POLY1,POLY2)
     :: POLY1 と POLY2 の gcd.

     :: The polynomial greatest common divisor of POLY1 and POLY2.

return
     多項式

     polynomial

poly1 poly2
     多項式

     polynomial

mod
     素数

     prime

  * 二つの多項式の最大公約式 (GCD) を求める.

  * gcd() は有理数体上の多項式としての GCD を返す. すなわち, 結果は整数係数で, かつ係数の GCD が 1 になるような多項式, または, 互いに素の場合は 1 を返す.

  * gcdz() は POLY1, POLY2 ともに整数係数の場合に, 整数環上の多項式としての GCD を返す. すなわち, gcd() の値に, 係数全体の整数 GCDの値を掛けたものを返す.

  * 引数 MOD がある時, gcd() は GF(MOD) 上での GCD を返す.

  * gcd(), gcdz() Extended Zassenhaus アルゴリズムによる. 有限体上の GCD は PRS アルゴリズムによっているため, 大きな問題, GCD が 1 の場合などにおいて効率が悪い.

  * Functions gcd() and gcdz() return the greatest common divisor (GCD) of the given two polynomials.

  * Function gcd() returns an integral polynomial GCD over the rational number field.  The coefficients are normalized such that their GCD is 1.  It returns 1 in case that the given polynomials are mutually prime.

  * Function gcdz() works for arguments of integral polynomials, and returns a polynomial GCD over the integer ring, that is, it returns gcd() multiplied by the contents of all coefficients of the two input polynomials.

  * gcd() computes the GCD over GF(MOD) if MOD is specified.

  * Polynomial GCD is computed by an improved algorithm based on Extended Zassenhaus algorithm.

  * GCD over a finite field is computed by PRS algorithm and it may not be efficient for large inputs and co-prime inputs.

     [0] gcd(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     x^3+3*x^2+3*x+1
     [1] gcdz(12*(x^2+2*x+1)^2,18*(x^2+(y+1)*x+y)^3);
     6*x^3+18*x^2+18*x+6
     [2] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y));
     x^2-y^2
     [3] gcd((x+y)*(x-y)^2,(x+y)^2*(x-y),2);
     x^3+y*x^2+y^2*x+y^3

参照

References
     igcd igcdcntl.

red
---

red(RAT)
     :: RAT を約分したもの.

     :: Reduced form of RAT by canceling common divisors.

return
     有理式

     rational expression

rat
     有理式

     rational expression

  * Asir は有理数の約分を常に自動的に行う. しかし, 有理式については通分は行うが, 約分はユーザーが指定しない限り行わない. この約分を行うコマンドが red である.

  * EZGCD により RAT の分子, 分母を約分する.

  * 出力される有理式の分母の多項式は, 各係数の GCD が 1 の整数係数多項式である. 分子については整数係数多項式となるとは限らない.

  * GCD は大変重い演算なので, 他の方法で除ける共通因子は可能な限り除くのが望ましい. また, 分母, 分子が大きくなってからのこの函数の呼び出しは, 非常に時間が掛かる場合が多い. 有理式演算を行う場合は, ある程度頻繁に, 約分を行う必要がある.

  * Asir automatically performs cancellation of common divisors of rational numb ers. But, without an explicit command, it does not cancel common polynomial divisors of rational expressions. (Reduction of rational expressions to a common denominator will be always done.) Use command red() to perform this cancellation.

  * Cancel the common divisors of the numerator and the denominator of a rational expression RAT by computing their GCD.

  * The denominator polynomial of the result is an integral polynomial which has no common divisors in its coefficients, while the numerator may have rational coefficients.

  * Since GCD computation is a very hard operation, it is desirable to detect and remove by any means common divisors as far as possible. Furthermore, a call to this function after swelling of the denominator and the numerator shall usually take a very long time.  Therefore, often, to some extent, reduction of common divisors is inevitable for operations of rational expressions.

     [0] (x^3-1)/(x-1);
     (x^3-1)/(x-1)
     [1] red((x^3-1)/(x-1));
     x^2+x+1
     [2] red((x^3+y^3+z^3-3*x*y*z)/(x+y+z));
     x^2+(-y-z)*x+y^2-z*y+z^2
     [3] red((3*x*y)/(12*x^2+21*y^3*x));
     (y)/(4*x+7*y^3)
     [4] red((3/4*x^2+5/6*x)/(2*y*x+4/3*x));
     (9/8*x+5/4)/(3*y+2)

参照

References
     nm dn, gcd gcdz, ptozp.