@comment $OpenXM: OpenXM/src/asir-doc/parts/builtin/upoly.texi,v 1.3 2003/04/19 15:44:59 noro Exp $
\BJP
@node 一変数多項式の演算,,, 組み込み函数
@section 一変数多項式の演算
\E
\BEG
@node Univariate polynomials,,, Built-in Function
@section Univariate polynomials
\E

@menu
* umul umul_ff usquare usquare_ff utmul utmul_ff::
* kmul ksquare ktmul::
* utrunc udecomp ureverse::
* set_upkara set_uptkara set_upfft::
* uinv_as_power_series ureverse_inv_as_power_series::
* udiv urem urembymul urembymul_precomp ugcd::
@end menu

\JP @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, 一変数多項式の演算
\EG @node umul umul_ff usquare usquare_ff utmul utmul_ff,,, Univariate polynomials
@subsection @code{umul}, @code{umul_ff}, @code{usquare}, @code{usquare_ff}, @code{utmul}, @code{utmul_ff}
@findex umul
@findex umul_ff
@findex usquare
@findex usquare_ff
@findex utmul
@findex utmul_ff

@table @t
@item umul(@var{p1},@var{p2}) 
@itemx umul_ff(@var{p1},@var{p2}) 
\JP :: 一変数多項式の高速乗算
\EG :: Fast multiplication of univariate polynomials
@item usquare(@var{p1})
@itemx usquare_ff(@var{p1})
\JP :: 一変数多項式の高速 2 乗算
\EG :: Fast squaring of a univariate polynomial
@item utmul(@var{p1},@var{p2},@var{d}) 
@itemx utmul_ff(@var{p1},@var{p2},@var{d}) 
\JP :: 一変数多項式の高速乗算 (打ち切り次数指定)
\EG :: Fast multiplication of univariate polynomials with truncation
@end table

@table @var
@item return
\JP 一変数多項式
\EG univariate polynomial
@item p1 p2
\JP 一変数多項式
\EG univariate polynomial
@item d
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
一変数多項式の乗算を, 次数に応じて決まるアルゴリズムを用いて
高速に行う. 
@item
@code{umul()}, @code{usquare()}, @code{utmul()} は
係数を整数と見なして, 整数係数の多項式として積を求める. 
係数が有限体 GF(p) の元の場合には, 係数は 0 以上 p 未満の整数と見なされる. 
@item
@code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} は,
係数を有限体の元と見なして, 有限体上の多項式として
積を求める. ただし, 引数の係数が整数の場合, 
整数係数の多項式を返す場合もあるので, これらを呼び出した結果
が有限体係数であることを保証するためには
あらかじめ @code{simp_ff()} で係数を有限体の元に変換しておくとよい. 
@item
@code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} は, 
GF(2^n) 係数の多項式を引数に取れない. 
@item
@code{umul()}, @code{umul_ff()} の結果は @var{p1}, @var{p2} の積, 
@code{usquare()}, @code{usquare_ff()} の結果は @var{p1} の 2 乗, 
@code{utmul()}, @code{utmul_ff()} の結果は @var{p1}, @var{p2} の積
の, @var{d} 次以下の部分となる. 
@item
いずれも, @code{set_upkara()} (@code{utmul}, @code{utmul_ff} については
@code{set_uptkara()}) で返される値以下の次数に対しては通常の筆算
形式の方法, @code{set_upfft()} で返される値以下の次数に対しては Karatsuba
法, それ以上では FFTおよび中国剰余定理が用いられる. すなわち, 
整数に対する FFT ではなく, 十分多くの 1 ワード以内の法 @var{mi} を用意し, 
@var{p1}, @var{p2} の係数を @var{mi} で割った余りとしたものの積を, 
FFT で計算し, 最後に中国剰余定理で合成する. その際, 有限体版の関数に
おいては, 最後に基礎体を表す法で各係数の剰余を計算するが, ここでは
Shoup によるトリック @code{[Shoup]} を用いて高速化してある. 
\E
\BEG
@item
These functions compute products of univariate polynomials
by selecting an appropriate algorithm depending on the degrees
of inputs.
@item
@code{umul()}, @code{usquare()}, @code{utmul()} 
compute products over the integers.
Coefficients in GF(p) are regarded as non-negative integers
less than p.
@item
@code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()}
compute products over a finite field. However, if some of
the coefficients of the inputs are integral,
the result may be an integral polynomial. So if one wants
to assure that the result is a polynomial over the finite field,
apply @code{simp_ff()} to the inputs.
@item
@code{umul_ff()}, @code{usquare_ff()}, @code{utmul_ff()} 
cannot take polynomials over GF(2^n) as their inputs.
@item
@code{umul()}, @code{umul_ff()} produce @var{p1*p2}.
@code{usquare()}, @code{usquare_ff()} produce @var{p1^2}.
@code{utmul()}, @code{utmul_ff()} produce @var{p1*p2 mod} @var{v}^(@var{d}+1),
where @var{v} is the variable of @var{p1}, @var{p2}.
@item
If the degrees of the inputs are less than or equal to the
value returned by @code{set_upkara()} (@code{set_uptkara()} for
@code{utmul}, @code{utmul_ff}), usual pencil and paper method is
used. If the degrees of the inputs are less than or equall to 
the value returned by @code{set_upfft()}, Karatsuba algorithm
is used. If the degrees of the inputs exceed it, a combination
of FFT and Chinese remainder theorem is used.
First of all sufficiently many primes @var{mi} 
within 1 machine word are prepared.
Then @var{p1*p2 mod mi} is computed by FFT for each @var{mi}.
Finally they are combined by Chinese remainder theorem.
The functions over finite fields use an improvement by V. Shoup @code{[Shoup]}.
\E
@end itemize

