[ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

## 6.4 Univariate polynomials

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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 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

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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
[37] kmul(A,B)\$
```

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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

 [ << ] [ < ] [ Up ] [ > ] [ >> ]

This document was generated on April 22, 2021 using texi2html 5.0.