Univariate dense skew polynomials over finite fields#

This module provides the class: $s a g e . r i n g s . p o l y n o m i a l . s k e w_{p} o l y n o m i a l_{f} i n i t e_{f} i e l d . S k e w P o l y n o m i a l_{f} i n i t e_{f} i e l d_{d} e n s e$ , which constructs a single univariate skew polynomial over a finite field equipped with the Frobenius endomorphism. Among other things, it implements the fast factorization algorithm designed in [CL2017].

AUTHOR:

- Xavier Caruso (2012-06-29): initial version

Arpit Merchant (2016-08-04): improved docstrings, fixed doctests and refactored classes and methods

class sage.rings.polynomial.skew_polynomial_finite_field.SkewPolynomial_finite_field_dense#

Bases: SkewPolynomial_finite_order_dense

count_factorizations()#

Return the number of factorizations (as a product of a unit and a product of irreducible monic factors) of this skew polynomial.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^4 + (4*t + 3)*x^3 + t^2*x^2 + (4*t^2 + 3*t)*x + 3*t
sage: a.count_factorizations()
216

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^4 + (4*t + 3)*x^3 + t^2*x^2 + (4*t^2 + 3*t)*x + 3*t
a.count_factorizations()

We illustrate that an irreducible polynomial in the center have in general a lot of distinct factorizations in the skew polynomial ring:

sage: Z.<x3> = S.center()
sage: N = x3^5 + 4*x3^4 + 4*x3^2 + 4*x3 + 3
sage: N.is_irreducible()
True
sage: S(N).count_factorizations()
30537115626

Z.<x3> = S.center()
N = x3^5 + 4*x3^4 + 4*x3^2 + 4*x3 + 3
N.is_irreducible()
S(N).count_factorizations()

count_irreducible_divisors()#

Return the number of irreducible monic divisors of this skew polynomial.

Note

One can prove that there are always as many left irreducible monic divisors as right irreducible monic divisors.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]

We illustrate that a skew polynomial may have a number of irreducible divisors greater than its degree:

sage: a = x^4 + (4*t + 3)*x^3 + t^2*x^2 + (4*t^2 + 3*t)*x + 3*t
sage: a.count_irreducible_divisors()
12

a = x^4 + (4*t + 3)*x^3 + t^2*x^2 + (4*t^2 + 3*t)*x + 3*t
a.count_irreducible_divisors()

We illustrate that an irreducible polynomial in the center have in general a lot of irreducible divisors in the skew polynomial ring:

sage: Z.<x3> = S.center()
sage: N = x3^5 + 4*x3^4 + 4*x3^2 + 4*x3 + 3; N
x3^5 + 4*x3^4 + 4*x3^2 + 4*x3 + 3
sage: N.is_irreducible()
True
sage: S(N).count_irreducible_divisors()
9768751

Z.<x3> = S.center()
N = x3^5 + 4*x3^4 + 4*x3^2 + 4*x3 + 3; N
N.is_irreducible()
S(N).count_irreducible_divisors()

factor(uniform=False)#

Return a factorization of this skew polynomial.

INPUT:

uniform – a boolean (default: False); whether the output irreducible divisor should be uniformly distributed among all possibilities

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^3 + (t^2 + 4*t + 2)*x^2 + (3*t + 3)*x + t^2 + 1
sage: F = a.factor(); F   # random
(x + t^2 + 4) * (x + t + 3) * (x + t)
sage: F.value() == a
True

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^3 + (t^2 + 4*t + 2)*x^2 + (3*t + 3)*x + t^2 + 1
F = a.factor(); F   # random
F.value() == a

The result of the factorization is cached. Hence, if we try again to factor $a$ , we will get the same answer:

sage: a.factor()  # random
(x + t^2 + 4) * (x + t + 3) * (x + t)

a.factor()  # random

However, the algorithm is probabilistic. Hence if we first reinitialiaze $a$ , we may get a different answer:

sage: a = x^3 + (t^2 + 4*t + 2)*x^2 + (3*t + 3)*x + t^2 + 1
sage: F = a.factor(); F   # random
(x + t^2 + t + 2) * (x + 2*t^2 + t + 4) * (x + t)
sage: F.value() == a
True

a = x^3 + (t^2 + 4*t + 2)*x^2 + (3*t + 3)*x + t^2 + 1
F = a.factor(); F   # random
F.value() == a

There is a priori no guarantee on the distribution of the factorizations we get. Passing in the keyword uniform=True ensures the output is uniformly distributed among all factorizations:

