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.

>>> from flint import ctx
>>> 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)¶

complex_roots(self)¶: This method is not implemented for polynomials in \((\mathbb{Z}/N\mathbb{Z})[X]\)

compose(self, other)¶

Returns the composition of two polynomials

To be precise about the order of composition, given self, and other by \(f(x)\), \(g(x)\), returns \(f(g(x))\).

>>> f = nmod_poly([1,2,3], 163)
>>> g = nmod_poly([0,0,1], 163)
>>> f.compose(g)
3*x^4 + 2*x^2 + 1
>>> g.compose(f)
9*x^4 + 12*x^3 + 10*x^2 + 4*x + 1

compose_mod(self, other, modulus)¶

Returns the composition of two polynomials modulo a third.

To be precise about the order of composition, given self, and other and modulus by \(f(x)\), \(g(x)\) and \(h(x)\), returns \(f(g(x)) \mod h(x)\). We require that \(h(x)\) is non-zero.

>>> f = nmod_poly([1,2,3,4,5], 163)
>>> g = nmod_poly([3,2,1], 163)
>>> h = nmod_poly([1,0,1,0,1], 163)
>>> f.compose_mod(g, h)
63*x^3 + 100*x^2 + 17*x + 63
>>> g.compose_mod(f, h)
147*x^3 + 159*x^2 + 4*x + 7

deflation(self)¶

degree(self) → long¶

derivative(self)¶

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)])

factor_squarefree(self)¶

Factors self into square-free polynomials. Returns (c, factors) where c is the leading coefficient and factors is a list of (poly, exp).

>>> x = nmod_poly([0, 1], 7)
>>> p = x**2 * (x/2 - 1)**2 * (x + 1)**3
>>> p
2*x^7 + 5*x^6 + 4*x^5 + 2*x^4 + 2*x^3 + x^2
>>> p.factor_squarefree()
(2, [(x^2 + 5*x, 2), (x + 1, 3)])
>>> p.factor()
(2, [(x, 2), (x + 5, 2), (x + 1, 3)])

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

integral(self)¶

inverse_series_trunc(self, slong n)¶

Returns the inverse of self modulo \(x^n\). Assumes the leading coefficient of the polynomial is invertible.

>>> f = nmod_poly([123, 129, 63, 14, 51, 76, 133], 163)
>>> f.inverse_series_trunc(3)
159*x^2 + 151*x + 110
>>> f.inverse_series_trunc(4)
23*x^3 + 159*x^2 + 151*x + 110
>>> f.inverse_series_trunc(5)
45*x^4 + 23*x^3 + 159*x^2 + 151*x + 110

is_constant(self)¶

Returns True if this is a constant polynomial.

>>> nmod_poly([0, 1], 3).is_constant()
False
>>> nmod_poly([1], 3).is_constant()
True

is_gen(self)¶

Returns True if this polynomial is equal to the generator x.

>>> x = nmod_poly([0, 1], 3)
>>> x
x
>>> x.is_gen()
True
>>> (2*x).is_gen()
False

is_one(self)¶: Returns True if this polynomial is equal to 1.

is_zero(self)¶: Returns True if this is the zero polynomial.

leading_coefficient(self)¶

Return the leading coefficient of this polynomial.

>>> f = nmod_poly([123, 129, 63, 14, 51, 76, 133], 163)
>>> f.leading_coefficient()
133

left_shift(self, slong n)¶

Returns self shifted left by n coefficients by inserting zero coefficients. This is equivalent to multiplying the polynomial by x^n

>>> f = nmod_poly([1,2,3], 99991)
>>> f.left_shift(0)
3*x^2 + 2*x + 1
>>> f.left_shift(1)
3*x^3 + 2*x^2 + x
>>> f.left_shift(4)
3*x^6 + 2*x^5 + x^4

length(self) → long¶

modulus(self) → mp_limb_t¶

pow_mod(self, e, modulus, mod_rev_inv=None)¶

Returns self raised to the power e modulo modulus: \(f^e \mod g\)/

mod_rev_inv is the inverse of the reverse of the modulus, precomputing it and passing it to pow_mod() can optimise powering of polynomials with large exponents.

>>> x = nmod_poly([0,1], 163)
>>> f = 30*x**6 + 104*x**5 + 76*x**4 + 33*x**3 + 70*x**2 + 44*x + 65
>>> g = 43*x**6 + 91*x**5 + 77*x**4 + 113*x**3 + 71*x**2 + 132*x + 60
>>> mod = x**4 + 93*x**3 + 78*x**2 + 72*x + 149
>>>
>>> f.pow_mod(123, mod)
3*x^3 + 25*x^2 + 115*x + 161
>>> f.pow_mod(2**64, mod)
52*x^3 + 96*x^2 + 136*x + 9
>>> mod_rev_inv = mod.reverse().inverse_series_trunc(4)
>>> f.pow_mod(2**64, mod, mod_rev_inv)
52*x^3 + 96*x^2 + 136*x + 9

real_roots(self)¶: This method is not implemented for polynomials in \((\mathbb{Z}/N\mathbb{Z})[X]\)

repr(self)¶

resultant(self, other)¶

Returns the resultant of self and other.

>>> f = nmod_poly([1, 2, 3], 3)
>>> g = nmod_poly([1, 0, 1], 3)
>>> f.resultant(f)
0
>>> f.resultant(g)
2

reverse(self, degree=None)¶

Return a polynomial with the coefficients of this polynomial reversed.

If degree is not None, the output polynomial will be zero-padded or truncated before being reversed. NOTE: degree must be non-negative.

>>> f = nmod_poly([1,2,3,4,5], 163)
>>> f.reverse()
x^4 + 2*x^3 + 3*x^2 + 4*x + 5
>>> f.reverse(degree=1)
x + 2
>>> f.reverse(degree=100)
x^100 + 2*x^99 + 3*x^98 + 4*x^97 + 5*x^96

right_shift(self, slong n)¶

Returns self shifted right by n coefficients. This is equivalent to the floor division of the polynomial by x^n

>>> f = nmod_poly([1,2,3], 99991)
>>> f.right_shift(0)
3*x^2 + 2*x + 1
>>> f.right_shift(1)
3*x + 2
>>> f.right_shift(4)
0

roots(self)¶

Computes all the roots in the base ring of the polynomial. Returns a list of all pairs (v, m) where v is the integer root and m is the multiplicity of the root.

To compute complex roots of a polynomial, instead use the .complex_roots() method, which is available on certain polynomial rings.

>>> from flint import fmpz_poly
>>> fmpz_poly([1, 2]).roots()
[]
>>> fmpz_poly([2, 1]).roots()
[(-2, 1)]
>>> fmpz_poly([12, 7, 1]).roots()
[(-3, 1), (-4, 1)]
>>> (fmpz_poly([-5,1]) * fmpz_poly([-5,1]) * fmpz_poly([-3,1])).roots()
[(3, 1), (5, 2)]

sqrt(self)¶: Return exact square root or None.

str(self, bool ascending=False, var='x', *args, **kwargs)¶

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.

truncate(self, slong n)¶

Notionally truncate the polynomial to have length n. If n is larger than the length of the input, then a copy of self is returned. If n is not positive, then the zero polynomial is returned.

Effectively returns this polynomial \(\mod x^n\).

>>> f = nmod_poly([1,2,3], 65537)
>>> f.truncate(3) == f
True
>>> f.truncate(2)
2*x + 1
>>> f.truncate(1)
1
>>> f.truncate(0)
0
>>> f.truncate(-1)
0

xgcd(self, other)¶