Go to the first, previous, next, last section, table of contents.

### `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

`参照`
  section `set_upkara`, `set_uptkara`, `set_upfft`, section `kmul`, `ksquare`, `ktmul`.

Go to the first, previous, next, last section, table of contents.