@example
[176] load("fff")$
[177] cputime(1)$
0sec(1.407e-05sec)
[178] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
0sec(0.00028sec)
[179] A=randpoly_ff(100,x)$
0sec(0.001422sec)
[180] B=randpoly_ff(100,x)$
0sec(0.00107sec)
[181] for(I=0;I<100;I++)A*B;
7.77sec + gc : 8.38sec(16.15sec)
[182] for(I=0;I<100;I++)umul(A,B);
2.24sec + gc : 1.52sec(3.767sec)
[183] for(I=0;I<100;I++)umul_ff(A,B);
1.42sec + gc : 0.24sec(1.653sec)
[184] for(I=0;I<100;I++)usquare_ff(A);  
1.08sec + gc : 0.21sec(1.297sec)
[185] for(I=0;I<100;I++)utmul_ff(A,B,100);
1.2sec + gc : 0.17sec(1.366sec)
[186] deg(utmul_ff(A,B,100),x);
100
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{set_upkara set_uptkara set_upfft},
@fref{kmul ksquare ktmul}.
@end table

\JP @node kmul ksquare ktmul,,, 一変数多項式の演算
\EG @node kmul ksquare ktmul,,, Univariate polynomials
@subsection @code{kmul}, @code{ksquare}, @code{ktmul}
@findex kmul
@findex ksquare
@findex ktmul

@table @t
@item kmul(@var{p1},@var{p2}) 
\JP :: 一変数多項式の高速乗算
\EG :: Fast multiplication of univariate polynomials
@item ksquare(@var{p1})
\JP :: 一変数多項式の高速 2 乗算
\EG :: Fast squaring of a univariate polynomial
@item ktmul(@var{p1},@var{p2},@var{d}) 
\JP :: 一変数多項式の高速乗算 (打ち切り次数指定)
\EG :: Fast multiplication of univariate polynomials with truncation
@end table

@table @var
@item return
\JP 一変数多項式
\EG univariate polynomial
@item p1 p2
\JP 一変数多項式
\EG univariate polynomial
@item d
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
一変数多項式の乗算を Karatsuba 法で行う. 
@item
基本的には @code{umul} と同様だが, 次数が大きくなっても
FFT を用いた高速化は行わない. 
@item
GF(2^n) 係数の多項式にも用いることができる. 
\E
\BEG
These functions compute products of univariate polynomials by Karatsuba
algorithm.
@item
These functions do not apply FFT for large degree inputs.
@item
These functions can compute products over GF(2^n).
\E
@end itemize

@example
[0] load("code/fff");
1
[34] setmod_ff(defpoly_mod2(160));
x^160+x^5+x^3+x^2+1
[35] A=randpoly_ff(100,x)$
[36] B=randpoly_ff(100,x)$
[37] umul(A,B)$
umul : invalid argument
return to toplevel
[37] kmul(A,B)$
@end example

\JP @node set_upkara set_uptkara set_upfft,,, 一変数多項式の演算
\EG @node set_upkara set_uptkara set_upfft,,, Univariate polynomials
@subsection @code{set_upkara}, @code{set_uptkara}, @code{set_upfft}
@findex set_upkara
@findex set_uptkara
@findex set_upfft

@table @t
@item set_upkara([@var{threshold}])
@itemx set_uptkara([@var{threshold}])
@itemx set_upfft([@var{threshold}])
\JP :: 1 変数多項式の積演算における N^2 , Karatsuba, FFT アルゴリズムの切替えの閾値
\BEG
:: Set thresholds in the selection of an algorithm from N^2, Karatsuba,
FFT algorithms for univariate polynomial multiplication.
\E
@end table

