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.