Dense univariate polynomials over \(\ZZ\), implemented using FLINT#
AUTHORS:
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
David Harvey: split off from polynomial_element_generic.py (2007-09)
Burcin Erocal: rewrote to use FLINT (2008-06-16)
- class sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint#
Bases:
Polynomial
A dense polynomial over the integers, implemented via FLINT.
- _add_(right)#
Return
self
plusright
.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: f = 2*x + 1 sage: g = -3*x^2 + 6 sage: f + g -3*x^2 + 2*x + 7
- _sub_(right)#
Return
self
minusright
.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: f = 2*x + 1 sage: g = -3*x^2 + 6 sage: f - g 3*x^2 + 2*x - 5
- _lmul_(right)#
Return
self
multiplied byright
, whereright
is a scalar (integer).EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: x*3 3*x sage: (2*x^2 + 4)*3 6*x^2 + 12
- _rmul_(right)#
Return
self
multiplied byright
, where right is a scalar (integer).EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: 3*x 3*x sage: 3*(2*x^2 + 4) 6*x^2 + 12
- _mul_(right)#
Return
self
multiplied byright
.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: (x - 2)*(x^2 - 8*x + 16) x^3 - 10*x^2 + 32*x - 32
- _mul_trunc_(right, n)#
Truncated multiplication
See also
_mul_()
for standard multiplicationEXAMPLES:
sage: x = polygen(ZZ) sage: p1 = 1 + x + x^2 + x^4 sage: p2 = -2 + 3*x^2 + 5*x^4 sage: p1._mul_trunc_(p2, 4) 3*x^3 + x^2 - 2*x - 2 sage: (p1*p2).truncate(4) 3*x^3 + x^2 - 2*x - 2 sage: p1._mul_trunc_(p2, 6) 5*x^5 + 6*x^4 + 3*x^3 + x^2 - 2*x - 2
- 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) 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) sage: x.degree() 1 sage: (x^2).degree() 2 sage: R(1).degree() 0 sage: R(0).degree() -1
- disc(proof=True)#
Return the discriminant of
self
, which is by definition\[(-1)^{m(m-1)/2} \mathop{\mathrm{resultant}}(a, a')/\mathop{\mathrm{lc}}(a),\]where \(m = \mathop{\mathrm{deg}}(a)\), and \(\mathop{\mathrm{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: R.<x> = ZZ[] sage: f = 3*x^3 + 2*x + 1 sage: f.discriminant() -339 sage: f.discriminant(proof=False) -339
- discriminant(proof=True)#
Return the discriminant of
self
, which is by definition\[(-1)^{m(m-1)/2} \mathop{\mathrm{resultant}}(a, a')/\mathop{\mathrm{lc}}(a),\]where \(m = \mathop{\mathrm{deg}}(a)\), and \(\mathop{\mathrm{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: R.<x> = ZZ[] sage: f = 3*x^3 + 2*x + 1 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> = ZZ['x'] 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) 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
andright
. The leading coefficient need not be 1.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) 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
- inverse_series_trunc(prec)#
Return a polynomial approximation of precision
prec
of the inverse series of this polynomial.EXAMPLES:
sage: x = polygen(ZZ) sage: p = 1 + x + 2*x^2 sage: q5 = p.inverse_series_trunc(5) sage: q5 -x^4 + 3*x^3 - x^2 - x + 1 sage: p*q5 -2*x^6 + 5*x^5 + 1 sage: (x-1).inverse_series_trunc(5) -x^4 - x^3 - x^2 - x - 1 sage: q100 = p.inverse_series_trunc(100) sage: (q100 * p).truncate(100) 1
- is_one()#
Return
True
ifself
is equal to one.EXAMPLES:
sage: R.<x> = ZZ[] sage: R(0).is_one() False sage: R(1).is_one() True sage: x.is_one() False
- is_zero()#
Return
True
ifself
is equal to zero.EXAMPLES:
sage: R.<x> = ZZ[] sage: R(0).is_zero() True sage: R(1).is_zero() False sage: x.is_zero() False
- lcm(right)#
Return the LCM of
self
andright
.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) 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').0 sage: f = x^3 + 3*x - 17 sage: f.list() [-17, 3, 0, 1] sage: f = PolynomialRing(ZZ,'x')(0) sage: f.list() []
- pseudo_divrem(B)#
Write
A = self
. This function computes polynomials \(Q\) and \(R\) and an integer \(d\) such that\[\mathop{\mathrm{lead}}(B)^d A = B Q + R\]where R has degree less than that of B.
INPUT:
B
– a polynomial over \(\ZZ\)
OUTPUT:
Q
,R
– polynomialsd
– nonnegative integer
EXAMPLES:
sage: R.<x> = ZZ['x'] sage: A = R(range(10)) sage: B = 3*R([-1, 0, 1]) sage: Q, R, d = A.pseudo_divrem(B) sage: Q, R, d (9*x^7 + 8*x^6 + 16*x^5 + 14*x^4 + 21*x^3 + 18*x^2 + 24*x + 20, 75*x + 60, 1) sage: B.leading_coefficient()^d * A == B*Q + R True
- quo_rem(right)#
Attempts to divide
self
byright
, and return a quotient and remainder.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) 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: f = x^2 sage: f.quo_rem(0) Traceback (most recent call last): ... ZeroDivisionError: 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) (0, x^2)
- real_root_intervals()#
Return 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) 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)]
- resultant(other, proof=True)#
Return the resultant of
self
andother
, which must lie in the same polynomial ring.If
proof=False
(the default isproof=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').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
- reverse(degree=None)#
Return a polynomial with the coefficients of this polynomial reversed.
If an optional degree argument is given the coefficient list will be truncated or zero padded as necessary before computing the reverse.
EXAMPLES:
sage: R.<x> = ZZ[] sage: p = R([1,2,3,4]); p 4*x^3 + 3*x^2 + 2*x + 1 sage: p.reverse() x^3 + 2*x^2 + 3*x + 4 sage: p.reverse(degree=6) x^6 + 2*x^5 + 3*x^4 + 4*x^3 sage: p.reverse(degree=2) x^2 + 2*x + 3
- revert_series(n)#
Return a polynomial \(f\) such that \(f(\)
self
\((x)) =\)self
\((f(x)) = x\) (mod \(x^n\)).EXAMPLES:
sage: R.<t> = ZZ[] sage: f = t - t^3 + t^5 sage: f.revert_series(6) 2*t^5 + t^3 + t sage: f.revert_series(-1) Traceback (most recent call last): ... ValueError: argument n must be a non-negative integer, got -1 sage: g = - t^3 + t^5 sage: g.revert_series(6) Traceback (most recent call last): ... ValueError: self must have constant coefficient 0 and a unit for coefficient t^1
- squarefree_decomposition()#
Return the square-free decomposition of
self
. This is a partial factorization ofself
into square-free, relatively prime polynomials.This is a wrapper for the NTL function
SquareFreeDecomp
.EXAMPLES:
sage: R.<x> = PolynomialRing(ZZ) sage: p = (x-1)^2 * (x-2)^2 * (x-3)^3 * (x-4) sage: p.squarefree_decomposition() (x - 4) * (x^2 - 3*x + 2)^2 * (x - 3)^3 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)#
Return a triple \((g,s,t)\) such that \(g = s\cdot{}\)
self
+ \(t\cdot{}\)right
and such that \(g\) is the gcd ofself
andright
up to a divisor of the resultant ofself
andother
.As integer polynomials do not form a principal ideal domain, it is not always possible given \(a\) and \(b\) to find a pair \(s,t\) such that \(gcd(a,b) = sa + tb\). Take \(a=x+2\) and \(b=x+4\) as an example for which the gcd is \(1\) but the best you can achieve in the Bezout identity is \(2\).
If
self
andright
are coprime as polynomials over the rationals, theng
is guaranteed to be the resultant ofself
andright
, as a constant polynomial.EXAMPLES:
sage: P.<x> = PolynomialRing(ZZ) sage: (x + 2).xgcd(x + 4) (2, -1, 1) sage: (x + 2).resultant(x + 4) 2 sage: (x + 2).gcd(x + 4) 1 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: zero = P(0) sage: x.xgcd(zero) (x, 1, 0) sage: zero.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