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)
:: 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]`.
``` load("fff")\$
 cputime(1)\$
0sec(1.407e-05sec)
 setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
0sec(0.00028sec)
 A=randpoly_ff(100,x)\$
0sec(0.001422sec)
 B=randpoly_ff(100,x)\$
0sec(0.00107sec)
 for(I=0;I<100;I++)A*B;
7.77sec + gc : 8.38sec(16.15sec)
 for(I=0;I<100;I++)umul(A,B);
2.24sec + gc : 1.52sec(3.767sec)
 for(I=0;I<100;I++)umul_ff(A,B);
1.42sec + gc : 0.24sec(1.653sec)
 for(I=0;I<100;I++)usquare_ff(A);
1.08sec + gc : 0.21sec(1.297sec)
 for(I=0;I<100;I++)utmul_ff(A,B,100);
1.2sec + gc : 0.17sec(1.366sec)
 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.