Dense univariate polynomials over \(\ZZ\), implemented using NTL.¶

AUTHORS:

David Harvey: split off from polynomial_element_generic.py (2007-09)
David Harvey: rewrote to talk to NTL directly, instead of via ntl.pyx (2007-09); a lot of this was based on Joel Mohler’s recent rewrite of the NTL wrapper

Sage includes two implementations of dense univariate polynomials over \(\ZZ\); this file contains the implementation based on NTL, but there is also an implementation based on FLINT in sage.rings.polynomial.polynomial_integer_dense_flint.

The FLINT implementation is preferred (FLINT’s arithmetic operations are generally faster), so it is the default; to use the NTL implementation, you can do:

Sage

sage: K.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: K
Univariate Polynomial Ring in x over Integer Ring (using NTL)

Python

>>> from sage.all import *
>>> K = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = K._first_ngens(1)
>>> K
Univariate Polynomial Ring in x over Integer Ring (using NTL)

Sage Live

K.<x> = PolynomialRing(ZZ, implementation='NTL')
K

class sage.rings.polynomial.polynomial_integer_dense_ntl.Polynomial_integer_dense_ntl[source]¶

Bases: Polynomial

A dense polynomial over the integers, implemented via NTL.

content()[source]¶

Return the greatest common divisor of the coefficients of this polynomial. The sign is the sign of the leading coefficient. The content of the zero polynomial is zero.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: (2*x^2 - 4*x^4 + 14*x^7).content()
2
sage: (2*x^2 - 4*x^4 - 14*x^7).content()
-2
sage: x.content()
1
sage: R(1).content()
1
sage: R(0).content()
0

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> (Integer(2)*x**Integer(2) - Integer(4)*x**Integer(4) + Integer(14)*x**Integer(7)).content()
2
>>> (Integer(2)*x**Integer(2) - Integer(4)*x**Integer(4) - Integer(14)*x**Integer(7)).content()
-2
>>> x.content()
1
>>> R(Integer(1)).content()
1
>>> R(Integer(0)).content()
0

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
(2*x^2 - 4*x^4 + 14*x^7).content()
(2*x^2 - 4*x^4 - 14*x^7).content()
x.content()
R(1).content()
R(0).content()

degree(gen=None)[source]¶

Return the degree of this polynomial. The zero polynomial has degree \(-1\).

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: x.degree()
1
sage: (x^2).degree()
2
sage: R(1).degree()
0
sage: R(0).degree()
-1

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> x.degree()
1
>>> (x**Integer(2)).degree()
2
>>> R(Integer(1)).degree()
0
>>> R(Integer(0)).degree()
-1

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
x.degree()
(x^2).degree()
R(1).degree()
R(0).degree()

discriminant(proof=True)[source]¶

Return the discriminant of self, which is by definition

