umul, umul_ff, usquare, usquare_ff, utmul, utmul_ffumul(), 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
set_upkara, set_uptkara, set_upfft,
section kmul, ksquare, ktmul.
Go to the first, previous, next, last section, table of contents.