`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
     *Note `set_upkara set_uptkara set_upfft': set_upkara set_uptkara
     set_upfft, *Note `kmul ksquare ktmul': kmul ksquare ktmul.

