6.4 Univariate polynomials

6.4.1 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 equal 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

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

6.4.2 kmul, ksquare, ktmul

kmul(p1,p2)

:: Fast multiplication of univariate polynomials

ksquare(p1)

:: Fast squaring of a univariate polynomial

ktmul(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 Karatsuba algorithm.
• These functions do not apply FFT for large degree inputs.
• These functions can compute products over GF(2^n).

[0] load("code/fff");
1
[34] setmod_ff(defpoly_mod2(160));
x^160+x^5+x^3+x^2+1
[35] A=randpoly_ff(100,x)$
[36] B=randpoly_ff(100,x)$
[37] umul(A,B)$
umul : invalid argument
return to toplevel
[37] kmul(A,B)$

6.4.3 set_upkara, set_uptkara, set_upfft

set_upkara([threshold])

set_uptkara([threshold])

set_upfft([threshold])

:: Set thresholds in the selection of an algorithm from N^2, Karatsuba, FFT algorithms for univariate polynomial multiplication.

return

value currently set

threshold

non-negative integer

• These functions set thresholds in the selection of an algorithm from N^2, Karatsuba, FFT algorithms for univariate polynomial multiplication.
• Products of univariate polynomials are computed by N^2, Karatsuba, FFT algorithms. The algorithm selection is done according to the degrees of input polynomials and the thresholds.
• See the description of each function for details.

References

kmul, ksquare, ktmul, umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff.

6.4.4 utrunc, udecomp, ureverse

utrunc(p,d)

udecomp(p,d)

ureverse(p)

:: Operations on polynomials

return

univariate polynomial or list of univariate polynomials

p

univariate polynomial

d

non-negative integer

• Let x be the variable of p. Then p can be decomposed as p = p1+x^(d+1)p2, where the degree of p1 is less than or equal to d. Under the decomposition, utrunc() returns p1 and udecomp() returns [p1,p2].
• Let e be the degree of p and p[i] the coefficient of p at degree i. Then ureverse() returns p[e]+p[e-1]x+....

[132] utrunc((x+1)^10,5);
252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
[133] udecomp((x+1)^10,5);
[252*x^5+210*x^4+120*x^3+45*x^2+10*x+1,x^4+10*x^3+45*x^2+120*x+210]
[134] ureverse(3*x^3+x^2+2*x);
2*x^2+x+3

References

udiv, urem, urembymul, urembymul_precomp, ugcd.

6.4.5 uinv_as_power_series, ureverse_inv_as_power_series

uinv_as_power_series(p,d)

ureverse_inv_as_power_series(p,d)

:: Computes the truncated inverse as a power series.

return

univariate polynomial

p

univariate polynomial

d

non-negative integer

• For a polynomial p with a non zero constant term, uinv_as_power_series(p,d) computes a polynomial r whose degree is at most d such that p*r = 1 mod x^(d+1), where x is the variable of p.
• Let e be the degree of p. ureverse_inv_as_power_series(p,d) computes uinv_as_power_series(p1,d) for p1=ureverse(p,e).
• The output of ureverse_inv_as_power_series() can be used as the input of rembymul_precomp().

[123] A=(x+1)^5;                 
x^5+5*x^4+10*x^3+10*x^2+5*x+1
[124] uinv_as_power_series(A,5); 
-126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
[126] A*R;
-126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
[127] A=x^10+x^9;
x^10+x^9
[128] R=ureverse_inv_as_power_series(A,5);
-x^5+x^4-x^3+x^2-x+1
[129] ureverse(A)*R;
-x^6+1

References

utrunc, udecomp, ureverse, udiv, urem, urembymul, urembymul_precomp, ugcd.

6.4.6 udiv, urem, urembymul, urembymul_precomp, ugcd

udiv(p1,p2)

urem(p1,p2)

urembymul(p1,p2)

urembymul_precomp(p1,p2,inv)

ugcd(p1,p2)

:: Division and GCD for univariate polynomials.

return

univariate polynomial

p1 p2 inv

univariate polynomial

• For univariate polynomials p1 and p2, there exist polynomials q and r such that p1=q*p2+r and the degree of r is less than that of p2. Then udiv returns q, urem and urembymul return r. ugcd returns the polynomial GCD of p1 and p2. These functions are specially tuned up for dense univariate polynomials. In urembymul the division by p2 is replaced with the inverse computation of p2 as a power series and two polynomial multiplications. It speeds up the computation when the degrees of inputs are large.
• urembymul_precomp is efficient when one repeats divisions by a fixed polynomial. One has to compute the third argument by ureverse_inv_as_power_series().

[177] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
[178] A=randpoly_ff(200,x)$
[179] B=randpoly_ff(101,x)$
[180] cputime(1)$
0sec(1.597e-05sec)
[181] srem(A,B)$
0.15sec + gc : 0.15sec(0.3035sec)
[182] urem(A,B)$
0.11sec + gc : 0.12sec(0.2347sec)
[183] urembymul(A,B)$          
0.08sec + gc : 0.09sec(0.1651sec)
[184] R=ureverse_inv_as_power_series(B,101)$
0.04sec + gc : 0.03sec(0.063sec)
[185] urembymul_precomp(A,B,R)$             
0.03sec(0.02501sec)

References

uinv_as_power_series, ureverse_inv_as_power_series.

This document was generated on December 22, 2024 using texi2html 5.0.