Univariate Polynomials over GF(p^e) via NTL’s ZZ_pEX#

AUTHOR:

Yann Laigle-Chapuy (2010-01) initial implementation
Lorenz Panny (2023-01): minpoly_mod()

class sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX#

Bases: Polynomial_template

Univariate Polynomials over GF(p^n) via NTL’s ZZ_pEX.

EXAMPLES:

sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: (x^3 + a*x^2 + 1) * (x + a)
x^4 + 2*a*x^3 + a^2*x^2 + x + a

is_irreducible(algorithm='fast_when_false', iter=1)#

Returns \(True\) precisely when self is irreducible over its base ring.

INPUT:

Parameters:

algorithm – a string (default “fast_when_false”), there are 3 available algorithms: “fast_when_true”, “fast_when_false” and “probabilistic”.
iter – (default: 1) if the algorithm is “probabilistic” defines the number of iterations. The error probability is bounded by \(q**-iter\) for polynomials in \(GF(q)[x]\).

EXAMPLES:

sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: P = x^3+(2-a)*x+1
sage: P.is_irreducible(algorithm="fast_when_false")
True
sage: P.is_irreducible(algorithm="fast_when_true")
True
sage: P.is_irreducible(algorithm="probabilistic")
True
sage: Q = (x^2+a)*(x+a^3)
sage: Q.is_irreducible(algorithm="fast_when_false")
False
sage: Q.is_irreducible(algorithm="fast_when_true")
False
sage: Q.is_irreducible(algorithm="probabilistic")
False

list(copy=True)#

Return the list of coefficients.

EXAMPLES:

sage: K.<a> = GF(5^3)
sage: P = PolynomialRing(K, 'x')
sage: f = P.random_element(100)
sage: f.list() == [f[i] for i in  range(f.degree()+1)]
True
sage: P.0.list()
[0, 1]

minpoly_mod(other)#

Compute the minimal polynomial of this polynomial modulo another polynomial in the same ring.

ALGORITHM:

NTL’s MinPolyMod(), which uses Shoup’s algorithm [Sho1999].

EXAMPLES:

sage: R.<x> = GF(101^2)[]
sage: f = x^17 + x^2 - 1
sage: (x^2).minpoly_mod(f)
x^17 + 100*x^2 + 2*x + 100

resultant(other)#

Returns the resultant of self and other, which must lie in the same polynomial ring.

INPUT:

Parameters:: other – a polynomial

OUTPUT: an element of the base ring of the polynomial ring

EXAMPLES:

sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: f=(x-a)*(x-a**2)*(x+1)
sage: g=(x-a**3)*(x-a**4)*(x+a)
sage: r = f.resultant(g)
sage: r == prod(u-v for (u,eu) in f.roots() for (v,ev) in g.roots())
True

shift(n)#

EXAMPLES:

sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: f = x^3 + x^2 + 1
sage: f.shift(1)
x^4 + x^3 + x
sage: f.shift(-1)
x^2 + x

class sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pX#: Bases: Polynomial_template

class sage.rings.polynomial.polynomial_zz_pex.Polynomial_template#

Bases: Polynomial

Template for interfacing to external C / C++ libraries for implementations of polynomials.

AUTHORS:

Robert Bradshaw (2008-10): original idea for templating
Martin Albrecht (2008-10): initial implementation

This file implements a simple templating engine for linking univariate polynomials to their C/C++ library implementations. It requires a ‘linkage’ file which implements the celement_ functions (see sage.libs.ntl.ntl_GF2X_linkage for an example). Both parts are then plugged together by inclusion of the linkage file when inheriting from this class. See sage.rings.polynomial.polynomial_gf2x for an example.

We illustrate the generic glueing using univariate polynomials over \(\mathop{\mathrm{GF}}(2)\).

Note

Implementations using this template MUST implement coercion from base ring elements and get_unsafe(). See Polynomial_GF2X for an example.

degree()#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: x.degree()
1
sage: P(1).degree()
0
sage: P(0).degree()
-1

gcd(other)#

Return the greatest common divisor of self and other.

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: f = x*(x+1)
sage: f.gcd(x+1)
x + 1
sage: f.gcd(x^2)
x

get_cparent()#

is_gen()#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: x.is_gen()
True
sage: (x+1).is_gen()
False

is_one()#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: P(1).is_one()
True

is_zero()#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: x.is_zero()
False

list(copy=True)#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: x.list()
[0, 1]
sage: list(x)
[0, 1]

quo_rem(right)#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: f = x^2 + x + 1
sage: f.quo_rem(x + 1)
(x, 1)

shift(n)#

EXAMPLES:

sage: P.<x> = GF(2)[]
sage: f = x^3 + x^2 + 1
sage: f.shift(1)
x^4 + x^3 + x
sage: f.shift(-1)
x^2 + x

truncate(n)#

Returns this polynomial mod \(x^n\).

EXAMPLES:

sage: R.<x> =GF(2)[]
sage: f = sum(x^n for n in range(10)); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
sage: f.truncate(6)
x^5 + x^4 + x^3 + x^2 + x + 1

If the precision is higher than the degree of the polynomial then the polynomial itself is returned:

sage: f.truncate(10) is f
True

If the precision is negative, the zero polynomial is returned:

sage: f.truncate(-1)
0

xgcd(other)#

Computes extended gcd of self and other.

EXAMPLES:

sage: P.<x> = GF(7)[]
sage: f = x*(x+1)
sage: f.xgcd(x+1)
(x + 1, 0, 1)
sage: f.xgcd(x^2)
(x, 1, 6)

sage.rings.polynomial.polynomial_zz_pex.make_element(parent, args)#