`umul', `umul_ff', `usquare', `usquare_ff', `utmul', `utmul_ff'
---------------------------------------------------------------

umul(P1,P2)
umul_ff(P1,P2)
     :: 一変数多項式の高速乗算

usquare(P1)
usquare_ff(P1)
     :: 一変数多項式の高速 2 乗算

utmul(P1,P2,D)
utmul_ff(P1,P2,D)
     :: 一変数多項式の高速乗算 (打ち切り次数指定)

RETURN
     一変数多項式

P1 P2
     一変数多項式

D
     非負整数

   * 一変数多項式の乗算を, 次数に応じて決まるアルゴリズムを用いて
     高速に行う.

   * `umul()', `usquare()', `utmul()' は 係数を整数と見なして,
     整数係数の多項式として積を求める.  係数が有限体 GF(p)
     の元の場合には, 係数は 0 以上 p 未満の整数と見なされる.

   * `umul_ff()', `usquare_ff()', `utmul_ff()' は,
     係数を有限体の元と見なして, 有限体上の多項式として 積を求める.
     ただし, 引数の係数が整数の場合,
     整数係数の多項式を返す場合もあるので, これらを呼び出した結果
     が有限体係数であることを保証するためには あらかじめ `simp_ff()'
     で係数を有限体の元に変換しておくとよい.

   * `umul_ff()', `usquare_ff()', `utmul_ff()' は, GF(2^n)
     係数の多項式を引数に取れない.

   * `umul()', `umul_ff()' の結果は P1, P2 の積, `usquare()',
     `usquare_ff()' の結果は P1 の 2 乗, `utmul()', `utmul_ff()'
     の結果は P1, P2 の積 の, D 次以下の部分となる.

   * いずれも, `set_upkara()' (`utmul', `utmul_ff' については
     `set_uptkara()') で返される値以下の次数に対しては通常の筆算
     形式の方法, `set_upfft()' で返される値以下の次数に対しては
     Karatsuba 法, それ以上では FFTおよび中国剰余定理が用いられる.
     すなわち, 整数に対する FFT ではなく, 十分多くの 1 ワード以内の法
     MI を用意し, P1, P2 の係数を MI で割った余りとしたものの積を, FFT
     で計算し, 最後に中国剰余定理で合成する. その際, 有限体版の関数に
     おいては, 最後に基礎体を表す法で各係数の剰余を計算するが, ここでは
     Shoup によるトリック `[Shoup]' を用いて高速化してある.

     [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

参照
     *Note `set_upkara set_uptkara set_upfft': set_upkara set_uptkara
     set_upfft, *Note `kmul ksquare ktmul': kmul ksquare ktmul.