\[(-1)^{m(m-1)/2} \text{resultant}(a, a')/lc(a),\]

where \(m = deg(a)\), and \(lc(a)\) is the leading coefficient of a. If proof is False (the default is True), then this function may use a randomized strategy that errors with probability no more than \(2^{-80}\).

EXAMPLES:

Sage

sage: f = ntl.ZZX([1,2,0,3])
sage: f.discriminant()
-339
sage: f.discriminant(proof=False)
-339

Python

>>> from sage.all import *
>>> f = ntl.ZZX([Integer(1),Integer(2),Integer(0),Integer(3)])
>>> f.discriminant()
-339
>>> f.discriminant(proof=False)
-339

Sage Live

f = ntl.ZZX([1,2,0,3])
f.discriminant()
f.discriminant(proof=False)

factor()[source]¶

This function overrides the generic polynomial factorization to make a somewhat intelligent decision to use PARI or NTL based on some benchmarking.

Note: This function factors the content of the polynomial, which can take very long if it’s a really big integer. If you do not need the content factored, divide it out of your polynomial before calling this function.

EXAMPLES:

Sage

sage: R.<x> = ZZ[]
sage: f = x^4 - 1
sage: f.factor()
(x - 1) * (x + 1) * (x^2 + 1)
sage: f = 1 - x
sage: f.factor()
(-1) * (x - 1)
sage: f.factor().unit()
-1
sage: f = -30*x; f.factor()
(-1) * 2 * 3 * 5 * x

Python

>>> from sage.all import *
>>> R = ZZ['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(4) - Integer(1)
>>> f.factor()
(x - 1) * (x + 1) * (x^2 + 1)
>>> f = Integer(1) - x
>>> f.factor()
(-1) * (x - 1)
>>> f.factor().unit()
-1
>>> f = -Integer(30)*x; f.factor()
(-1) * 2 * 3 * 5 * x

Sage Live

R.<x> = ZZ[]
f = x^4 - 1
f.factor()
f = 1 - x
f.factor()
f.factor().unit()
f = -30*x; f.factor()

factor_mod(p)[source]¶

Return the factorization of self modulo the prime \(p\).

INPUT:

p – prime

OUTPUT: factorization of self reduced modulo \(p\)

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, 'x', implementation='NTL')
sage: f = -3*x*(x-2)*(x-9) + x
sage: f.factor_mod(3)
x
sage: f = -3*x*(x-2)*(x-9)
sage: f.factor_mod(3)
Traceback (most recent call last):
...
ArithmeticError: factorization of 0 is not defined

sage: f = 2*x*(x-2)*(x-9)
sage: f.factor_mod(7)
(2) * x * (x + 5)^2

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, 'x', implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = -Integer(3)*x*(x-Integer(2))*(x-Integer(9)) + x
>>> f.factor_mod(Integer(3))
x
>>> f = -Integer(3)*x*(x-Integer(2))*(x-Integer(9))
>>> f.factor_mod(Integer(3))
Traceback (most recent call last):
...
ArithmeticError: factorization of 0 is not defined

>>> f = Integer(2)*x*(x-Integer(2))*(x-Integer(9))
>>> f.factor_mod(Integer(7))
(2) * x * (x + 5)^2

Sage Live

R.<x> = PolynomialRing(ZZ, 'x', implementation='NTL')
f = -3*x*(x-2)*(x-9) + x
f.factor_mod(3)
f = -3*x*(x-2)*(x-9)
f.factor_mod(3)
f = 2*x*(x-2)*(x-9)
f.factor_mod(7)

factor_padic(p, prec=10)[source]¶

Return \(p\)-adic factorization of self to given precision.

INPUT:

p – prime
prec – integer; the precision

OUTPUT: factorization of self over the completion at \(p\)

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f = x^2 + 1
sage: f.factor_padic(5, 4)
((1 + O(5^4))*x + 2 + 5 + 2*5^2 + 5^3 + O(5^4))
* ((1 + O(5^4))*x + 3 + 3*5 + 2*5^2 + 3*5^3 + O(5^4))

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(2) + Integer(1)
>>> f.factor_padic(Integer(5), Integer(4))
((1 + O(5^4))*x + 2 + 5 + 2*5^2 + 5^3 + O(5^4))
* ((1 + O(5^4))*x + 3 + 3*5 + 2*5^2 + 3*5^3 + O(5^4))

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
f = x^2 + 1
f.factor_padic(5, 4)

A more difficult example:

Sage

sage: f = 100 * (5*x + 1)^2 * (x + 5)^2
sage: f.factor_padic(5, 10)
(4 + O(5^10)) * (5 + O(5^11))^2 * ((1 + O(5^10))*x + 5 + O(5^10))^2
* ((5 + O(5^10))*x + 1 + O(5^10))^2

Python

>>> from sage.all import *
>>> f = Integer(100) * (Integer(5)*x + Integer(1))**Integer(2) * (x + Integer(5))**Integer(2)
>>> f.factor_padic(Integer(5), Integer(10))
(4 + O(5^10)) * (5 + O(5^11))^2 * ((1 + O(5^10))*x + 5 + O(5^10))^2
* ((5 + O(5^10))*x + 1 + O(5^10))^2

Sage Live

f = 100 * (5*x + 1)^2 * (x + 5)^2
f.factor_padic(5, 10)

gcd(right)[source]¶

Return the GCD of self and right. The leading coefficient need not be 1.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f = (6*x + 47) * (7*x^2 - 2*x + 38)
sage: g = (6*x + 47) * (3*x^3 + 2*x + 1)
sage: f.gcd(g)
6*x + 47

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38))
>>> g = (Integer(6)*x + Integer(47)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
>>> f.gcd(g)
6*x + 47

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
f = (6*x + 47) * (7*x^2 - 2*x + 38)
g = (6*x + 47) * (3*x^3 + 2*x + 1)
f.gcd(g)

lcm(right)[source]¶

Return the LCM of self and right.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f = (6*x + 47) * (7*x^2 - 2*x + 38)
sage: g = (6*x + 47) * (3*x^3 + 2*x + 1)
sage: h = f.lcm(g); h
126*x^6 + 951*x^5 + 486*x^4 + 6034*x^3 + 585*x^2 + 3706*x + 1786
sage: h == (6*x + 47) * (7*x^2 - 2*x + 38) * (3*x^3 + 2*x + 1)
True

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38))
>>> g = (Integer(6)*x + Integer(47)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
>>> h = f.lcm(g); h
126*x^6 + 951*x^5 + 486*x^4 + 6034*x^3 + 585*x^2 + 3706*x + 1786
>>> h == (Integer(6)*x + Integer(47)) * (Integer(7)*x**Integer(2) - Integer(2)*x + Integer(38)) * (Integer(3)*x**Integer(3) + Integer(2)*x + Integer(1))
True

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
f = (6*x + 47) * (7*x^2 - 2*x + 38)
g = (6*x + 47) * (3*x^3 + 2*x + 1)
h = f.lcm(g); h
h == (6*x + 47) * (7*x^2 - 2*x + 38) * (3*x^3 + 2*x + 1)

list(copy=True)[source]¶

Return a new copy of the list of the underlying elements of self.

EXAMPLES:

Sage

sage: x = PolynomialRing(ZZ, 'x', implementation='NTL').0
sage: f = x^3 + 3*x - 17
sage: f.list()
[-17, 3, 0, 1]
sage: f = PolynomialRing(ZZ, 'x', implementation='NTL')(0)
sage: f.list()
[]

Python

>>> from sage.all import *
>>> x = PolynomialRing(ZZ, 'x', implementation='NTL').gen(0)
>>> f = x**Integer(3) + Integer(3)*x - Integer(17)
>>> f.list()
[-17, 3, 0, 1]
>>> f = PolynomialRing(ZZ, 'x', implementation='NTL')(Integer(0))
>>> f.list()
[]

Sage Live

x = PolynomialRing(ZZ, 'x', implementation='NTL').0
f = x^3 + 3*x - 17
f.list()
f = PolynomialRing(ZZ, 'x', implementation='NTL')(0)
f.list()

quo_rem(right)[source]¶

Attempt to divide self by right, and return a quotient and remainder.

If right is monic, then it returns (q, r) where self = q * right + r and deg(r) < deg(right).

If right is not monic, then it returns \((q, 0)\) where q = self/right if right exactly divides self, otherwise it raises an exception.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f = R(range(10)); g = R([-1, 0, 1])
sage: q, r = f.quo_rem(g)
sage: q, r
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 25*x + 20)
sage: q*g + r == f
True

