umul
, umul_ff
, usquare
, usquare_ff
, utmul
, utmul_ff
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.
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
set_upkara
, set_uptkara
, set_upfft
,
section kmul
, ksquare
, ktmul
.
Go to the first, previous, next, last section, table of contents.