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]`.

    [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.