fmpz_mod_poly – polynomials over integers mod n

class flint.fmpz_mod_poly_ctx(mod)

Context object for creating fmpz_mod_poly initialised with a modulus \(N\).

>>> fmpz_mod_poly_ctx(2**127 - 1)
fmpz_mod_poly_ctx(170141183460469231731687303715884105727)

gen(self)

Return the generator of the polynomial: \(x\)

>>> R = fmpz_mod_poly_ctx(163)
>>> R.gen()
x

is_prime(self)

Return whether the modulus is prime

>>> fmpz_mod_poly_ctx(2**127).is_prime()
False
>>> fmpz_mod_poly_ctx(2**127 - 1).is_prime()
True

minpoly(self, vals)

Returns a minimal generating polynomial for sequence \(vals\).

A minimal generating polynomial is a monic polynomial, of minimal degree \(d\), that annihilates any consecutive \(d+1\) terms in seq.

Assumes that the modulus is prime.

>>> R = fmpz_mod_poly_ctx(163)
>>> R.minpoly([1,1,2,3,5,8])
x^2 + 162*x + 162
>>> R.minpoly([2,4,6,8,10])
x^2 + 161*x + 1

modulus(self)

Return the modulus from the context as an fmpz type

>>> R = fmpz_mod_poly_ctx(2**127 - 1)
>>> R.modulus()
170141183460469231731687303715884105727

one(self)

Return the one element of this polynomial ring

>>> R = fmpz_mod_poly_ctx(163)
>>> R.one()
1

random_element(self, degree=3, monic=False, irreducible=False)

Return a random element of degree degree. If monic is True, ensures the output is monic. If irreducible is True, ensures that the output is irreducible.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R.random_element()
>>> f.degree()
3
>>> f = R.random_element(degree=123)
>>> f.degree()
123
>>> f = R.random_element(monic=True)
>>> f.is_monic()
True
>>> f = R.random_element(degree=13, monic=True, irreducible=True)
>>> f.degree()
13
>>> f.is_monic()
True
>>> f.is_irreducible()
True

zero(self)

Return the zero element of this polynomial ring

>>> R = fmpz_mod_poly_ctx(163)
>>> R.zero()
0

class flint.fmpz_mod_poly(val, ctx)

The fmpz_mod_poly type represents univariate polynomials over integer modulo an arbitrary-size modulus. For wordsize modulus, see nmod_poly.

An fmpz_mod_poly element is constructed from an fmpz_mod_poly_ctx either by passing it as an argument to the type, or by directly calling the context:

>>> fmpz_mod_poly([1,-2,3], fmpz_mod_poly_ctx(2**127 - 1))
3*x^2 + 170141183460469231731687303715884105725*x + 1
>>> R = fmpz_mod_poly_ctx(2**127 - 1)
>>> R([4,5,6])
6*x^2 + 5*x + 4

add_trunc(self, other, slong n)

Truncate self and other to polynomials of length n and return their sum

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> h = R([1,2,3])
>>> f.add_trunc(h, 2)
4*x + 2
>>> f.add_trunc(h, 3)
6*x^2 + 4*x + 2

coeffs(self)

Returns the coefficients of self as a list

>>> from flint import fmpz_poly
>>> f = fmpz_poly([1,2,3,4,5])
>>> f.coeffs()
[1, 2, 3, 4, 5]

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))\).

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> g = R([0,0,1])
>>> 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.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> g = R([3,2,1])
>>> h = R([1,0,1,0,1])
>>> 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

constant_coefficient(self)

Return the constant coefficient of this polynomial.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.constant_coefficient()
fmpz_mod(1, 163)

context(self)

deflate(self, ulong n)

Returns the result of the polynomial \(f = \textrm{self}\) to \(f(x^{1/n})\)

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,0,2,0,3])
>>> f
3*x^4 + 2*x^2 + 1
>>> f.deflate(2)
3*x^2 + 2*x + 1

deflation(self)

Returns the tuple (g, n) where for \(f = \textrm{self}\) to \(g = f(x^{1/n})\) where n is the largest allowed integer

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,0,2,0,3])
>>> f
3*x^4 + 2*x^2 + 1
>>> f.deflate(2)
3*x^2 + 2*x + 1

degree(self) → long

Return the degree of the polynomial

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.degree()
2

derivative(self)

The formal derivative of this polynomial

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = 111*x**4 + 58*x**3 + 98*x**2 + 117*x + 7
>>> f.derivative()
118*x^3 + 11*x^2 + 33*x + 117

discriminant(self)

Return the discriminant of self.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = 6*x**4 + 7*x**3 + 7*x**2 + 8*x + 6
>>> f.discriminant()
fmpz_mod(50, 163)

divmod(self, other)