sage: 0//(2*x)
0

sage: f = x^2
sage: f.quo_rem(0)
Traceback (most recent call last):
...
ArithmeticError: division by zero polynomial

sage: f = (x^2 + 3) * (2*x - 1)
sage: f.quo_rem(2*x - 1)
(x^2 + 3, 0)

sage: f = x^2
sage: f.quo_rem(2*x - 1)
Traceback (most recent call last):
...
ArithmeticError: division not exact in Z[x] (consider coercing to Q[x] first)

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = R(range(Integer(10))); g = R([-Integer(1), Integer(0), Integer(1)])
>>> q, r = f.quo_rem(g)
>>> q, r
(9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 25*x + 20)
>>> q*g + r == f
True

>>> Integer(0)//(Integer(2)*x)
0

>>> f = x**Integer(2)
>>> f.quo_rem(Integer(0))
Traceback (most recent call last):
...
ArithmeticError: division by zero polynomial

>>> f = (x**Integer(2) + Integer(3)) * (Integer(2)*x - Integer(1))
>>> f.quo_rem(Integer(2)*x - Integer(1))
(x^2 + 3, 0)

>>> f = x**Integer(2)
>>> f.quo_rem(Integer(2)*x - Integer(1))
Traceback (most recent call last):
...
ArithmeticError: division not exact in Z[x] (consider coercing to Q[x] first)

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
f = R(range(10)); g = R([-1, 0, 1])
q, r = f.quo_rem(g)
q, r
q*g + r == f
0//(2*x)
f = x^2
f.quo_rem(0)
f = (x^2 + 3) * (2*x - 1)
f.quo_rem(2*x - 1)
f = x^2
f.quo_rem(2*x - 1)

real_root_intervals()[source]¶

Return isolating intervals for the real roots of this polynomial.

EXAMPLES: We compute the roots of the characteristic polynomial of some Salem numbers:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: f = 1 - x^2 - x^3 - x^4 + x^6
sage: f.real_root_intervals()                                               # needs sage.libs.linbox
[((1/2, 3/4), 1), ((1, 3/2), 1)]

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = Integer(1) - x**Integer(2) - x**Integer(3) - x**Integer(4) + x**Integer(6)
>>> f.real_root_intervals()                                               # needs sage.libs.linbox
[((1/2, 3/4), 1), ((1, 3/2), 1)]

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
f = 1 - x^2 - x^3 - x^4 + x^6
f.real_root_intervals()                                               # needs sage.libs.linbox

