kmul, ksquare, ktmul

kmul(p1,p2)

:: 一変数多項式の高速乗算

ksquare(p1)

:: 一変数多項式の高速 2 乗算

ktmul(p1,p2,d)

:: 一変数多項式の高速乗算 (打ち切り次数指定)

return

一変数多項式

p1 p2

一変数多項式

d

非負整数

• 一変数多項式の乗算を Karatsuba 法で行う.
• 基本的には umul と同様だが, 次数が大きくなっても FFT を用いた高速化は行わない.
• GF(2^n) 係数の多項式にも用いることができる.

[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)$

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