Return \(Q\), \(R\) such that for self = \(F\) and other = \(G\), \(F = Q*G + R\)

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([123, 129, 63, 14, 51, 76, 133])
>>> g = R([106, 134, 32, 41, 158, 115, 115])
>>> f.divmod(g)
(21, 106*x^5 + 156*x^4 + 131*x^3 + 43*x^2 + 86*x + 16)

equal_trunc(self, other, slong n)

Returns if two polynomials are equal when truncated to the first n terms

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> h = R([1,2,3])
>>> f.equal_trunc(h, 3)
True
>>> f.equal_trunc(h, 4)
False

evaluate(self, input)

Evaluate self at a point in the base ring. This is the same as calling the polynomial directly. To evaluate a list of points, use multiploint_evaluate.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5,6])
>>> f.evaluate(-1)
fmpz_mod(160, 163)
>>> f.evaluate(-1) == f(-1)
True

exact_division(self, right)

Attempt to compute the exact quotient of self with other Raises a value error if division without remainder is not possible.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,1])
>>> g = R([1,1])
>>> f.exact_division(g)
x + 1

factor(self, algorithm=None)

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.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = 6*x**4 + 7*x**3 + 7*x**2 + 8*x + 6
>>> f.factor()
(fmpz_mod(6, 163), [(x^4 + 137*x^3 + 137*x^2 + 110*x + 1, 1)])
>>> f = (x + 1)**3 * (x + 2)
>>> f.factor()
(fmpz_mod(1, 163), [(x + 1, 3), (x + 2, 1)])

factor_squarefree(self)

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

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = (x + 1) * (x + 2)
>>> f.factor_squarefree()
(fmpz_mod(1, 163), [(x^2 + 3*x + 2, 1)])
>>> f = (x + 1) * (x + 2)**5
>>> f.factor_squarefree()
(fmpz_mod(1, 163), [(x + 1, 1), (x + 2, 5)])

gcd(self, other)

Return the greatest common divisor of self and other.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = x*(x + 1)
>>> f.gcd(x+1)
x + 1
>>> f.gcd(x*x)
x

inflate(self, ulong n)

Returns the result of the polynomial \(f = \textrm{self}\) to \(f(x^n)\)

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.inflate(10)
3*x^20 + 2*x^10 + 1

integral(self)

The formal integral of this polynomial. The constant term from boundary conditions is picked to be zero.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = 118*x**3 + 11*x**2 + 33*x + 117
>>> f.integral()
111*x^4 + 58*x^3 + 98*x^2 + 117*x

inverse_mod(self, other)

Returns the inverse of self modulo other

>>> R = fmpz_mod_poly_ctx(163)
>>> f = f = R([123, 129, 63, 14, 51, 76, 133])
>>> f = R([123, 129, 63, 14, 51, 76, 133])
>>> g = R([139, 9, 35, 154, 87, 120, 24])
>>> f.inverse_mod(g)
41*x^5 + 121*x^4 + 47*x^3 + 41*x^2 + 6*x + 5

inverse_series_trunc(self, slong n)

Returns the inverse of self modulo \(x^n\).

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([123, 129, 63, 14, 51, 76, 133])
>>> 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

inverse_sqrt_trunc(self, slong n)

Returns the inverse squareroot of self modulo \(x^n\).

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> h = f.inverse_sqrt_trunc(5)
>>> h
78*x^4 + 2*x^3 + 162*x + 1
>>> (h*h).inverse_series_trunc(5) == f
True

is_constant(self)

Return True if this is a constant polynomial.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> x.is_constant()
False
>>> R(123).is_constant()
True

is_gen(self)

Return True if the polynomial is the generator of the polynomial, \(x\), and False otherwise

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([0,1])
>>> f.is_gen()
True

is_irreducible(self)

Return whether this polynomial is irreducible.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = x**2 + 5*x + 3
>>> f.is_irreducible()
True
>>> f = x**2 + x + 3
>>> f.is_irreducible()
False

is_monic(self)

Return whether this polynomial is monic.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = x**2 + 5*x + 3
>>> f.is_monic()
True
>>> f = 5*x**2 + x + 3
>>> f.is_monic()
False

is_one(self)

Return True if the polynomial is equal to one and False otherwise

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R(1)
>>> f.is_one()
True

is_squarefree(self)

Return whether this polynomial is squarefree.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = (x + 1)**2 * (x + 3)
>>> f.is_squarefree()
False
>>> f = (x + 1) * (x + 3)
>>> f.is_squarefree()
True

is_zero(self)

Return True if the polynomial is the zero polynomial and False otherwise

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R(0)
>>> f.is_zero()
True

leading_coefficient(self)

Return the leading coefficient of this polynomial.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.leading_coefficient()
fmpz_mod(3, 163)

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

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> 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

Return the length of the polynomial

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.length()
3

modulus(self)

monic(self, check=True)