sage: a.factor(uniform=True)   # random
(x + t^2 + 4) * (x + t) * (x + t + 3)
sage: a.factor(uniform=True)   # random
(x + 2*t^2) * (x + t^2 + t + 1) * (x + t^2 + t + 2)
sage: a.factor(uniform=True)   # random
(x + 2*t^2 + 3*t) * (x + 4*t + 2) * (x + 2*t + 2)

a.factor(uniform=True)   # random
a.factor(uniform=True)   # random
a.factor(uniform=True)   # random

By convention, the zero skew polynomial has no factorization:

sage: S(0).factor()
Traceback (most recent call last):
...
ValueError: factorization of 0 not defined

S(0).factor()

factorizations()#

Return an iterator over all factorizations (as a product of a unit and a product of irreducible monic factors) of this skew polynomial.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^3 + (t^2 + 1)*x^2 + (2*t + 3)*x + t^2 + t + 2
sage: iter = a.factorizations(); iter
<...generator object at 0x...>
sage: next(iter)   # random
(x + 3*t^2 + 4*t) * (x + 2*t^2) * (x + 4*t^2 + 4*t + 2)
sage: next(iter)   # random
(x + 3*t^2 + 4*t) * (x + 3*t^2 + 2*t + 2) * (x + 4*t^2 + t + 2)

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^3 + (t^2 + 1)*x^2 + (2*t + 3)*x + t^2 + t + 2
iter = a.factorizations(); iter
next(iter)   # random
next(iter)   # random

We can use this function to build the list of factorizations of $a$ :

sage: factorizations = [ F for F in a.factorizations() ]

factorizations = [ F for F in a.factorizations() ]

We do some checks:

sage: len(factorizations) == a.count_factorizations()
True
sage: len(factorizations) == Set(factorizations).cardinality()  # check no duplicates
True
sage: for F in factorizations:
....:     assert F.value() == a, "factorization has a different value"
....:     for d,_ in F:
....:         assert d.is_irreducible(), "a factor is not irreducible"

len(factorizations) == a.count_factorizations()
len(factorizations) == Set(factorizations).cardinality()  # check no duplicates
for F in factorizations:
    assert F.value() == a, "factorization has a different value"
    for d,_ in F:
        assert d.is_irreducible(), "a factor is not irreducible"

Note that the algorithm used in this method is probabilistic. As a consequence, if we call it two times with the same input, we can get different orderings:

sage: factorizations2 = [ F for F in a.factorizations() ]
sage: factorizations == factorizations2  # random
False
sage: sorted(factorizations) == sorted(factorizations2)
True

factorizations2 = [ F for F in a.factorizations() ]
factorizations == factorizations2  # random
sorted(factorizations) == sorted(factorizations2)

is_irreducible()#

Return True if this skew polynomial is irreducible.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]

sage: a = x^2 + t*x + 1
sage: a.is_irreducible()
False
sage: a.factor()
(x + 4*t^2 + 4*t + 1) * (x + 3*t + 2)

sage: a = x^2 + t*x + t + 1
sage: a.is_irreducible()
True
sage: a.factor()
x^2 + t*x + t + 1

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^2 + t*x + 1
a.is_irreducible()
a.factor()
a = x^2 + t*x + t + 1
a.is_irreducible()
a.factor()

Skew polynomials of degree $1$ are of course irreducible:

sage: a = x + t
sage: a.is_irreducible()
True

a = x + t
a.is_irreducible()

A random irreducible skew polynomial is irreducible:

sage: a = S.random_irreducible(degree=4,monic=True); a   # random
x^4 + (t + 1)*x^3 + (3*t^2 + 2*t + 3)*x^2 + 3*t*x + 3*t
sage: a.is_irreducible()
True

a = S.random_irreducible(degree=4,monic=True); a   # random
a.is_irreducible()

By convention, constant skew polynomials are not irreducible:

sage: S(1).is_irreducible()
False
sage: S(0).is_irreducible()
False

S(1).is_irreducible()
S(0).is_irreducible()

left_irreducible_divisor(uniform=False)#

Return a left irreducible divisor of this skew polynomial.

INPUT:

uniform – a boolean (default: False); whether the output irreducible divisor should be uniformly distributed among all possibilities

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3
sage: dl = a.left_irreducible_divisor(); dl  # random
x^3 + (t^2 + t + 2)*x^2 + (t + 2)*x + 3*t^2 + t + 4
sage: a.is_left_divisible_by(dl)
True

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3
dl = a.left_irreducible_divisor(); dl  # random
a.is_left_divisible_by(dl)

