fq_default_poly – polynomials over finite fields

class flint.fq_default_poly_ctx(*args, **kwargs)

Context object for creating fq_default_poly initialised with a finite field \(GF(p^d)\).

>>> fq_default_poly_ctx(163, 3, fq_type="FQ_NMOD")
fq_default_poly_ctx(fq_default_ctx(163, 3, 'z', x^3 + 7*x + 161, 'FQ_NMOD'))

base_field(self)

Return the base field of the polynomial ring

>>> R = fq_default_poly_ctx(65537, 3)
>>> R.base_field()
fq_default_ctx(65537, 3, 'z', x^3 + 3*x^2 + 30077, 'FQ_NMOD')

characteristic(self)

Return the characteristic of the field from the context as an fmpz type

>>> R = fq_default_poly_ctx(65537, 3)
>>> R.characteristic()
65537

gen(self)

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

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

one(self)

Return the one element of this polynomial ring

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

prime()

fq_default_poly_ctx.characteristic(self)

Return the characteristic of the field from the context as an fmpz type

>>> R = fq_default_poly_ctx(65537, 3)
>>> R.characteristic()
65537

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

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

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

zero(self)

Return the zero element of this polynomial ring

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

class flint.fq_default_poly(val, ctx)

The fq_default_poly type represents univariate polynomials over a finite field.

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

>>> fq_default_poly([1,-2,3], fq_default_poly_ctx(2**127 - 1))
3*x^2 + 170141183460469231731687303715884105725*x + 1
>>> R = fq_default_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 = fq_default_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 finite fields

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

context(self)

deflate(self, ulong n)

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

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

derivative(self)

The formal derivative of this polynomial

>>> R = fq_default_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

divmod(self, other)

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

>>> R = fq_default_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 = fq_default_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.

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

exact_division(self, other)

Attempt to compute the exact quotient of self with other.

Raises a value error if division without remainder is not possible.

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

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.

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

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 = fq_default_poly_ctx(163)
>>> x = R.gen()
>>> f = (x + 1) * (x + 2)
>>> f.factor_squarefree()
(1, [(x^2 + 3*x + 2, 1)])
>>> f = (x + 1) * (x + 2)**5
>>> f.factor_squarefree()
(1, [(x + 1, 1), (x + 2, 5)])

gcd(self, other)

Return the greatest common divisor of self and other.

>>> R = fq_default_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 = fq_default_poly_ctx(163, 3)
>>> f = R([1,2,3])
>>> f.inflate(10)
3*x^20 + 2*x^10 + 1

integral(self)

inv_sqrt_trunc(self, slong n)

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

Requires that the constant coefficient of the polynomial is one.

>>> R = fq_default_poly_ctx(65537, 2)
>>> x = R.gen()
>>> z = R.base_field().gen()
>>> f = 28902*x**3 + (49416*z + 58229)*x**2 + 9441*z*x + (7944*z + 57534)
>>> h = f.inv_sqrt_trunc(3)
>>> h
(23030*z + 8965)*x^2 + (43656*z + 7173)*x + (27935*z + 28199)
>>> (h*h).mul_low(f, 3).is_one()
True

inverse_mod(self, other)

Returns the inverse of self modulo other

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

inverse_series_trunc(self, slong n)

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

>>> R = fq_default_poly_ctx(163, 3)
>>> x = R.gen()
>>> z = R.base_field().gen()
>>> f = (37*z + 54)*x**3 + (8*z + 94)*x**2 + (52*z + 142)*x + 1
>>> f.inverse_series_trunc(2)
(111*z + 21)*x + 1
>>> f.inverse_series_trunc(3)
(96*z^2 + 90*z + 21)*x^2 + (111*z + 21)*x + 1
>>> f.inverse_series_trunc(4)
(34*z^2 + z + 2)*x^3 + (96*z^2 + 90*z + 21)*x^2 + (111*z + 21)*x + 1
>>> h = f.inverse_series_trunc(4)
>>> f.mul_low(h, 4).is_one()
True

is_constant(self)

Return True if this is a constant polynomial.

>>> R = fq_default_poly_ctx(163, 3)
>>> 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 = fq_default_poly_ctx(163, 3)
>>> f = R([0,1])
>>> f.is_gen()
True

is_irreducible(self)

Return whether this polynomial is irreducible.

>>> R = fq_default_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 = fq_default_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 = fq_default_poly_ctx(163, 3)
>>> f = R.one()
>>> f.is_one()
True

is_squarefree(self)

Return whether this polynomial is squarefree.

>>> R = fq_default_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 = fq_default_poly_ctx(163, 3)
>>> f = R.zero()
>>> f.is_zero()
True

leading_coefficient(self)

Return the leading coefficient of this polynomial.

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

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

monic(self)

Return this polynomial divided by its leading coefficient.

>>> R = fq_default_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 = fq_default_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 = fq_default_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

pow_mod(self, e, modulus)

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

>>> R = fq_default_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
>>> 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

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 = fq_default_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 = fq_default_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 finite fields

repr(self)

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 = fq_default_poly_ctx(163, 3)
>>> 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 = fq_default_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 the finite field

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

sqrt(self)

If self is a perfect square, compute the square root

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

sqrt_trunc(self, slong n)

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

Requires that the constant coefficient of the polynomial is one.

>>> R = fq_default_poly_ctx(163, 3)
>>> x = R.gen()
>>> z = R.base_field().gen()
>>> f = (37*z + 54)*x**3 + (8*z + 94)*x**2 + (52*z + 142)*x + 1
>>> h = f.sqrt_trunc(4)
>>> h
(7*z^2 + 17*z + 148)*x^3 + (151*z^2 + 114*z + 53)*x^2 + (26*z + 71)*x + 1
>>> h.mul_low(h, 4) == f
True

square(self)

Returns the square of self

>>> R = fq_default_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 = fq_default_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 self is returned. If n is not positive, then the zero polynomial is returned.

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

>>> R = fq_default_poly_ctx(163, 5)
>>> 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 = fq_default_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)
>>> G, S, T = f.xgcd(g)
>>> assert G == f*S + g*T