umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff

umul(p1,p2)

umul_ff(p1,p2)

:: Fast multiplication of univariate polynomials

usquare(p1)

usquare_ff(p1)

:: Fast squaring of a univariate polynomial

utmul(p1,p2,d)

utmul_ff(p1,p2,d)

:: Fast multiplication of univariate polynomials with truncation

return

univariate polynomial

p1 p2

univariate polynomial

d

non-negative integer

• These functions compute products of univariate polynomials by selecting an appropriate algorithm depending on the degrees of inputs.
• umul(), usquare(), utmul() compute products over the integers. Coefficients in GF(p) are regarded as non-negative integers less than p.
• umul_ff(), usquare_ff(), utmul_ff() compute products over a finite field. However, if some of the coefficients of the inputs are integral, the result may be an integral polynomial. So if one wants to assure that the result is a polynomial over the finite field, apply simp_ff() to the inputs.
• umul_ff(), usquare_ff(), utmul_ff() cannot take polynomials over GF(2^n) as their inputs.
• umul(), umul_ff() produce p1*p2. usquare(), usquare_ff() produce p1^2. utmul(), utmul_ff() produce p1*p2 mod v^(d+1), where v is the variable of p1, p2.
• If the degrees of the inputs are less than or equal to the value returned by set_upkara() (set_uptkara() for utmul, utmul_ff), usual pencil and paper method is used. If the degrees of the inputs are less than or equall to the value returned by set_upfft(), Karatsuba algorithm is used. If the degrees of the inputs exceed it, a combination of FFT and Chinese remainder theorem is used. First of all sufficiently many primes mi within 1 machine word are prepared. Then p1*p2 mod mi is computed by FFT for each mi. Finally they are combined by Chinese remainder theorem. The functions over finite fields use an improvement by V. 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

References

section set_upkara, set_uptkara, set_upfft, section kmul, ksquare, ktmul.

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