The algorithm is probabilistic. Hence, if we ask again for a left irreducible divisor of $a$ , we may get a different answer:

sage: a.left_irreducible_divisor()  # random
x^3 + (4*t + 3)*x^2 + (2*t^2 + 3*t + 4)*x + 4*t^2 + 2*t

a.left_irreducible_divisor()  # random

We can also generate uniformly distributed irreducible monic divisors as follows:

sage: a.left_irreducible_divisor(uniform=True)  # random
x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + t + 3)*x + 2*t^2 + 3
sage: a.left_irreducible_divisor(uniform=True)  # random
x^3 + (2*t^2 + t + 4)*x^2 + (2*t^2 + 4*t + 4)*x + 2*t + 3
sage: a.left_irreducible_divisor(uniform=True)  # random
x^3 + (t^2 + t + 2)*x^2 + (3*t^2 + t)*x + 2*t + 1

a.left_irreducible_divisor(uniform=True)  # random
a.left_irreducible_divisor(uniform=True)  # random
a.left_irreducible_divisor(uniform=True)  # random

By convention, the zero skew polynomial has no irreducible divisor:

sage: S(0).left_irreducible_divisor()
Traceback (most recent call last):
...
ValueError: 0 has no irreducible divisor

S(0).left_irreducible_divisor()

left_irreducible_divisors()#

Return an iterator over all irreducible monic left divisors of this skew polynomial.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^4 + 2*t*x^3 + 3*t^2*x^2 + (t^2 + t + 1)*x + 4*t + 3
sage: iter = a.left_irreducible_divisors(); iter
<...generator object at 0x...>
sage: next(iter)  # random
x + 3*t + 3
sage: next(iter)  # random
x + 4*t + 2

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^4 + 2*t*x^3 + 3*t^2*x^2 + (t^2 + t + 1)*x + 4*t + 3
iter = a.left_irreducible_divisors(); iter
next(iter)  # random
next(iter)  # random

We can use this function to build the list of all monic irreducible divisors of $a$ :

sage: leftdiv = [ d for d in a.left_irreducible_divisors() ]

leftdiv = [ d for d in a.left_irreducible_divisors() ]

Note that the algorithm is probabilistic. As a consequence, if we build again the list of left monic irreducible divisors of $a$ , we may get a different ordering:

sage: leftdiv2 = [ d for d in a.left_irreducible_divisors() ]
sage: Set(leftdiv) == Set(leftdiv2)
True

leftdiv2 = [ d for d in a.left_irreducible_divisors() ]
Set(leftdiv) == Set(leftdiv2)

right_irreducible_divisor(uniform=False)#

Return a right irreducible divisor of this skew polynomial.

INPUT:

uniform – a boolean (default: False); whether the output irreducible divisor should be uniformly distributed among all possibilities

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3

sage: dr = a.right_irreducible_divisor(); dr  # random
x^3 + (2*t^2 + t + 4)*x^2 + (4*t + 1)*x + 4*t^2 + t + 1
sage: a.is_right_divisible_by(dr)
True

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3
dr = a.right_irreducible_divisor(); dr  # random
a.is_right_divisible_by(dr)

Right divisors are cached. Hence, if we ask again for a right divisor, we will get the same answer:

sage: a.right_irreducible_divisor()  # random
x^3 + (2*t^2 + t + 4)*x^2 + (4*t + 1)*x + 4*t^2 + t + 1

a.right_irreducible_divisor()  # random

However the algorithm is probabilistic. Hence, if we first reinitialize $a$ , we may get a different answer:

sage: a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3
sage: a.right_irreducible_divisor()  # random
x^3 + (t^2 + 3*t + 4)*x^2 + (t + 2)*x + 4*t^2 + t + 1

a = x^6 + 3*t*x^5 + (3*t + 1)*x^3 + (4*t^2 + 3*t + 4)*x^2 + (t^2 + 2)*x + 4*t^2 + 3*t + 3
a.right_irreducible_divisor()  # random

We can also generate uniformly distributed irreducible monic divisors as follows:

sage: a.right_irreducible_divisor(uniform=True)  # random
x^3 + (4*t + 2)*x^2 + (2*t^2 + 2*t + 2)*x + 2*t^2 + 2
sage: a.right_irreducible_divisor(uniform=True)  # random
x^3 + (t^2 + 2)*x^2 + (3*t^2 + 1)*x + 4*t^2 + 2*t
sage: a.right_irreducible_divisor(uniform=True)  # random
x^3 + x^2 + (4*t^2 + 2*t + 4)*x + t^2 + 3