@table @var
@item return
\JP 設定されている値
\EG value currently set
@item threshold
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
いずれも, 一変数多項式の積の計算における, アルゴリズム切替えの閾値を
設定する. 
@item
一変数多項式の積は, 次数 N が小さい範囲では通常の N^2 アルゴリズム, 中程度
の場合 Karatsuba アルゴリズム, 大きい場合には FFT アルゴリズムで計算
される. この切替えの次数を設定する. 
@item
詳細は, それぞれの積関数の項を参照のこと. 
\E
\BEG
@item
These functions set thresholds in the selection of an algorithm from N^2, 
Karatsuba, FFT algorithms for univariate polynomial multiplication.
@item
Products of univariate polynomials are computed by N^2, Karatsuba,
FFT algorithms. The algorithm selection is done according to the degrees of
input polynomials and the thresholds.
@item
See the description of each function for details.
\E
@end itemize

@table @t
\JP @item 参照
\EG @item References
@fref{kmul ksquare ktmul},
@fref{umul umul_ff usquare usquare_ff utmul utmul_ff}.
@end table

\JP @node utrunc udecomp ureverse,,, 一変数多項式の演算
\EG @node utrunc udecomp ureverse,,, Univariate polynomials
@subsection @code{utrunc}, @code{udecomp}, @code{ureverse}
@findex utrunc
@findex udecomp
@findex ureverse

@table @t
@item utrunc(@var{p},@var{d}) 
@itemx udecomp(@var{p},@var{d}) 
@itemx ureverse(@var{p})
\JP :: 多項式に対する操作
\EG :: Operations on polynomials
@end table

@table @var
@item return
\JP 一変数多項式あるいは一変数多項式のリスト
\EG univariate polynomial or list of univariate polynomials
@item p
\JP 一変数多項式
\EG univariate polynomial
@item d
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
@var{p} の変数を x とする. このとき @var{p} = @var{p1}+x^(@var{d}+1)@var{p2}
(@var{p1} の次数は @var{d} 以下) と分解できる. @code{utrunc()} は
@var{p1} を返し, @code{udecomp()} は [@var{p1},@var{p2}] を返す. 
@item
@var{p} の次数を @var{e} とし, @var{i} 次の係数を @var{p}[@var{i}] とすれば, 
@code{ureverse()} は @var{p}[@var{e}]+@var{p}[@var{e}-1]x+... を返す. 
\E
\BEG
@item
Let @var{x} be the variable of @var{p}. Then @var{p} can be decomposed
as @var{p} = @var{p1}+x^(@var{d}+1)@var{p2}, where the degree of @var{p1} 
is less than or equal to @var{d}.
Under the decomposition, @code{utrunc()} returns 
@var{p1} and  @code{udecomp()} returns [@var{p1},@var{p2}].
@item
Let @var{e} be the degree of @var{p} and @var{p}[@var{i}] the coefficient
of @var{p} at degree @var{i}. Then 
@code{ureverse()} returns @var{p}[@var{e}]+@var{p}[@var{e}-1]x+....
\E
@end itemize

@example
[132] utrunc((x+1)^10,5);
252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
[133] udecomp((x+1)^10,5);
[252*x^5+210*x^4+120*x^3+45*x^2+10*x+1,x^4+10*x^3+45*x^2+120*x+210]
[134] ureverse(3*x^3+x^2+2*x);
2*x^2+x+3
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{udiv urem urembymul urembymul_precomp ugcd}.
@end table

\JP @node uinv_as_power_series ureverse_inv_as_power_series,,, 一変数多項式の演算
\EG @node uinv_as_power_series ureverse_inv_as_power_series,,, Univariate polynomials
@subsection @code{uinv_as_power_series}, @code{ureverse_inv_as_power_series}
@findex uinv_as_power_series
@findex ureverse_inv_as_power_series

@table @t
@item uinv_as_power_series(@var{p},@var{d}) 
@itemx ureverse_inv_as_power_series(@var{p},@var{d})
\JP :: 多項式を冪級数とみて, 逆元計算
\EG :: Computes the truncated inverse as a power series.
@end table

@table @var
@item return
\JP 一変数多項式
\EG univariate polynomial
@item p
\JP 一変数多項式
\EG univariate polynomial
@item d
\JP 非負整数
\EG non-negative integer
@end table