resultant(other, proof=True)[source]¶

Return the resultant of self and other, which must lie in the same polynomial ring.

If proof=False (the default is proof=True), then this function may use a randomized strategy that errors with probability no more than \(2^{-80}\).

INPUT:

other – a polynomial

OUTPUT: an element of the base ring of the polynomial ring

EXAMPLES:

Sage

sage: x = PolynomialRing(ZZ, 'x', implementation='NTL').0
sage: f = x^3 + x + 1;  g = x^3 - x - 1
sage: r = f.resultant(g); r
-8
sage: r.parent() is ZZ
True

Python

>>> from sage.all import *
>>> x = PolynomialRing(ZZ, 'x', implementation='NTL').gen(0)
>>> f = x**Integer(3) + x + Integer(1);  g = x**Integer(3) - x - Integer(1)
>>> r = f.resultant(g); r
-8
>>> r.parent() is ZZ
True

Sage Live

x = PolynomialRing(ZZ, 'x', implementation='NTL').0
f = x^3 + x + 1;  g = x^3 - x - 1
r = f.resultant(g); r
r.parent() is ZZ

squarefree_decomposition()[source]¶

Return the square-free decomposition of self. This is a partial factorization of self into square-free, relatively prime polynomials.

This is a wrapper for the NTL function SquareFreeDecomp.

EXAMPLES:

Sage

sage: R.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: p = 37 * (x-1)^2 * (x-2)^2 * (x-3)^3 * (x-4)
sage: p.squarefree_decomposition()
(37) * (x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3

Python

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> p = Integer(37) * (x-Integer(1))**Integer(2) * (x-Integer(2))**Integer(2) * (x-Integer(3))**Integer(3) * (x-Integer(4))
>>> p.squarefree_decomposition()
(37) * (x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3

Sage Live

R.<x> = PolynomialRing(ZZ, implementation='NTL')
p = 37 * (x-1)^2 * (x-2)^2 * (x-3)^3 * (x-4)
p.squarefree_decomposition()

xgcd(right)[source]¶

This function can’t in general return \((g,s,t)\) as above, since they need not exist. Instead, over the integers, we first multiply \(g\) by a divisor of the resultant of \(a/g\) and \(b/g\), up to sign, and return g, u, v such that g = s*self + s*right. But note that this \(g\) may be a multiple of the gcd.

If self and right are coprime as polynomials over the rationals, then g is guaranteed to be the resultant of self and right, as a constant polynomial.

EXAMPLES:

Sage

sage: P.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(27*x^2 + 54, 1, -x^2 - 3*x - 9)
sage: u*F + v*G
27*x^2 + 54
sage: x.xgcd(P(0))
(x, 1, 0)
sage: f = P(0)
sage: f.xgcd(x)
(x, 0, 1)
sage: F = (x-3)^3; G = (x-15)^2
sage: g, u, v = F.xgcd(G)
sage: g, u, v
(2985984, -432*x + 8208, 432*x^2 + 864*x + 14256)
sage: u*F + v*G
2985984

Python

>>> from sage.all import *
>>> P = PolynomialRing(ZZ, implementation='NTL', names=('x',)); (x,) = P._first_ngens(1)
>>> F = (x**Integer(2) + Integer(2))*x**Integer(3); G = (x**Integer(2)+Integer(2))*(x-Integer(3))
>>> g, u, v = F.xgcd(G)
>>> g, u, v
(27*x^2 + 54, 1, -x^2 - 3*x - 9)
>>> u*F + v*G
27*x^2 + 54
>>> x.xgcd(P(Integer(0)))
(x, 1, 0)
>>> f = P(Integer(0))
>>> f.xgcd(x)
(x, 0, 1)
>>> F = (x-Integer(3))**Integer(3); G = (x-Integer(15))**Integer(2)
>>> g, u, v = F.xgcd(G)
>>> g, u, v
(2985984, -432*x + 8208, 432*x^2 + 864*x + 14256)
>>> u*F + v*G
2985984

Sage Live

P.<x> = PolynomialRing(ZZ, implementation='NTL')
F = (x^2 + 2)*x^3; G = (x^2+2)*(x-3)
g, u, v = F.xgcd(G)
g, u, v
u*F + v*G
x.xgcd(P(0))
f = P(0)
f.xgcd(x)
F = (x-3)^3; G = (x-15)^2
g, u, v = F.xgcd(G)
g, u, v
u*F + v*G