fmpz_poly – polynomials over integers

class flint.fmpz_poly(val=None)

The fmpz_poly type represents dense univariate polynomials over the integers.

>>> fmpz_poly([1,2,3]) ** 3
27*x^6 + 54*x^5 + 63*x^4 + 44*x^3 + 21*x^2 + 6*x + 1
>>> divmod(fmpz_poly([2,0,1,1,6]), fmpz_poly([3,5,7]))
(0, 6*x^4 + x^3 + x^2 + 2)

static chebyshev_t(n)

Returns the Chebyshev polynomial of the first kind \(T_n(x)\) as an fmpz_poly.

>>> fmpz_poly.chebyshev_t(3)
4*x^3 + (-3)*x

static chebyshev_u(n)

Returns the Chebyshev polynomial of the second kind \(U_n(x)\) as an fmpz_poly.

>>> fmpz_poly.chebyshev_u(3)
8*x^3 + (-4)*x

coeffs(self)

static cos_minpoly(ulong n)

Returns the monic polynomial of \(2 \cos(2 \pi / n)\) as an fmpz_poly.

>>> fmpz_poly.cos_minpoly(7)
x^3 + x^2 + (-2)*x + (-1)

static cyclotomic(ulong n)

Returns the cyclotomic polynomial \(\Phi_n(x)\) as an fmpz_poly.

>>> fmpz_poly.cyclotomic(12)
x^4 + (-1)*x^2 + 1

degree(self) → long

factor(self)

Factors self into irreducible factors, returning a tuple (c, factors) where c is the content of the coefficients and factors is a list of (poly, exp) pairs.

>>> (-73 * fmpz_poly([1,2,3]) ** 3 * fmpz_poly([5,6,7,8,9]) ** 8).factor()
(-73, [(3*x^2 + 2*x + 1, 3), (9*x^4 + 8*x^3 + 7*x^2 + 6*x + 5, 8)])
>>> fmpz_poly.chebyshev_t(6).factor()
(1, [(2*x^2 + (-1), 1), (16*x^4 + (-16)*x^2 + 1, 1)])
>>> (fmpz_poly([-1,1])**100).factor()
(1, [(x + (-1), 100)])
>>> fmpz_poly([1,2,3,4,5,6]).factor()
(1, [(6*x^5 + 5*x^4 + 4*x^3 + 3*x^2 + 2*x + 1, 1)])

gcd(self, other)

Returns the greatest common divisor of self and other.

>>> A = fmpz_poly([2,0,1,0,5]); B = fmpz_poly([2,3,4])
>>> (A*B).gcd(B)
4*x^2 + 3*x + 2

static hilbert_class_poly(long D)

Returns the Hilbert class polynomial \(H_D(x)\) as an fmpz_poly.

>>> fmpz_poly.hilbert_class_poly(-3)
x
>>> fmpz_poly.hilbert_class_poly(-4)
x + (-1728)
>>> fmpz_poly.hilbert_class_poly(-59)
x^3 + 30197678080*x^2 + (-140811576541184)*x + 374643194001883136
>>> fmpz_poly.hilbert_class_poly(-5)
Traceback (most recent call last):
  ...
ValueError: D must be an imaginary quadratic discriminant

length(self) → long

repr(self)

roots(self, bool verbose=False)

Computes all the complex roots of this polynomial. Returns a list of pairs (c, m) where c is the root as an acb and m is the multiplicity of the root.

>>> fmpz_poly([]).roots()
[]
>>> fmpz_poly([1]).roots()
[]
>>> fmpz_poly([2,0,1]).roots()
[([1.41421356237310 +/- 4.96e-15]j, 1), ([-1.41421356237310 +/- 4.96e-15]j, 1)]
>>> for c, m in (fmpz_poly([2,3,4]) * fmpz_poly([5,6,7,11])**3).roots():
...     print((c,m))
...
([-0.375000000000000 +/- 1.0e-19] + [0.599478940414090 +/- 5.75e-17]j, 1)
([-0.375000000000000 +/- 1.0e-19] + [-0.599478940414090 +/- 5.75e-17]j, 1)
([-0.735284727404843 +/- 4.11e-16], 3)
([0.0494605455206031 +/- 1.33e-17] + [0.784693167647185 +/- 2.85e-16]j, 3)
([0.0494605455206031 +/- 1.33e-17] + [-0.784693167647185 +/- 2.85e-16]j, 3)

str(self, bool ascending=False)

Convert to a human-readable string (generic implementation for all polynomial types).

If ascending is True, the monomials are output from low degree to high, otherwise from high to low.

static swinnerton_dyer(ulong n, bool use_arb=True)

Returns the Swinnerton-Dyer polynomial \(S_n(x)\) as an fmpz_poly. Warning: the degree is \(2^n\).

>>> fmpz_poly.swinnerton_dyer(0)
x
>>> fmpz_poly.swinnerton_dyer(1)
x^2 + (-2)
>>> fmpz_poly.swinnerton_dyer(2)
x^4 + (-10)*x^2 + 1
>>> fmpz_poly.swinnerton_dyer(3)
x^8 + (-40)*x^6 + 352*x^4 + (-960)*x^2 + 576