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: K.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: K
Univariate Polynomial Ring in x over Integer Ring (using NTL)
- class sage.rings.polynomial.polynomial_integer_dense_ntl.Polynomial_integer_dense_ntl#
Bases:
sage.rings.polynomial.polynomial_element.Polynomial
A dense polynomial over the integers, implemented via NTL.
- content()#
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: 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
- degree(gen=None)#
Return the degree of this polynomial. The zero polynomial has degree -1.
EXAMPLES:
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
- discriminant(proof=True)#
Return the discriminant of self, which is by definition
\[(-1)^{m(m-1)/2} {\mbox{\tt 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: f = ntl.ZZX([1,2,0,3]) sage: f.discriminant() -339 sage: f.discriminant(proof=False) -339
- factor()#
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: 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
- factor_mod(p)#
Return the factorization of self modulo the prime p.
INPUT:
p
– prime
OUTPUT: factorization of self reduced modulo p.
EXAMPLES:
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
- factor_padic(p, prec=10)#
Return \(p\)-adic factorization of self to given precision.
INPUT:
p
– primeprec
– integer; the precision
OUTPUT:
factorization of
self
over the completion at \(p\).
EXAMPLES:
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))
A more difficult example:
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
- gcd(right)#
Return the GCD of self and right. The leading coefficient need not be 1.
EXAMPLES:
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
- lcm(right)#
Return the LCM of self and right.
EXAMPLES:
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
- list(copy=True)#
Return a new copy of the list of the underlying elements of
self
.EXAMPLES:
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() []
- quo_rem(right)#
Attempts 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: 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)
- real_root_intervals()#
Returns isolating intervals for the real roots of this polynomial.
EXAMPLES: We compute the roots of the characteristic polynomial of some Salem numbers:
sage: R.<x> = PolynomialRing(ZZ, implementation='NTL') sage: f = 1 - x^2 - x^3 - x^4 + x^6 sage: f.real_root_intervals() [((1/2, 3/4), 1), ((1, 3/2), 1)]
- resultant(other, proof=True)#
Returns 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: 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
- squarefree_decomposition()#
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: 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
- xgcd(right)#
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 returng, u, v
such thatg = s*self + s*right
. But note that this \(g\) may be a multiple of the gcd.If
self
andright
are coprime as polynomials over the rationals, theng
is guaranteed to be the resultant of self and right, as a constant polynomial.EXAMPLES:
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