@itemize @bullet
\BJP
@item
@code{uinv_as_power_series(@var{p},@var{d})} は, 定数項が 0 でない
多項式 @var{p} に対し, @var{p}@var{r}-1 の最低次数が @var{d}+1
以上になるような 高々 @var{d} 次の多項式 @var{r} を求める. 
@item
@code{ureverse_inv_as_power_series(@var{p},@var{d})} は
@var{p} の次数を @var{e} とするとき, @var{p1}=@code{ureverse(@var{p},@var{e})}
に対して @code{uinv_as_power_series(@var{p1},@var{d})} を計算する. 
@item
@code{rembymul_precomp()} の引数として用いる場合, @code{ureverse_inv_as_power_series()} の結果をそのまま用いることができる. 
\E
\BEG
@item
For a polynomial @var{p} with a non zero constant term,
@code{uinv_as_power_series(@var{p},@var{d})} computes
a polynomial @var{r} whose degree is at most @var{d}
such that @var{p*r = 1 mod} x^(@var{d}+1), where @var{x} is the variable
of @var{p}.
@item
Let @var{e} be the degree of @var{p}.
@code{ureverse_inv_as_power_series(@var{p},@var{d})} computes
@code{uinv_as_power_series(@var{p1},@var{d})} for
@var{p1}=@code{ureverse(@var{p},@var{e})}.
@item
The output of @code{ureverse_inv_as_power_series()} can be used
as the input of @code{rembymul_precomp()}.
\E
@end itemize

@example
[123] A=(x+1)^5;                 
x^5+5*x^4+10*x^3+10*x^2+5*x+1
[124] uinv_as_power_series(A,5); 
-126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
[126] A*R;
-126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
[127] A=x^10+x^9;
x^10+x^9
[128] R=ureverse_inv_as_power_series(A,5);
-x^5+x^4-x^3+x^2-x+1
[129] ureverse(A)*R;
-x^6+1
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{utrunc udecomp ureverse},
@fref{udiv urem urembymul urembymul_precomp ugcd}.
@end table

\JP @node udiv urem urembymul urembymul_precomp ugcd,,, 一変数多項式の演算
\EG @node udiv urem urembymul urembymul_precomp ugcd,,, Univariate polynomials
@subsection @code{udiv}, @code{urem}, @code{urembymul}, @code{urembymul_precomp}, @code{ugcd}
@findex udiv
@findex urem
@findex urembymul
@findex urembymul_precomp
@findex ugcd

@table @t
@item udiv(@var{p1},@var{p2}) 
@item urem(@var{p1},@var{p2}) 
@item urembymul(@var{p1},@var{p2}) 
@item urembymul_precomp(@var{p1},@var{p2},@var{inv}) 
@item ugcd(@var{p1},@var{p2}) 
\JP :: 一変数多項式の除算, GCD
\EG :: Division and GCD for univariate polynomials.
@end table

@table @var
@item return
\JP 一変数多項式
\EG univariate polynomial
@item p1 p2 inv
\JP 一変数多項式
\EG univariate polynomial
@end table

@itemize @bullet
\BJP
@item
一変数多項式 @var{p1}, @var{p2} に対し, 
@code{udiv} は商, @code{urem}, @code{urembymul} は剰余, 
@code{ugcd} は GCD を返す. 
これらは, 密な一変数多項式に対する高速化を図ったものである. 
@code{urembymul} は, @var{p2} による剰余計算を, @var{p2} の
冪級数としての逆元計算および, 乗算 2 回に置き換えたもので, 
次数が大きい場合に有効である. 
@item
@code{urembymul_precomp} は, 固定された多項式による剰余
計算を多数行う場合などに効果を発揮する. 
第 3 引数は, あらかじめ @code{ureverse_inv_as_power_series()} に
より計算しておく. 
\E
\BEG
@item
For univariate polynomials @var{p1} and @var{p2},
there exist polynomials @var{q} and @var{r} such that
@var{p1=q*p2+r} and the degree of @var{r} is less than that of @var{p2}.
Then @code{udiv} returns @var{q}, @code{urem} and @code{urembymul} return
@var{r}. @code{ugcd} returns the polynomial GCD of @var{p1} and @var{p2}.
These functions are specially tuned up for dense univariate polynomials.
In @code{urembymul} the division by @var{p2} is replaced with 
the inverse computation of @var{p2} as a power series and
two polynomial multiplications. It speeds up the computation
when the degrees of inputs are large.
@item
@code{urembymul_precomp} is efficient when one repeats divisions
by a fixed polynomial.
One has to compute the third argument by @code{ureverse_inv_as_power_series()}.
\E
@end itemize

@example
[177] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
[178] A=randpoly_ff(200,x)$
[179] B=randpoly_ff(101,x)$
[180] cputime(1)$
0sec(1.597e-05sec)
[181] srem(A,B)$
0.15sec + gc : 0.15sec(0.3035sec)
[182] urem(A,B)$
0.11sec + gc : 0.12sec(0.2347sec)
[183] urembymul(A,B)$          
0.08sec + gc : 0.09sec(0.1651sec)
[184] R=ureverse_inv_as_power_series(B,101)$
0.04sec + gc : 0.03sec(0.063sec)
[185] urembymul_precomp(A,B,R)$             
0.03sec(0.02501sec)
@end example

@table @t
\JP @item 参照
\EG @item References
@fref{uinv_as_power_series ureverse_inv_as_power_series}.
@end table