Return to poly.texi CVS log

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

Explanation on ptozp(F | factor=1).

@comment $OpenXM: OpenXM/src/asir-doc/parts/builtin/poly.texi,v 1.8 2004/05/15 08:25:12 takayama Exp $
\BJP
@node $BB?9`<0$*$h$SM-M}<0$N1i;;(B,,, $BAH$_9~$_H!?t(B
@section $BB?9`<0(B, $BM-M}<0$N1i;;(B
\E
\BEG
@node Polynomials and rational expressions,,, Built-in Function
@section operations with polynomials and rational expressions
\E

@menu
* var::
* vars::
* uc::
* coef::
* deg mindeg::
* nmono::
* ord::
* sdiv sdivm srem sremm sqr sqrm::
* tdiv::
* %::
* subst psubst::
* diff::
* ediff::
* res::
* fctr sqfr::
* modfctr::
* ufctrhint::
* ptozp::
* prim cont::
* gcd gcdz::
* red::
@end menu

\JP @node var,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node var,,, Polynomials and rational expressions
@subsection @code{var}
@findex var

@table @t
@item var(@var{rat}) 
\JP :: @var{rat} $B$N<gJQ?t(B. 
\EG :: Main variable (indeterminate) of @var{rat}.
@end table

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

@itemize @bullet
\BJP
@item
$B<gJQ?t$K4X$7$F$O(B, @xref{Asir $B$G;HMQ2DG=$J7?(B}.
@item 
$B%G%U%)%k%H$NJQ?t=g=x$O<!$N$h$&$K$J$C$F$$$k(B. 

@code{x}, @code{y}, @code{z}, @code{u}, @code{v}, @code{w}, @code{p}, @code{q}, @code{r}, @code{s}, @code{t}, @code{a}, @code{b}, @code{c}, @code{d}, @code{e},
@code{f}, @code{g}, @code{h}, @code{i}, @code{j}, @code{k}, @code{l}, @code{m}, @code{n}, @code{o},$B0J8e$OJQ?t$N8=$l$?=g(B. 
\E
\BEG
@item
See @ref{Types in Asir} for main variable.
@item
Indeterminates (variables) are ordered by default as follows.
 
@code{x}, @code{y}, @code{z}, @code{u}, @code{v}, @code{w}, @code{p}, @code{q},
@code{r}, @code{s}, @code{t}, @code{a}, @code{b}, @code{c}, @code{d}, @code{e},
@code{f}, @code{g}, @code{h}, @code{i}, @code{j}, @code{k}, @code{l}, @code{m},
@code{n}, @code{o}. The other variables will be ordered after the above noted variables
so that the first comer will be ordered prior to the followers.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{ord}, @fref{vars}.
@end table

\JP @node vars,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node vars,,, Polynomials and rational expressions
@subsection @code{vars}
@findex vars

@table @t
@item vars(@var{obj})
\JP :: @var{obj} $B$K4^$^$l$kJQ?t$N%j%9%H(B. 
\EG :: A list of variables (indeterminates) in an expression @var{obj}.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item obj
\JP $BG$0U(B
\EG arbitrary
@end table

@itemize @bullet
\BJP
@item
$BM?$($i$l$?<0$K4^$^$l$kJQ?t$N%j%9%H$rJV$9(B. 
@item
$BJQ?t=g=x$N9b$$$b$N$+$i=g$KJB$Y$k(B. 
\E
\BEG
@item
Returns a list of variables (indeterminates) contained in a given expression.
@item
Lists variables according to the variable ordering.
\E
@end itemize

@example
[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]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{var}, @fref{uc}, @fref{ord}.
@end table

\JP @node uc,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node uc,,, Polynomials and rational expressions
@subsection @code{uc}
@findex uc

@table @t
@item uc()
\JP :: $BL$Dj78?tK!$N$?$a$NITDj85$r@8@.$9$k(B. 
\EG :: Create a new indeterminate for an undermined coeficient.
@end table

@table @var
@item return
\JP @code{vtype} $B$,(B 1 $B$NITDj85(B
\EG indeterminate with its @code{vtype} 1.
@end table

@itemize @bullet
\BJP
@item
@code{uc()} $B$r<B9T$9$k$?$S$K(B, @code{_0}, @code{_1}, @code{_2},... $B$H$$$&(B
$BITDj85$r@8@.$9$k(B. 
@item
@code{uc()} $B$G@8@.$5$l$?ITDj85$O(B, $BD>@\%-!<%\!<%I$+$iF~NO$9$k$3$H$,$G$-$J$$(B. 
$B$3$l$O(B, $B%W%m%0%i%`Cf$GL$Dj78?t$r<+F0@8@.$9$k>l9g(B, $BF~NO$J$I$K4^$^$l$k(B
$BITDj85$HF10l$N$b$N$,@8@.$5$l$k$3$H$rKI$0$?$a$G$"$k(B. 
@item
$BDL>o$NITDj85(B (@code{vtype} $B$,(B 0) $B$N<+F0@8@.$K$O(B @code{rtostr()}, 
@code{strtov()} $B$rMQ$$$k(B. 
@item
@code{uc()} $B$G@8@.$5$l$?ITDj85$NITDj85$H$7$F$N7?(B (@code{vtype}) $B$O(B 1 $B$G$"$k(B. 
(@xref{$BITDj85$N7?(B}.)
\E
\BEG
@item
At every evaluation of command @code{uc()}, a new indeterminate in
the sequence of indeterminates @code{_0}, @code{_1}, @code{_2}, @dots{}
is created successively.
@item
Indeterminates created by @code{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.
@item
Functions, @code{rtostr()} and @code{strtov()}, are used to create
ordinary indeterminates (indeterminates having 0 for their @code{vtype}).
@item
Kernel sub-type of indeterminates created by @code{uc()} is 1.
(@code{vtype(uc())}=1)
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{vtype}, @fref{rtostr}, @fref{strtov}.
@end table

\JP @node coef,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node coef,,, Polynomials and rational expressions
@subsection @code{coef}
@findex coef

@table @t
@item coef(@var{poly},@var{deg}[,@var{var}])
\JP :: @var{poly} $B$N(B @var{var} ($B>JN,;~$O<gJQ?t(B) $B$K4X$9$k(B @var{deg} $B<!$N78?t(B. 
\BEG
:: The coefficient of a polynomial @var{poly} at degree @var{deg}
with respect to the variable @var{var} (main variable if unspecified).
\E
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item var
\JP $BITDj85(B
\EG indeterminate
@item deg
\JP $B<+A3?t(B
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
@var{poly} $B$N(B @var{var} $B$K4X$9$k(B @var{deg} $B<!$N78?t$r=PNO$9$k(B. 
@item
@var{var} $B$O(B, $B>JN,$9$k$H<gJQ?t(B @t{var}(@var{poly}) $B$@$H$_$J$5$l$k(B. 
@item
@var{var} $B$,<gJQ?t$G$J$$;~(B, @var{var} $B$,<gJQ?t$N>l9g$KHf3S$7$F(B
$B8zN($,Mn$A$k(B. 
\E
\BEG
@item
The coefficient of a polynomial @var{poly} at degree @var{deg}
with respect to the variable @var{var}.
@item
The default value for @var{var} is the main variable, i.e.,
@t{var(@var{poly})}.
@item
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.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{var}, @fref{deg mindeg}.
@end table

\JP @node deg mindeg,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node deg mindeg,,, Polynomials and rational expressions
@subsection @code{deg}, @code{mindeg}
@findex deg
@findex mindeg

@table @t
@item deg(@var{poly},@var{var})
\JP :: @var{poly} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k:G9b<!?t(B. 
\EG :: The degree of a polynomial @var{poly} with respect to variable.
@item mindeg(@var{poly},@var{var})
\JP :: @var{poly} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k:GDc<!?t(B. 
\BEG
:: The least exponent of the terms with non-zero coefficients in
a polynomial @var{poly} with respect to the variable @var{var}.
In this manual, this quantity is sometimes referred to the minimum
degree of a polynomial for short.
\E
@end table

@table @var
@item return	
\JP $B<+A3?t(B
\EG non-negative integer
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item var
\JP $BITDj85(B
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
$BM?$($i$l$?B?9`<0$NJQ?t(B @var{var} $B$K4X$9$k:G9b<!?t(B, $B:GDc<!?t$r=PNO$9$k(B. 
@item
$BJQ?t(B @var{var} $B$r>JN,$9$k$3$H$O=PMh$J$$(B. 
\E
\BEG
@item
The least exponent of the terms with non-zero coefficients in
a polynomial @var{poly} with respect to the variable @var{var}.
In this manual, this quantity is sometimes referred to the minimum
degree of a polynomial for short.
@item
Variable @var{var} must be specified.
\E
@end itemize

@example
[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
@end example

\JP @node nmono,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node nmono,,,Polynomials and rational expressions
@subsection @code{nmono}
@findex nmono

@table @t
@item nmono(@var{rat})
\JP :: @var{rat} $B$NC19`<0$N9`?t(B. 
\EG :: Number of monomials in rational expression @var{rat}.
@end table

@table @var
@item return
\JP $B<+A3?t(B
\EG non-negative integer
@item rat
\JP $BM-M}<0(B
\EG rational expression
@end table

@itemize @bullet
\BJP
@item
$BB?9`<0$rE83+$7$?>uBV$G$N(B 0 $B$G$J$$78?t$r;}$DC19`<0$N9`?t$r5a$a$k(B. 
@item
$BM-M}<0$N>l9g$O(B, $BJ,;R$HJ,Jl$N9`?t$NOB$,JV$5$l$k(B. 
@item
$BH!?t7A<0(B (@ref{$BITDj85$N7?(B}) $B$O(B, $B0z?t$,2?$G$"$C$F$bC19`$H$_$J$5$l$k(B. (1 $B8D$NITDj85$HF1$8(B. )
\E
\BEG
@item
Number of monomials with non-zero number coefficients in the full
expanded form of the given polynomial.
@item
For a rational expression, the sum of the numbers of monomials
of the numerator and denominator.
@item
A function form is regarded as a single indeterminate no matter how
complex arguments it has.
\E
@end itemize

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

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{vtype}.
@end table

\JP @node ord,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node ord,,, Polynomials and rational expressions
@subsection @code{ord}
@findex ord

@table @t
@item ord([@var{varlist}])
\JP :: $BJQ?t=g=x$N@_Dj(B
\EG :: It sets the ordering of indeterminates (variables).
@end table

@table @var
@item return	
\JP $BJQ?t$N%j%9%H(B
\EG list of indeterminates 
@item varlist
\JP $BJQ?t$N%j%9%H(B
\EG list of indeterminates 
@end table

@itemize @bullet
\BJP
@item
$B0z?t$,$"$k$H$-(B, $B0z?t$NJQ?t%j%9%H$r@hF,$K=P$7(B, $B;D$j$NJQ?t$,$=$N8e$K(B
$BB3$/$h$&$KJQ?t=g=x$r@_Dj$9$k(B. $B0z?t$N$"$k$J$7$K4X$o$i$:(B, @code{ord()}
$B$N=*N;;~$K$*$1$kJQ?t=g=x%j%9%H$rJV$9(B. 

@item
$B$3$NH!?t$K$h$kJQ?t=g=x$NJQ99$r9T$C$F$b(B, $B4{$K%W%m%0%i%`JQ?t$J$I$K(B
$BBeF~$5$l$F$$$k<0$NFbIt7A<0$O?7$7$$=g=x$K=>$C$F$OJQ99$5$l$J$$(B. 
$B=>$C$F(B, $B$3$NH!?t$K$h$k=g=x$NJQ99$O(B, @b{Asir} $B$N5/F0D>8e(B, 
$B$"$k$$$O(B, $B?7$?$JJQ?t$,8=$l$?;~E@$K9T$o$l$k(B
$B$Y$-$G$"$k(B. $B0[$J$kJQ?t=g=x$N$b$H$G@8@.$5$l$?<0$I$&$7$N1i;;(B
$B$,9T$o$l$?>l9g(B, $BM=4|$;$L7k2L$,@8$:$k$3$H$b$"$jF@$k(B. 
\E
\BEG
@item
When an argument is given,
this function rearranges the ordering of variables (indeterminates)
so that the indeterminates in the argument @var{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.

@item
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 @b{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.
\E
@end itemize

@example
[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)]
@end example

\JP @node sdiv sdivm srem sremm sqr sqrm,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node sdiv sdivm srem sremm sqr sqrm,,, Polynomials and rational expressions
@subsection @code{sdiv}, @code{sdivm}, @code{srem}, @code{sremm}, @code{sqr}, @code{sqrm}
@findex sdiv
@findex sdivm
@findex srem
@findex sremm
@findex sqr
@findex sqrm

@table @t
@item sdiv(@var{poly1},@var{poly2}[,@var{v}])
@itemx sdivm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
\JP :: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>&$r5a$a$k(B. 
\BEG
:: Quotient of @var{poly1} divided by @var{poly2} provided that the
division can be performed within polynomial arithmetic over the
rationals.
\E
@item srem(@var{poly1},@var{poly2}[,@var{v}])
@item sremm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
\JP :: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>jM>$r5a$a$k(B. 
\BEG
:: Remainder of @var{poly1} divided by @var{poly2} provided that the
division can be performed within polynomial arithmetic over the
rationals.
\E
@item sqr(@var{poly1},@var{poly2}[,@var{v}])
@item sqrm(@var{poly1},@var{poly2},@var{mod}[,@var{v}])
\BJP
:: @var{poly1} $B$r(B @var{poly2} $B$G3d$k=|;;$,:G8e$^$G<B9T$G$-$k>l9g$K>&(B, $B>jM>$r(B
$B5a$a$k(B. 
\E
\BEG
:: Quotient and remainder of @var{poly1} divided by @var{poly2} provided
that the division can be performed within polynomial arithmetic over
the rationals.
\E
@end table

@table @var
@item return
\JP @code{sdiv()}, @code{sdivm()}, @code{srem()}, @code{sremm()} : $BB?9`<0(B, @code{sqr()}, @code{sqrm()} : @code{[$B>&(B,$B>jM>(B]} $B$J$k%j%9%H(B
\EG @code{sdiv()}, @code{sdivm()}, @code{srem()}, @code{sremm()} : polynomial @code{sqr()}, @code{sqrm()} : a list @code{[quotient,remainder]}
@item poly1 poly2
\JP $BB?9`<0(B
\EG polynomial
@item v
\JP $BITDj85(B
\EG indeterminate
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
@var{poly1} $B$r(B @var{poly2} $B$N<gJQ?t(B @t{var}(@var{poly2}) 
( $B0z?t(B @var{v} $B$,$"$k>l9g$K$O(B @var{v}) $B$K4X$9$kB?9`<0$H8+$F(B, 
@var{poly2} $B$G(B, $B3d$j;;$r9T$&(B.
@item
@code{sdivm()}, @code{sremm()}, @code{sqrm()} $B$O(B GF(@var{mod}) $B>e$G7W;;$9$k(B. 
@item
$BB?9`<0$N=|;;$O(B, $B<g78?t$I$&$7$N3d;;$K$h$jF@$i$l$?>&$H(B, $B<gJQ?t$NE,Ev$JQQ$N(B
$B@Q$r(B @var{poly2} $B$K3]$1$F(B, @var{poly1} $B$+$i0z$/$H$$$&A`:n$r(B
@var{poly1} $B$N<!?t$,(B @var{poly2} $B$N<!?t$h$j>.$5$/$J$k$^$G7+$jJV$7$F(B
$B9T$&(B. $B$3$NA`:n$,(B, $BB?9`<0$NHO0OFb$G9T$o$l$k$?$a$K$O(B, $B3F%9%F%C%W$K$*$$$F(B
$B<g78?t$I$&$7$N=|;;$,(B, $BB?9`<0$H$7$F$N@0=|$G$"$kI,MW$,$"$k(B. $B$3$l$,(B, $B!V=|;;(B
$B$,:G8e$^$G<B9T$G$-$k!W$3$H$N0UL#$G$"$k(B. 
@item
$BE57?E*$J>l9g$H$7$F(B, @var{poly2} $B$N<g78?t$,(B, $BM-M}?t$G$"$k>l9g(B, $B$"$k$$$O(B, 
@var{poly2} $B$,(B @var{poly1} $B$N0x;R$G$"$k$3$H$,$o$+$C$F$$$k>l9g$J$I(B
$B$,$"$k(B. 
@item
@code{sqr()} $B$O>&$H>jM>$rF1;~$K5a$a$?$$;~$KMQ$$$k(B. 
@item
$B@0?t=|;;$N>&(B, $B>jM>$O(B @code{idiv}, @code{irem} $B$rMQ$$$k(B. 
@item
$B78?t$KBP$9$k>jM>1i;;$O(B @code{%} $B$rMQ$$$k(B. 
\E
\BEG
@item
Regarding @var{poly1} as an uni-variate polynomial in the main variable
of @var{poly2},
i.e. @t{var(@var{poly2})} (@var{v} if specified), @code{sdiv()} and
@code{srem()} compute
the polynomial quotient and remainder of @var{poly1} divided by @var{poly2}.
@item @code{sdivm()}, @code{sremm()}, @code{sqrm()} execute the same
operation over GF(@var{mod}).
@item
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 @var{poly1} by subtracting, from
@var{poly1}, the product of Q with some powers of main variable
and @var{poly2}; obtain a new @var{poly1};
(3) repeat the above step until the degree of @var{poly1} become smaller
than that of @var{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.''
@item
There are typical cases where the division is possible:
leading coefficient of @var{poly2} is a rational number;
@var{poly2} is a factor of @var{poly1}.
@item
Use @code{sqr()} to get both the quotient and remainder at once.
@item
Use @code{idiv()}, @code{irem()} for integer quotient.
@item
For remainder operation on all integer coefficients, use @code{%}.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{idiv irem}, @fref{%}.
@end table

\JP @node tdiv,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node tdiv,,, Polynomials and rational expressions
@subsection @code{tdiv}
@findex tdiv

@table @t
@item tdiv(@var{poly1},@var{poly2})
\JP :: @var{poly1} $B$,(B @var{poly2} $B$G3d$j@Z$l$k$+$I$&$+D4$Y$k(B. 
\EG :: Tests whether @var{poly2} divides @var{poly1}.
@end table

@table @var
@item return	
\JP $B3d$j@Z$l$k$J$i$P>&(B, $B3d$j@Z$l$J$1$l$P(B 0
\EG Quotient if @var{poly2} divides @var{poly1}, 0 otherwise.
@item poly1 poly2
\JP $BB?9`<0(B
\EG polynomial
@end table

@itemize @bullet
\BJP
@item
@var{poly2} $B$,(B @var{poly1} $B$rB?9`<0$H$7$F3d$j@Z$k$+$I$&$+D4$Y$k(B. 
@item
$B$"$kB?9`<0$,4{Ls0x;R$G$"$k$3$H$O$o$+$C$F$$$k$,(B, $B$=$N=EJ#EY$,$o$+$i$J$$(B
$B>l9g$K(B, @code{tdiv()} $B$r7+$jJV$78F$V$3$H$K$h$j=EJ#EY$,$o$+$k(B. 
\E
\BEG
@item
Tests whether @var{poly2} divides @var{poly1} in polynomial ring.
@item
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 @code{tdiv()}
to the polynomials repeatedly yields the multiplicity.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{sdiv sdivm srem sremm sqr sqrm}.
@end table

\JP @node %,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node %,,, Polynomials and rational expressions
@subsection @code{%}
@findex %

@table @t
@item @var{poly} % @var{m}
\JP :: $B@0?t$K$h$k>jM>(B
\EG :: integer remainder to all integer coefficients of the polynomial.
@end table

@table @var
@item return	
\JP $B@0?t$^$?$OB?9`<0(B
\EG integer or polynomial
@item poly
\JP $B@0?t$^$?$O@0?t78?tB?9`<0(B
\EG integer or polynomial with integer coefficients
@item m
\JP $B@0?t(B
\EG intger
@end table

@itemize @bullet
\BJP
@item
@var{poly} $B$N3F78?t$r(B @var{m} $B$G3d$C$?>jM>$GCV$-49$($?B?9`<0$rJV$9(B. 
@item
$B7k2L$N78?t$OA4$F@5$N@0?t$H$J$k(B. 
@item
@var{poly} $B$O@0?t$G$b$h$$(B. $B$3$N>l9g(B, $B7k2L$,@5$K@55,2=$5$l$k$3$H$r=|$1$P(B
@code{irem()} $B$HF1MM$KMQ$$$k$3$H$,$G$-$k(B. 
@item
@var{poly} $B$N78?t(B, @var{m} $B$H$b@0?t$G$"$kI,MW$,$"$k$,(B, $B%A%'%C%/$O9T$J$o$l$J$$(B. 
\E
\BEG
@item
Returns a polynomial whose coefficients are remainders of the
coefficients of the input polynomial divided by @var{m}.
@item
The resulting coefficients are all normalized to non-negative integers.
@item
An integer is allowed for @var{poly}.  This can be used for an
alternative for @code{irem()} except that the result is normalized to
a non-negative integer.
@item
Coefficients of @var{poly} and @var{m} must all be integers, though the
type checking is not done.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{idiv irem}.
@end table

\JP @node subst psubst,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node subst psubst,,, Polynomials and rational expressions
@subsection @code{subst}, @code{psubst}
@findex subst
@findex psubst

@table @t
@item subst(@var{rat}[,@var{varn},@var{ratn}]*)
@item psubst(@var{rat}[,@var{var},@var{rat}]*)
\BJP
:: @var{rat} $B$N(B @var{varn} $B$K(B @var{ratn} $B$rBeF~(B
(@var{n}=1,2,... $B$G:8$+$i1&$K=g<!BeF~$9$k(B). 
\E
\BEG
:: Substitute @var{ratn} for @var{varn} in expression @var{rat}.
(@var{n}=1,2,@dots{}.
Substitution will be done successively from left to right
if arguments are repeated.)
\E
@end table

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

@itemize @bullet
\BJP
@item
$BM-M}<0$NFCDj$NITDj85$K(B, $BDj?t$"$k$$$OB?9`<0(B, $BM-M}<0$J$I$rBeF~$9$k$N$KMQ$$$k(B. 
@item
@t{subst}(@var{rat},@var{var1},@var{rat1},@var{var2},@var{rat2},...) $B$O(B, 
@t{subst}(@t{subst}(@var{rat},@var{var1},@var{rat1}),@var{var2},@var{rat2},...) 
$B$HF1$80UL#$G$"$k(B. 
@item
$BF~NO$N:8B&$+$i=g$KBeF~$r7+$jJV$9$?$a$K(B, $BF~NO$N=g$K$h$C$F7k2L$,JQ$o$k$3$H$,$"$k(B. 
@item
@code{subst()} $B$O(B, @code{sin()} $B$J$I$NH!?t$N0z?t$KBP$7$F$bBeF~$r9T$&(B. 
@code{psubst()} $B$O(B, $B$3$N$h$&$JH!?t$r0l$D$NFHN)$7$?ITDj85$H8+$J$7$F(B, $B$=(B
$B$N0z?t$K$OBeF~$O9T$o$J$$(B. (partial substitution $B$N$D$b$j(B)
@item
@b{Asir} $B$G$O(B, $BM-M}<0$NLsJ,$O<+F0E*$K$O9T$o$J$$$?$a(B, 
$BM-M}<0$NBeF~$O(B, $B;W$o$L7W;;;~4V$NA}Bg$r0z$-5/$3$9>l9g$,$"$k(B. 
$BM-M}<0$rBeF~$9$k>l9g$K$O(B, $BLdBj$K1~$8$?FH<+$NH!?t$r=q$$$F(B, 
$B$J$k$Y$/J,Jl(B, $BJ,;R$,Bg$-$/$J$i$J$$$h$&$KG[N8$9$k$3$H$b$7$P$7$PI,MW$H$J$k(B. 
@item
$BJ,?t$rBeF~$9$k>l9g$bF1MM$G$"$k(B. 
@item
@code{subst}$B$N0z?t(B@var{rat}$B$,%j%9%H(B,$BG[Ns(B,$B9TNs(B,$B$"$k$$$OJ,;6I=8=B?9`<0$G(B
$B$"$C$?>l9g$K$O(B, $B$=$l$>$l$NMWAG$^$?$O78?t$KBP$7$F:F5"E*$K(B@code{subst}$B$r(B
$B9T$&(B.
\E
\BEG
@item
Substitutes rational expressions for specified kernels in a rational
expression.
@item
@t{subst}(@var{r},@var{v1},@var{r1},@var{v2},@var{r2},@dots{})
has the same effect as
@t{subst}(@t{subst}(@var{r},@var{v1},@var{r1}),@var{v2},@var{r2},@dots{}).
@item
Note that repeated substitution is done from left to right successively.
You may get different result by changing the specification order.
@item
Ordinary @code{subst()} performs
substitution at all levels of a scalar algebraic expression creeping
into arguments of function forms recursively.
Function @code{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.)
@item
Since @b{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.
@item
The same applies to substitution by rational numbers.
\E
@end itemize

@example
[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
@end example

\JP @node diff,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node diff,,, Polynomials and rational expressions
@subsection @code{diff}
@findex diff

@table @t
@item diff(@var{rat}[,@var{varn}]*)
@item diff(@var{rat},@var{varlist})
\JP :: @var{rat} $B$r(B @var{varn} $B$"$k$$$O(B @var{varlist} $B$NCf$NJQ?t$G=g<!HyJ,$9$k(B.
\BEG
:: Differentiate @var{rat} successively by @var{var}'s for the first
form, or by variables in @var{varlist} for the second form.
\E
@end table

@table @var
@item return
\JP $B<0(B
\EG expression
@item rat
\JP $BM-M}<0(B ($B=iEyH!?t$r4^$s$G$b$h$$(B)
\EG rational expression which contains elementary functions.
@item varn
\JP $BITDj85(B
\EG indeterminate
@item varlist
\JP $BITDj85$N%j%9%H(B
\EG list of indeterminates
@end table

@itemize @bullet
\BJP
@item
$BM?$($i$l$?=iEyH!?t$r(B @var{varn} $B$"$k$$$O(B @var{varlist} $B$NCf$NJQ?t$G(B
$B=g<!HyJ,$9$k(B. 
@item
$B:8B&$NITDj85$h$j(B, $B=g$KHyJ,$7$F$$$/(B. $B$D$^$j(B, @t{diff}(@var{rat},@t{x,y}) $B$O(B, 
@t{diff}(@t{diff}(@var{rat},@t{x}),@t{y}) $B$HF1$8$G$"$k(B. 
\E
\BEG
@item
Differentiate @var{rat} successively by @var{var}'s for the first
form, or by variables in @var{varlist} for the second form.
@item
differentiation is performed by the specified indeterminates (variables)
from left to right.
@t{diff}(@var{rat},@t{x,y}) is the same as
@t{diff}(@t{diff}(@var{rat},@t{x}),@t{y}).
\E
@end itemize

@example
[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)
@end example

\JP @node ediff,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node ediff,,, Polynomials and rational expressions
@subsection @code{ediff}
@findex ediff

@table @t
@item ediff(@var{poly}[,@var{varn}]*)
@item ediff(@var{poly},@var{varlist})
\JP :: @var{poly} $B$r(B @var{varn} $B$"$k$$$O(B @var{varlist} $B$NCf$NJQ?t$G=g<!%*%$%i!<HyJ,$9$k(B.
\BEG
:: Differentiate @var{poly} successively by Euler operators of @var{var}'s for the first
form, or by Euler operators of variables in @var{varlist} for the second form.
\E
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly
\JP $BB?9`<0(B
\EG polynomial
@item varn
\JP $BITDj85(B
\EG indeterminate
@item varlist
\JP $BITDj85$N%j%9%H(B
\EG list of indeterminates
@end table

@itemize @bullet
\BJP
@item
$B:8B&$NITDj85$h$j(B, $B=g$K%*%$%i!<HyJ,$7$F$$$/(B. $B$D$^$j(B, @t{ediff}(@var{poly},@t{x,y}) $B$O(B, 
@t{ediff}(@t{ediff}(@var{poly},@t{x}),@t{y}) $B$HF1$8$G$"$k(B. 
\E
\BEG
@item
differentiation is performed by the specified indeterminates (variables)
from left to right.
@t{ediff}(@var{poly},@t{x,y}) is the same as
@t{ediff}(@t{ediff}(@var{poly},@t{x}),@t{y}).
\E
@end itemize

@example
[0] ediff((x+2*y)^2,x);  
2*x^2+4*y*x
[1] ediff((x+2*y)^2,x,y);
4*y*x
@end example

\JP @node res,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node res,,, Polynomials and rational expressions
@subsection @code{res}
@findex res

@table @t
@item res(@var{var},@var{poly1},@var{poly2}[,@var{mod}])
\JP :: @var{var} $B$K4X$9$k(B @var{poly1} $B$H(B @var{poly2} $B$N=*7k<0(B. 
\EG :: Resultant of @var{poly1} and @var{poly2} with respect to @var{var}.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item var
\JP $BITDj85(B
\EG indeterminate
@item poly1 poly2
\JP $BB?9`<0(B
\EG polynomial
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
$BFs$D$NB?9`<0(B @var{poly1} $B$H(B @var{poly2} $B$N(B, $BJQ?t(B @var{var} $B$K4X$9$k(B
$B=*7k<0$r5a$a$k(B. 
@item
$BItJ,=*7k<0%"%k%4%j%:%`$K$h$k(B. 
@item
$B0z?t(B @var{mod} $B$,$"$k;~(B, GF(@var{mod}) $B>e$G$N7W;;$r9T$&(B. 
\E
\BEG
@item
Resultant of two polynomials @var{poly1} and @var{poly2}
with respect to @var{var}.
@item
Sub-resultant algorithm is used to compute the resultant.
@item
The computation is done over GF(@var{mod}) if @var{mod} is specified.
\E
@end itemize

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

\JP @node fctr sqfr,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node fctr sqfr,,, Polynomials and rational expressions
@subsection @code{fctr}, @code{sqfr}
@findex fctr
@findex sqfr

@table @t
@item fctr(@var{poly})
\JP :: @var{poly} $B$r4{Ls0x;R$KJ,2r$9$k(B. 
\EG :: Factorize polynomial @var{poly} over the rationals.
@item sqfr(@var{poly})
\JP :: @var{poly} $B$rL5J?J}J,2r$9$k(B. 
\EG :: Gets a square-free factorization of polynomial @var{poly}.
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BM-M}?t78?t$NB?9`<0(B
\EG polynomial with rational coefficients
@end table

@itemize @bullet
\BJP
@item
$BM-M}?t78?t$NB?9`<0(B @var{poly} $B$r0x?tJ,2r$9$k(B. @code{fctr()} $B$O4{Ls0x;RJ,2r(B, 
@code{sqfr()} $B$OL5J?J}0x;RJ,2r(B. 
@item
$B7k2L$O(B [[@b{$B?t78?t(B},1],[@b{$B0x;R(B},@b{$B=EJ#EY(B}],...] $B$J$k%j%9%H(B. 
@item
@b{$B?t78?t(B} $B$H(B $BA4$F$N(B @b{$B0x;R(B}^@b{$B=EJ#EY(B} $B$N@Q$,(B @var{poly} $B$HEy$7$$(B. 
@item
@b{$B?t78?t(B} $B$O(B, (@var{poly}/@b{$B?t78?t(B}) $B$,(B, $B@0?t78?t$G(B, $B78?t$N(B GCD $B$,(B 1 $B$H$J$k(B
$B$h$&$JB?9`<0$K$J$k$h$&$KA*$P$l$F$$$k(B. (@code{ptozp()} $B;2>H(B)
\E
\BEG
@item
Factorizes polynomial @var{poly} over the rationals.
@code{fctr()} for irreducible factorization;
@code{sqfr()} for square-free factorization.
@item
The result is represented by a list, whose elements are a pair
represented as

[[@b{num},1],[@b{factor},@b{multiplicity}],...].
@item
Products of all @b{factor}^@b{multiplicity} and @b{num} is equal to
@var{poly}.
@item
The number @b{num} is determined so that (@var{poly}/@b{num}) is an
integral polynomial and its content (GCD of all coefficients) is 1.
(@xref{ptozp}.)
\E
@end itemize

@example
[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]]
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{ufctrhint}.
@end table

\JP @node ufctrhint,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node ufctrhint,,, Polynomials and rational expressions
@subsection @code{ufctrhint}
@findex ufctrhint

@table @t
@item ufctrhint(@var{poly},@var{hint})
\JP :: $B<!?t>pJs$rMQ$$$?(B 1 $BJQ?tB?9`<0$N0x?tJ,2r(B
\BEG
:: Factorizes uni-variate polynomial @var{poly} over the rational number
field when the degrees of its factors are known to be some integer
multiples of @var{hint}.
\E
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $BM-M}?t78?t$N(B 1 $BJQ?tB?9`<0(B
\EG uni-variate polynomial with rational coefficients
@item hint
\JP $B<+A3?t(B
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
$B3F4{Ls0x;R$N<!?t$,(B @var{hint} $B$NG\?t$G$"$k$3$H$,$o$+$C$F$$$k>l9g$K(B
@var{poly} $B$N4{Ls0x;RJ,2r$r(B @code{fctr()} $B$h$j8zN(NI$/9T$&(B. 
@var{poly} $B$,(B, @var{d} $B<!$N3HBgBN>e$K$*$1$k(B
$B$"$kB?9`<0$N%N%k%`(B (@ref{$BBe?tE*?t$K4X$9$k1i;;(B}) $B$GL5J?J}$G$"$k>l9g(B, 
$B3F4{Ls0x;R$N<!?t$O(B @var{d} $B$NG\?t$H$J$k(B. $B$3$N$h$&$J>l9g$K(B
$BMQ$$$i$l$k(B. 
\E
\BEG
@item
By any reason, if the degree of all the irreducible factors of @var{poly}
is known to be some multiples of @var{hint}, factors can be computed
more efficiently by the knowledge than @code{fctr()}.
@item
When @var{hint} is 1, @code{ufctrhint()} is the same as @code{fctr()} for
uni-variate polynomials.
An typical application where @code{ufctrhint()} is effective:
Consider the case where @var{poly} is a norm (@ref{Algebraic numbers})
of a certain polynomial over an extension field with its extension
degree @var{d}, and it is square free;  Then, every irreducible factor
has a degree that is a multiple of @var{d}.
\E
@end itemize

@example
[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
@end example

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

\JP @node modfctr,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node modfctr,,, Polynomials and rational expressions
@subsection @code{modfctr}
@findex modfctr

@table @t
@item modfctr(@var{poly},@var{mod})
\JP :: $BM-8BBN>e$G$NB?9`<0$N0x?tJ,2r(B
\EG :: Factorizer over small finite fields
@end table

@table @var
@item return
\JP $B%j%9%H(B
\EG list
@item poly
\JP $B@0?t78?t$NB?9`<0(B
\EG Polynomial with integer coefficients
@item mod
\JP $B<+A3?t(B
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
2^29 $BL$K~$N<+A3?t(B @var{mod} $B$rI8?t$H$9$kAGBN>e$GB?9`<0(B
@var{poly} $B$r4{Ls0x;R$KJ,2r$9$k(B. 
@item
$B7k2L$O(B [[@b{$B?t78?t(B},1],[@b{$B0x;R(B},@b{$B=EJ#EY(B}],...] $B$J$k%j%9%H(B. 
@item
@b{$B?t78?t(B} $B$H(B $BA4$F$N(B @b{$B0x;R(B}^@b{$B=EJ#EY(B} $B$N@Q$,(B @var{poly} $B$HEy$7$$(B. 
@item
$BBg$-$J0L?t$r;}$DM-8BBN>e$N0x?tJ,2r$K$O(B @code{fctr_ff} $B$rMQ$$$k(B. 
(@ref{$BM-8BBN$K4X$9$k1i;;(B},@pxref{fctr_ff}).
\E
\BEG
@item
This function factorizes a polynomial @var{poly} over
the finite prime field of characteristic @var{mod}, where
@var{mod} must be smaller than 2^29.
@item
The result is represented by a list, whose elements are a pair
represented as

[[@b{num},1],[@b{factor},@b{multiplicity}],...].
@item
Products of all @b{factor}^@b{multiplicity} and @b{num} is equal to
@var{poly}.
@item
To factorize polynomials over large finite fields, use
@code{fctr_ff} (@pxref{Finite fields},@ref{fctr_ff}).
\E
@end itemize

@example
[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]]
@end example

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

\JP @node ptozp,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node ptozp,,, Polynomials and rational expressions
@subsection @code{ptozp}
@findex ptozp

@table @t
@item ptozp(@var{poly})
\JP :: @var{poly} $B$rM-M}?tG\$7$F@0?t78?tB?9`<0$K$9$k(B. 
\BEG
:: Converts a polynomial @var{poly} with rational coefficients into
an integral polynomial such that GCD of all its coefficients is 1.
\E
@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
\BJP
@item
$BM?$($i$l$?B?9`<0(B @var{poly} $B$KE,Ev$JM-M}?t$r3]$1$F(B, $B@0?t78?t$+$D(B
$B78?t$N(B GCD $B$,(B 1 $B$K$J$k$h$&$K$9$k(B. 
@item
$BJ,?t$N;MB'1i;;$O(B, $B@0?t$N1i;;$KHf3S$7$FCY$$$?$a(B, $B<o!9$NB?9`<01i;;(B
$B$NA0$K(B, $BB?9`<0$r@0?t78?t$K$7$F$*$/$3$H$,K>$^$7$$(B. 
@item
$BM-M}<0$rLsJ,$9$k(B @code{red()} $B$GJ,?t78?tM-M}<0$rLsJ,$7$F$b(B, 
$BJ,;RB?9`<0$N78?t$OM-M}?t$N$^$^$G$"$j(B, $BM-M}<0$NJ,;R$r5a$a$k(B
@code{nm()} $B$G$O(B, $BJ,?t78?tB?9`<0$O(B, $BJ,?t78?t$N$^$^$N7A$G=PNO$5$l$k$?$a(B, 
$BD>$A$K@0?t78?tB?9`<0$rF@$k;v$O=PMh$J$$(B. 
@item $B%*%W%7%g%s(B factor $B$,@_Dj$5$l$?>l9g$NLa$jCM$O%j%9%H(B [g,c] $B$G$"$k(B.
$B$3$3$G(B c $B$OM-M}?t$G$"$j(B, g $B$,%*%W%7%g%s$N$J$$>l9g$NLa$jCM$G$"$j(B,
 @var{poly} = c*g $B$H$J$k(B.
\E
\BEG
@item 
Converts the given polynomial by multiplying some rational number
into an integral polynomial such that GCD of all its coefficients is 1.
@item 
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.
@item 
Function @code{red} does not convert rational coefficients of the
numerator.
You cannot obtain an integral polynomial by direct use of the function
@code{nm()}.  The function @code{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.
@item When the option factor is set, the return value is a list [g,c].
Here, c is a rational number, g is an integral polynomial 
and @var{poly} = c*g holds.
\E
@end itemize

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

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{nm dn}.
@end table

\JP @node prim cont,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node prim cont,,, Polynomials and rational expressions
@subsection @code{prim}, @code{cont}
@findex prim

@table @t
@item prim(@var{poly}[,@var{v}])
\JP :: @var{poly} $B$N86;OE*ItJ,(B (primitive part). 
\EG :: Primitive part of @var{poly}.
@item cont(@var{poly}[,@var{v}])
\JP :: @var{poly} $B$NMFNL(B (content). 
\EG :: Content of @var{poly}.
@end table

@table @var
@item return poly
\JP $BM-M}?t78?tB?9`<0(B
\EG polynomial over the rationals
@item v
\JP $BITDj85(B
\EG indeterminate
@end table

@itemize @bullet
\BJP
@item
@var{poly} $B$N<gJQ?t(B ($B0z?t(B @var{v} $B$,$"$k>l9g$K$O(B @var{v}) 
$B$K4X$9$k86;OE*ItJ,(B, $BMFNL$r5a$a$k(B. 
\E
\BEG
@item 
The primitive part and the content of a polynomial @var{poly}
with respect to its main variable (@var{v} if specified).
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{var}, @fref{ord}.
@end table

\JP @node gcd gcdz,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node gcd gcdz,,, Polynomials and rational expressions
@subsection @code{gcd}, @code{gcdz}
@findex gcd

@table @t
@item gcd(@var{poly1},@var{poly2}[,@var{mod}])
@item gcdz(@var{poly1},@var{poly2})
\JP :: @var{poly1} $B$H(B @var{poly2} $B$N(B gcd. 
\EG :: The polynomial greatest common divisor of @var{poly1} and @var{poly2}.
@end table

@table @var
@item return
\JP $BB?9`<0(B
\EG polynomial
@item poly1 poly2
\JP $BB?9`<0(B
\EG polynomial
@item mod
\JP $BAG?t(B
\EG prime
@end table

@itemize @bullet
\BJP
@item
$BFs$D$NB?9`<0$N:GBg8xLs<0(B (GCD) $B$r5a$a$k(B. 
@item
@code{gcd()} $B$OM-M}?tBN>e$NB?9`<0$H$7$F$N(B GCD $B$rJV$9(B. 
$B$9$J$o$A(B, $B7k2L$O@0?t78?t$G(B, $B$+$D78?t$N(B GCD
$B$,(B 1 $B$K$J$k$h$&$JB?9`<0(B, $B$^$?$O(B, $B8_$$$KAG$N>l9g$O(B 1 $B$rJV$9(B.
@item
@code{gcdz()} $B$O(B @var{poly1}, @var{poly2} $B$H$b$K@0?t78?t$N>l9g$K(B, 
$B@0?t4D>e$NB?9`<0$H$7$F$N(B GCD $B$rJV$9(B.
$B$9$J$o$A(B, @code{gcd()} $B$NCM$K(B, $B78?tA4BN$N@0?t(B GCD$B$NCM$r3]$1$?$b$N$rJV$9(B. 
@item
$B0z?t(B @var{mod} $B$,$"$k;~(B, @code{gcd()} $B$O(B GF(@var{mod}) $B>e$G$N(B GCD $B$rJV$9(B. 
@item
@code{gcd()}, @code{gcdz()} Extended Zassenhaus $B%"%k%4%j%:%`$K$h$k(B. 
$BM-8BBN>e$N(B GCD $B$O(B PRS $B%"%k%4%j%:%`$K$h$C$F$$$k$?$a(B, $BBg$-$JLdBj(B, 
GCD $B$,(B 1 $B$N>l9g$J$I$K$*$$$F8zN($,0-$$(B. 
\E
\BEG
@item 
Functions @code{gcd()} and @code{gcdz()} return the greatest common divisor
(GCD) of the given two polynomials.
@item 
Function @code{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.
@item 
Function @code{gcdz()} works for arguments of integral polynomials,
and returns a polynomial GCD over the integer ring, that is,
it returns @code{gcd()} multiplied by the contents of all coefficients
of the two input polynomials.
@item 
@code{gcd()} computes the GCD over GF(@var{mod}) if @var{mod} is specified.
@item 
Polynomial GCD is computed by an improved algorithm based
on Extended Zassenhaus algorithm.
@item 
GCD over a finite field is computed by PRS algorithm and it may not be
efficient for large inputs and co-prime inputs.
\E
@end itemize

@example
[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
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{igcd igcdcntl}.
@end table

\JP @node red,,, $BB?9`<0$*$h$SM-M}<0$N1i;;(B
\EG @node red,,, Polynomials and rational expressions
@subsection @code{red}
@findex red

@table @t
@item red(@var{rat})
\JP :: @var{rat} $B$rLsJ,$7$?$b$N(B. 
\EG :: Reduced form of @var{rat} by canceling common divisors.
@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
\BJP
@item
@b{Asir} $B$OM-M}?t$NLsJ,$r>o$K<+F0E*$K9T$&(B. 
$B$7$+$7(B, $BM-M}<0$K$D$$$F$ODLJ,$O9T$&$,(B, 
$BLsJ,$O%f!<%6!<$,;XDj$7$J$$8B$j9T$o$J$$(B. 
$B$3$NLsJ,$r9T$&%3%^%s%I$,(B @t{red} $B$G$"$k(B. 
@item
EZGCD $B$K$h$j(B @var{rat} $B$NJ,;R(B, $BJ,Jl$rLsJ,$9$k(B. 
@item
$B=PNO$5$l$kM-M}<0$NJ,Jl$NB?9`<0$O(B, $B3F78?t$N(B GCD $B$,(B 1 $B$N(B
$B@0?t78?tB?9`<0$G$"$k(B. 
$BJ,;R$K$D$$$F$O@0?t78?tB?9`<0$H$J$k$H$O8B$i$J$$(B. 
@item
GCD $B$OBgJQ=E$$1i;;$J$N$G(B, $BB>$NJ}K!$G=|$1$k6&DL0x;R$O2DG=$J8B$j=|$/$N$,(B
$BK>$^$7$$(B. $B$^$?(B, $BJ,Jl(B, $BJ,;R$,Bg$-$/$J$C$F$+$i$N$3$NH!?t$N8F$S=P$7$O(B, 
$BHs>o$K;~4V$,3]$+$k>l9g$,B?$$(B. $BM-M}<01i;;$r9T$&>l9g$O(B, $B$"$kDxEY(B
$BIQHK$K(B, $BLsJ,$r9T$&I,MW$,$"$k(B. 
\E
\BEG
@item 
@b{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 @t{red()} to perform this cancellation.
@item 
Cancel the common divisors of the numerator and the denominator of
a rational expression @var{rat} by computing their GCD.
@item 
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.
@item 
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.
\E
@end itemize

@example
[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)
@end example

@table @t
\JP @item $B;2>H(B
\EG @item References
@fref{nm dn}, @fref{gcd gcdz}, @fref{ptozp}.
@end table