a.right_irreducible_divisor(uniform=True)  # random
a.right_irreducible_divisor(uniform=True)  # random
a.right_irreducible_divisor(uniform=True)  # random

By convention, the zero skew polynomial has no irreducible divisor:

sage: S(0).right_irreducible_divisor()
Traceback (most recent call last):
...
ValueError: 0 has no irreducible divisor

S(0).right_irreducible_divisor()

right_irreducible_divisors()#

Return an iterator over all irreducible monic right divisors of this skew polynomial.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: a = x^4 + 2*t*x^3 + 3*t^2*x^2 + (t^2 + t + 1)*x + 4*t + 3
sage: iter = a.right_irreducible_divisors(); iter
<...generator object at 0x...>
sage: next(iter)   # random
x + 2*t^2 + 4*t + 4
sage: next(iter)   # random
x + 3*t^2 + 4*t + 1

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
a = x^4 + 2*t*x^3 + 3*t^2*x^2 + (t^2 + t + 1)*x + 4*t + 3
iter = a.right_irreducible_divisors(); iter
next(iter)   # random
next(iter)   # random

We can use this function to build the list of all monic irreducible divisors of $a$ :

sage: rightdiv = [ d for d in a.right_irreducible_divisors() ]

rightdiv = [ d for d in a.right_irreducible_divisors() ]

Note that the algorithm is probabilistic. As a consequence, if we build again the list of right monic irreducible divisors of $a$ , we may get a different ordering:

sage: rightdiv2 = [ d for d in a.right_irreducible_divisors() ]
sage: rightdiv == rightdiv2
False
sage: Set(rightdiv) == Set(rightdiv2)
True

rightdiv2 = [ d for d in a.right_irreducible_divisors() ]
rightdiv == rightdiv2
Set(rightdiv) == Set(rightdiv2)

type(N)#

Return the $N$ -type of this skew polynomial (see definition below).

INPUT:

N – an irreducible polynomial in the center of the underlying skew polynomial ring

Note

The result is cached.

DEFINITION:

The $N$ -type of a skew polynomial $a$ is the Partition $(t_{0}, t_{1}, t_{2}, \dots)$ defined by

t_{0} + \dots + t_{i} = \frac{\deg g c d (a, N^{i})}{\deg N},

where $\deg N$ is the degree of $N$ considered as an element in the center.

This notion has an important mathematical interest because it corresponds to the Jordan type of the $N$ -typical part of the associated Galois representation.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: S.<x> = k['x',Frob]
sage: Z = S.center(); x3 = Z.gen()

sage: a = x^4 + x^3 + (4*t^2 + 4)*x^2 + (t^2 + 2)*x + 4*t^2
sage: N = x3^2 + x3 + 1
sage: a.type(N)
[1]
sage: N = x3 + 1
sage: a.type(N)
[2]

sage: a = x^3 + (3*t^2 + 1)*x^2 + (3*t^2 + t + 1)*x + t + 1
sage: N = x3 + 1
sage: a.type(N)
[2, 1]

k.<t> = GF(5^3)
Frob = k.frobenius_endomorphism()
S.<x> = k['x',Frob]
Z = S.center(); x3 = Z.gen()
a = x^4 + x^3 + (4*t^2 + 4)*x^2 + (t^2 + 2)*x + 4*t^2
N = x3^2 + x3 + 1
a.type(N)
N = x3 + 1
a.type(N)
a = x^3 + (3*t^2 + 1)*x^2 + (3*t^2 + t + 1)*x + t + 1
N = x3 + 1
a.type(N)

If $N$ does not divide the reduced map of $a$ , the type is empty:

sage: N = x3 + 2
sage: a.type(N)
[]

N = x3 + 2
a.type(N)

If $a = N$ , the type is just $[r]$ where $r$ is the order of the twisting morphism Frob:

sage: N = x3^2 + x3 + 1
sage: S(N).type(N)
[3]

N = x3^2 + x3 + 1
S(N).type(N)

$N$ must be irreducible:

sage: N = (x3 + 1) * (x3 + 2)
sage: a.type(N)
Traceback (most recent call last):
...
ValueError: N is not irreducible

N = (x3 + 1) * (x3 + 2)
a.type(N)