nmod_poly – polynomials over integers mod n

class flint.nmod_poly(val=None, ulong mod=0)

The nmod_poly type represents dense univariate polynomials over Z/nZ for word-size n.

>>> a = nmod_poly([5,1,10,14,8], 7)
>>> a
x^4 + 3*x^2 + x + 5
>>> -a
6*x^4 + 4*x^2 + 6*x + 2
>>> ctx.pretty = False
>>> list(nmod_poly(list(range(3)), 2))
[nmod(0, 2), nmod(1, 2)]
>>> nmod_poly([1, 2, 3], 23) ** 3
nmod_poly([1, 6, 21, 21, 17, 8, 4], 23)
>>> divmod(nmod_poly([2,0,1,1,6],23), nmod_poly([3,5,7],23))
(nmod_poly([4, 0, 14], 23), nmod_poly([13, 3], 23))
>>> ctx.pretty = True

coeffs(self)

degree(self) → long

factor(self, algorithm=None)

Factors self into irreducible factors, returning a tuple (c, factors) where c is the leading coefficient and factors is a list of (poly, exp) pairs with all polynomials monic.

>>> nmod_poly(list(range(10)), 3).factor()
(2, [(x, 1), (x + 2, 7)])
>>> nmod_poly(list(range(10)), 19).factor()
(9, [(x, 1), (x^4 + 15*x^3 + 2*x^2 + 7*x + 3, 1), (x^4 + 7*x^3 + 12*x^2 + 15*x + 12, 1)])
>>> nmod_poly(list(range(10)), 53).factor()
(9, [(x, 1), (x^8 + 48*x^7 + 42*x^6 + 36*x^5 + 30*x^4 + 24*x^3 + 18*x^2 + 12*x + 6, 1)])

Algorithm can be None (default), ‘berlekamp’, or ‘cantor-zassenhaus’.

>>> nmod_poly([3,2,1,2,3], 7).factor(algorithm='berlekamp')
(3, [(x + 2, 1), (x + 4, 1), (x^2 + 4*x + 1, 1)])
>>> nmod_poly([3,2,1,2,3], 7).factor(algorithm='cantor-zassenhaus')
(3, [(x + 4, 1), (x + 2, 1), (x^2 + 4*x + 1, 1)])

gcd(self, other)

Returns the monic greatest common divisor of self and other.

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

length(self) → long

modulus(self) → mp_limb_t

repr(self)

roots(self, **kwargs)

Isolates the complex roots of self. See acb_poly.roots() for details.

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.