Return this polynomial divided by its leading coefficient.

If check is True, raises ValueError if the leading coefficient is not invertible modulo N. If check is False and the leading coefficient is not invertible, the output is undefined.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.monic()
x^2 + 55*x + 109

mul_low(self, other, slong n)

Returns the lowest n coefficients of the multiplication of self with other

Equivalent to computing \(f(x) \cdot g(x) \mod x^n\)

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([2,3,5,7,11])
>>> g = R([1,2,4,8,16])
>>> f.mul_low(g, 5)
101*x^4 + 45*x^3 + 19*x^2 + 7*x + 2
>>> f.mul_low(g, 3)
19*x^2 + 7*x + 2
>>> f.mul_low(g, 1)
2

mul_mod(self, other, modulus)

Computes the multiplication of self with other modulo the polynomial modulus

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> 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.mul_mod(g, mod)
106*x^3 + 44*x^2 + 53*x + 77

multipoint_evaluate(self, vals)

Returns a list of values computed from evaluating self at the n values given in the vector val

TODO: We could allow passing as an optional input the subproduct tree, which would allow for faster, repeated multipoint evaluations

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> [f(x) for x in [-1,-2,-3]]
[fmpz_mod(3, 163), fmpz_mod(57, 163), fmpz_mod(156, 163)]
>>> f.multipoint_evaluate([-1,-2,-3])
[fmpz_mod(3, 163), fmpz_mod(57, 163), fmpz_mod(156, 163)]

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.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> 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

pow_trunc(self, slong e, slong n)

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

Note: For exponents larger that 2^31 (which do not fit inside a ulong) use the method pow_mod() with the explicit modulus \(x^n\).

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = 30*x**6 + 104*x**5 + 76*x**4 + 33*x**3 + 70*x**2 + 44*x + 65
>>> f.pow_trunc(2**20, 30) == pow(f, 2**20, x**30)
True
>>> f.pow_trunc(2**20, 5)
132*x^4 + 113*x^3 + 36*x^2 + 48*x + 6

radical(self)

Return the radical of self, the product of the irreducible factors of the polynomial. This is also referred to as the square-free part of the polynomial.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = (x + 1)**3 * (x + 2)
>>> f.radical()
x^2 + 3*x + 2

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 with other.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> g = R([9,8,7])
>>> f.resultant(g)
fmpz_mod(57, 163)

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.

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3,4,5])
>>> 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

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.right_shift(0)
3*x^2 + 2*x + 1
>>> f.right_shift(1)
3*x + 2
>>> f.right_shift(4)
0

roots(self, multiplicities=True)

Return the roots of the polynomial in \((\mathbb{Z}/N\mathbb{Z})^*\) Requires that the modulus \(N\) is prime.

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = (x - 1) * (x - 2)**3 * (x - 3)**5
>>> f.roots()
[(fmpz_mod(1, 163), 1), (fmpz_mod(2, 163), 3), (fmpz_mod(3, 163), 5)]
>>> f.roots(multiplicities=False)
[fmpz_mod(1, 163), fmpz_mod(2, 163), fmpz_mod(3, 163)]

scalar_mul(self, other)

Returns the polynomial equal to self scaled by the input other

sqrt(self)

If self is a perfect square, compute the square root

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,1])
>>> (f*f).sqrt()
x + 1

sqrt_trunc(self, slong n)

Returns the squareroot of self modulo \(x^n\).

>>> R = fmpz_mod_poly_ctx(163)
>>> x = R.gen()
>>> f = R([1,2,3])
>>> h = f.sqrt_trunc(5)
>>> h
82*x^4 + 162*x^3 + x^2 + x + 1
>>> h.mul_mod(h, x**5) == f
True

square(self)

Returns the square of self

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> f.square()
9*x^4 + 12*x^3 + 10*x^2 + 4*x + 1

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.

sub_trunc(self, other, slong n)

Truncate self and other to polynomials of length n and return their difference

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([2,3,5,7,11])
>>> h = R([1,2,4,8,16])
>>> f.sub_trunc(h, 2)
x + 1
>>> f.sub_trunc(h, 4)
162*x^3 + x^2 + x + 1

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\).

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([1,2,3])
>>> 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)

Computes the extended gcd of self and other: (\(G\), \(S\), \(T\)) where \(G\) is the gcd(self, other) and \(S\), \(T\) are such that:

\(G = \textrm{self}*S + \textrm{other}*T\)

>>> R = fmpz_mod_poly_ctx(163)
>>> f = R([143, 19, 37, 138, 102, 127, 95])
>>> g = R([139, 9, 35, 154, 87, 120, 24])
>>> f.xgcd(g)
(x^3 + 128*x^2 + 123*x + 91, 17*x^2 + 49*x + 104, 21*x^2 + 5*x + 25)