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

• Giacomo Pope (2023-08): reverse(), inverse_series_trunc()

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

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

Python

>>> from sage.all import *
>>> K = GF(next_prime(Integer(2)**Integer(60))**Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> R = PolynomialRing(K, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(3) + a*x**Integer(2) + Integer(1)) * (x + a)
x^4 + 2*a*x^3 + a^2*x^2 + x + a

Sage Live

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

compose_mod(other, modulus)

Compute \(f(g) \bmod h\).

To be precise about the order fo compostion, given self, other and modulus as \(f(x)\), \(g(x)\) and \(h(x)\) compute \(f(g(x)) \bmod h(x)\).

INPUT:

• other – a polynomial \(g(x)\)

• modulus – a polynomial \(h(x)\)

EXAMPLES:

Sage

sage: R.<x> = GF(3**6)[]
sage: f = R.random_element()
sage: g = R.random_element()
sage: g.compose_mod(g, f) == g(g) % f
True

sage: F.<z3> = GF(3**6)
sage: R.<x> = F[]
sage: f = 2*z3^2*x^2 + (z3 + 1)*x + z3^2 + 2
sage: g = (z3^2 + 2*z3)*x^2 + (2*z3 + 2)*x + 2*z3^2 + z3 + 2
sage: h = (2*z3 + 2)*x^2 + (2*z3^2 + 1)*x + 2*z3^2 + z3 + 2
sage: f.compose_mod(g, h)
(z3^5 + z3^4 + z3^3 + z3^2 + z3)*x + z3^5 + z3^3 + 2*z3 + 2
sage: f.compose_mod(g, h) == f(g) % h
True

Python

>>> from sage.all import *
>>> R = GF(Integer(3)**Integer(6))['x']; (x,) = R._first_ngens(1)
>>> f = R.random_element()
>>> g = R.random_element()
>>> g.compose_mod(g, f) == g(g) % f
True

>>> F = GF(Integer(3)**Integer(6), names=('z3',)); (z3,) = F._first_ngens(1)
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> f = Integer(2)*z3**Integer(2)*x**Integer(2) + (z3 + Integer(1))*x + z3**Integer(2) + Integer(2)
>>> g = (z3**Integer(2) + Integer(2)*z3)*x**Integer(2) + (Integer(2)*z3 + Integer(2))*x + Integer(2)*z3**Integer(2) + z3 + Integer(2)
>>> h = (Integer(2)*z3 + Integer(2))*x**Integer(2) + (Integer(2)*z3**Integer(2) + Integer(1))*x + Integer(2)*z3**Integer(2) + z3 + Integer(2)
>>> f.compose_mod(g, h)
(z3^5 + z3^4 + z3^3 + z3^2 + z3)*x + z3^5 + z3^3 + 2*z3 + 2
>>> f.compose_mod(g, h) == f(g) % h
True

Sage Live

R.<x> = GF(3**6)[]
f = R.random_element()
g = R.random_element()
g.compose_mod(g, f) == g(g) % f
F.<z3> = GF(3**6)
R.<x> = F[]
f = 2*z3^2*x^2 + (z3 + 1)*x + z3^2 + 2
g = (z3^2 + 2*z3)*x^2 + (2*z3 + 2)*x + 2*z3^2 + z3 + 2
h = (2*z3 + 2)*x^2 + (2*z3^2 + 1)*x + 2*z3^2 + z3 + 2
f.compose_mod(g, h)
f.compose_mod(g, h) == f(g) % h

AUTHORS:

• Giacomo Pope (2024-08) initial implementation

inverse_series_trunc(prec)

Compute and return the inverse of self modulo \(x^{prec}\).

The constant term of self must be invertible.

EXAMPLES:

Sage

sage: R.<x> = GF(101^2)[]
sage: z2 =  R.base_ring().gen()
sage: f = (3*z2 + 57)*x^3 + (13*z2 + 94)*x^2 + (7*z2 + 2)*x + 66*z2 + 15
sage: f.inverse_series_trunc(1)
51*z2 + 92
sage: f.inverse_series_trunc(2)
(30*z2 + 30)*x + 51*z2 + 92
sage: f.inverse_series_trunc(3)
(42*z2 + 94)*x^2 + (30*z2 + 30)*x + 51*z2 + 92
sage: f.inverse_series_trunc(4)
(99*z2 + 96)*x^3 + (42*z2 + 94)*x^2 + (30*z2 + 30)*x + 51*z2 + 92

Python

>>> from sage.all import *
>>> R = GF(Integer(101)**Integer(2))['x']; (x,) = R._first_ngens(1)
>>> z2 =  R.base_ring().gen()
>>> f = (Integer(3)*z2 + Integer(57))*x**Integer(3) + (Integer(13)*z2 + Integer(94))*x**Integer(2) + (Integer(7)*z2 + Integer(2))*x + Integer(66)*z2 + Integer(15)
>>> f.inverse_series_trunc(Integer(1))
51*z2 + 92
>>> f.inverse_series_trunc(Integer(2))
(30*z2 + 30)*x + 51*z2 + 92
>>> f.inverse_series_trunc(Integer(3))
(42*z2 + 94)*x^2 + (30*z2 + 30)*x + 51*z2 + 92
>>> f.inverse_series_trunc(Integer(4))
(99*z2 + 96)*x^3 + (42*z2 + 94)*x^2 + (30*z2 + 30)*x + 51*z2 + 92

Sage Live

R.<x> = GF(101^2)[]
z2 =  R.base_ring().gen()
f = (3*z2 + 57)*x^3 + (13*z2 + 94)*x^2 + (7*z2 + 2)*x + 66*z2 + 15
f.inverse_series_trunc(1)
f.inverse_series_trunc(2)
f.inverse_series_trunc(3)
f.inverse_series_trunc(4)

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

Return True precisely when self is irreducible over its base ring.

INPUT:

• algorithm – 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^{\text{-iter}}\) for polynomials in \(\GF{q}[x]\).

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> K = GF(next_prime(Integer(2)**Integer(60))**Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> R = PolynomialRing(K, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> P = x**Integer(3) + (Integer(2)-a)*x + Integer(1)
>>> P.is_irreducible(algorithm='fast_when_false')
True
>>> P.is_irreducible(algorithm='fast_when_true')
True
>>> P.is_irreducible(algorithm='probabilistic')
True
>>> Q = (x**Integer(2)+a)*(x+a**Integer(3))
>>> Q.is_irreducible(algorithm='fast_when_false')
False
>>> Q.is_irreducible(algorithm='fast_when_true')
False
>>> Q.is_irreducible(algorithm='probabilistic')
False

Sage Live

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

list(copy=True)

Return the list of coefficients.

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> K = GF(Integer(5)**Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> P = PolynomialRing(K, 'x')
>>> f = P.random_element(Integer(100))
>>> f.list() == [f[i] for i in range(f.degree()+Integer(1))]
True
>>> P.gen(0).list()
[0, 1]

Sage Live

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

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

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

Python

>>> from sage.all import *
>>> R = GF(Integer(101)**Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(17) + x**Integer(2) - Integer(1)
>>> (x**Integer(2)).minpoly_mod(f)
x^17 + 100*x^2 + 2*x + 100

Sage Live

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

modular_composition(other, modulus)

Compute \(f(g) \bmod h\).

To be precise about the order fo compostion, given self, other and modulus as \(f(x)\), \(g(x)\) and \(h(x)\) compute \(f(g(x)) \bmod h(x)\).

INPUT:

• other – a polynomial \(g(x)\)

• modulus – a polynomial \(h(x)\)

EXAMPLES:

Sage

sage: R.<x> = GF(3**6)[]
sage: f = R.random_element()
sage: g = R.random_element()
sage: g.compose_mod(g, f) == g(g) % f
True

sage: F.<z3> = GF(3**6)
sage: R.<x> = F[]
sage: f = 2*z3^2*x^2 + (z3 + 1)*x + z3^2 + 2
sage: g = (z3^2 + 2*z3)*x^2 + (2*z3 + 2)*x + 2*z3^2 + z3 + 2
sage: h = (2*z3 + 2)*x^2 + (2*z3^2 + 1)*x + 2*z3^2 + z3 + 2
sage: f.compose_mod(g, h)
(z3^5 + z3^4 + z3^3 + z3^2 + z3)*x + z3^5 + z3^3 + 2*z3 + 2
sage: f.compose_mod(g, h) == f(g) % h
True

Python

>>> from sage.all import *
>>> R = GF(Integer(3)**Integer(6))['x']; (x,) = R._first_ngens(1)
>>> f = R.random_element()
>>> g = R.random_element()
>>> g.compose_mod(g, f) == g(g) % f
True

>>> F = GF(Integer(3)**Integer(6), names=('z3',)); (z3,) = F._first_ngens(1)
>>> R = F['x']; (x,) = R._first_ngens(1)
>>> f = Integer(2)*z3**Integer(2)*x**Integer(2) + (z3 + Integer(1))*x + z3**Integer(2) + Integer(2)
>>> g = (z3**Integer(2) + Integer(2)*z3)*x**Integer(2) + (Integer(2)*z3 + Integer(2))*x + Integer(2)*z3**Integer(2) + z3 + Integer(2)
>>> h = (Integer(2)*z3 + Integer(2))*x**Integer(2) + (Integer(2)*z3**Integer(2) + Integer(1))*x + Integer(2)*z3**Integer(2) + z3 + Integer(2)
>>> f.compose_mod(g, h)
(z3^5 + z3^4 + z3^3 + z3^2 + z3)*x + z3^5 + z3^3 + 2*z3 + 2
>>> f.compose_mod(g, h) == f(g) % h
True

Sage Live

R.<x> = GF(3**6)[]
f = R.random_element()
g = R.random_element()
g.compose_mod(g, f) == g(g) % f
F.<z3> = GF(3**6)
R.<x> = F[]
f = 2*z3^2*x^2 + (z3 + 1)*x + z3^2 + 2
g = (z3^2 + 2*z3)*x^2 + (2*z3 + 2)*x + 2*z3^2 + z3 + 2
h = (2*z3 + 2)*x^2 + (2*z3^2 + 1)*x + 2*z3^2 + z3 + 2
f.compose_mod(g, h)
f.compose_mod(g, h) == f(g) % h

AUTHORS:

• Giacomo Pope (2024-08) initial implementation

resultant(other)

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

INPUT:

• other – a polynomial

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

EXAMPLES:

Sage

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

Python

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

Sage Live

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

reverse(degree=None)

Return the polynomial obtained by reversing the coefficients of this polynomial. If degree is set then this function behaves as if this polynomial has degree degree.

EXAMPLES:

Sage

sage: R.<x> = GF(101^2)[]
sage: f = x^13 + 11*x^10 + 32*x^6 + 4
sage: f.reverse()
4*x^13 + 32*x^7 + 11*x^3 + 1
sage: f.reverse(degree=15)
4*x^15 + 32*x^9 + 11*x^5 + x^2
sage: f.reverse(degree=2)
4*x^2

Python

>>> from sage.all import *
>>> R = GF(Integer(101)**Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = x**Integer(13) + Integer(11)*x**Integer(10) + Integer(32)*x**Integer(6) + Integer(4)
>>> f.reverse()
4*x^13 + 32*x^7 + 11*x^3 + 1
>>> f.reverse(degree=Integer(15))
4*x^15 + 32*x^9 + 11*x^5 + x^2
>>> f.reverse(degree=Integer(2))
4*x^2

Sage Live

R.<x> = GF(101^2)[]
f = x^13 + 11*x^10 + 32*x^6 + 4
f.reverse()
f.reverse(degree=15)
f.reverse(degree=2)

shift(n)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> K = GF(next_prime(Integer(2)**Integer(60))**Integer(3), names=('a',)); (a,) = K._first_ngens(1)
>>> R = PolynomialRing(K, implementation='NTL', names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(3) + x**Integer(2) + Integer(1)
>>> f.shift(Integer(1))
x^4 + x^3 + x
>>> f.shift(-Integer(1))
x^2 + x

Sage Live

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

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

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.degree()
1
>>> P(Integer(1)).degree()
0
>>> P(Integer(0)).degree()
-1

Sage Live

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

gcd(other)

Return the greatest common divisor of self and other.

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x*(x+Integer(1))
>>> f.gcd(x+Integer(1))
x + 1
>>> f.gcd(x**Integer(2))
x

Sage Live

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

get_cparent()

is_gen()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.is_gen()
True
>>> (x+Integer(1)).is_gen()
False

Sage Live

P.<x> = GF(2)[]
x.is_gen()
(x+1).is_gen()

is_one()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> P(Integer(1)).is_one()
True

Sage Live

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

is_zero()

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.is_zero()
False

Sage Live

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

list(copy=True)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> x.list()
[0, 1]
>>> list(x)
[0, 1]

Sage Live

P.<x> = GF(2)[]
x.list()
list(x)

quo_rem(right)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(2) + x + Integer(1)
>>> f.quo_rem(x + Integer(1))
(x, 1)

Sage Live

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

shift(n)

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> P = GF(Integer(2))['x']; (x,) = P._first_ngens(1)
>>> f = x**Integer(3) + x**Integer(2) + Integer(1)
>>> f.shift(Integer(1))
x^4 + x^3 + x
>>> f.shift(-Integer(1))
x^2 + x

Sage Live

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

truncate(n)

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> R = GF(Integer(2))['x']; (x,) = R._first_ngens(1)
>>> f = sum(x**n for n in range(Integer(10))); f
x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
>>> f.truncate(Integer(6))
x^5 + x^4 + x^3 + x^2 + x + 1

Sage Live

R.<x> =GF(2)[]
f = sum(x^n for n in range(10)); f
f.truncate(6)

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

Sage

sage: f.truncate(10) is f
True

Python

>>> from sage.all import *
>>> f.truncate(Integer(10)) is f
True

Sage Live

f.truncate(10) is f

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

Sage

sage: f.truncate(-1)
0

Python

>>> from sage.all import *
>>> f.truncate(-Integer(1))
0

Sage Live

f.truncate(-1)

xgcd(other)

Compute extended gcd of self and other.

EXAMPLES:

Sage

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)

Python

>>> from sage.all import *
>>> P = GF(Integer(7))['x']; (x,) = P._first_ngens(1)
>>> f = x*(x+Integer(1))
>>> f.xgcd(x+Integer(1))
(x + 1, 0, 1)
>>> f.xgcd(x**Integer(2))
(x, 1, 6)

Sage Live

P.<x> = GF(7)[]
f = x*(x+1)
f.xgcd(x+1)
f.xgcd(x^2)

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

Make live