Algebraic closures of finite fields

Let \(\Bold{F}\) be a finite field, and let \(\overline{\Bold{F}}\) be an algebraic closure of \(\Bold{F}\); this is unique up to (non-canonical) isomorphism. For every \(n\ge 1\), there is a unique subfield \(\Bold{F}_n\) of \(\overline{\Bold{F}}\) such that \(\Bold{F}\subset\Bold{F}_n\) and \([\Bold{F}_n:\Bold{F}]=n\).

In Sage, algebraic closures of finite fields are implemented using compatible systems of finite fields. The resulting Sage object keeps track of a finite lattice of the subfields \(\Bold{F}_n\) and the embeddings between them. This lattice is extended as necessary.

The Sage class corresponding to \(\overline{\Bold{F}}\) can be constructed from the finite field \(\Bold{F}\) by using the algebraic_closure() method.

The Sage class for elements of \(\overline{\Bold{F}}\) is AlgebraicClosureFiniteFieldElement. Such an element is represented as an element of one of the \(\Bold{F}_n\). This means that each element \(x\in\Bold{F}\) has infinitely many different representations, one for each \(n\) such that \(x\) is in \(\Bold{F}_n\).

Note

Only prime finite fields are currently accepted as base fields for algebraic closures. To obtain an algebraic closure of a non-prime finite field \(\Bold{F}\), take an algebraic closure of the prime field of \(\Bold{F}\) and embed \(\Bold{F}\) into this.

Algebraic closures of finite fields are currently implemented using (pseudo-)Conway polynomials; see AlgebraicClosureFiniteField_pseudo_conway and the module conway_polynomials. Other implementations may be added by creating appropriate subclasses of AlgebraicClosureFiniteField_generic.

In the current implementation, algebraic closures do not satisfy the unique parent condition. Moreover, there is no coercion map between different algebraic closures of the same finite field. There is a conceptual reason for this, namely that the definition of pseudo-Conway polynomials only determines an algebraic closure up to non-unique isomorphism. This means in particular that different algebraic closures, and their respective elements, never compare equal.

AUTHORS:

  • Peter Bruin (August 2013): initial version

  • Vincent Delecroix (November 2013): additional methods

sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField(base_ring, name, category=None, implementation=None, **kwds)[source]

Construct an algebraic closure of a finite field.

The recommended way to use this functionality is by calling the algebraic_closure() method of the finite field.

Note

Algebraic closures of finite fields in Sage do not have the unique representation property, because they are not determined up to unique isomorphism by their defining data.

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F = GF(2).algebraic_closure()
sage: F1 = AlgebraicClosureFiniteField(GF(2), 'z')
sage: F1 is F
False

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> F = GF(Integer(2)).algebraic_closure()
>>> F1 = AlgebraicClosureFiniteField(GF(Integer(2)), 'z')
>>> F1 is F
False

In the pseudo-Conway implementation, non-identical instances never compare equal:

sage: F1 == F
False
sage: loads(dumps(F)) == F
False

>>> from sage.all import *
>>> F1 == F
False
>>> loads(dumps(F)) == F
False

This is to ensure that the result of comparing two instances cannot change with time.

class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteFieldElement(parent, value)[source]

Bases: FieldElement

Element of an algebraic closure of a finite field.

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: F.gen(2)
z2
sage: type(F.gen(2))
<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category.element_class'>

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> F.gen(Integer(2))
z2
>>> type(F.gen(Integer(2)))
<class 'sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway_with_category.element_class'>
as_finite_field_element(minimal=False)[source]

Return self as a finite field element.

INPUT:

  • minimal – boolean (default: False); if True, always return the smallest subfield containing self

OUTPUT:

  • a triple (field, element, morphism) where field is a finite field, element an element of field and morphism a morphism from field to self.parent().

EXAMPLES:

sage: F = GF(3).algebraic_closure('t')
sage: t = F.gen(5)
sage: t.as_finite_field_element()
(Finite Field in t5 of size 3^5,
 t5,
 Ring morphism:
  From: Finite Field in t5 of size 3^5
  To:   Algebraic closure of Finite Field of size 3
  Defn: t5 |--> t5)

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure('t')
>>> t = F.gen(Integer(5))
>>> t.as_finite_field_element()
(Finite Field in t5 of size 3^5,
 t5,
 Ring morphism:
  From: Finite Field in t5 of size 3^5
  To:   Algebraic closure of Finite Field of size 3
  Defn: t5 |--> t5)

By default, field is not necessarily minimal. We can force it to be minimal using the minimal option:

sage: s = t + 1 - t
sage: s.as_finite_field_element()[0]
Finite Field in t5 of size 3^5
sage: s.as_finite_field_element(minimal=True)[0]
Finite Field of size 3

>>> from sage.all import *
>>> s = t + Integer(1) - t
>>> s.as_finite_field_element()[Integer(0)]
Finite Field in t5 of size 3^5
>>> s.as_finite_field_element(minimal=True)[Integer(0)]
Finite Field of size 3

This also works when the element has to be converted between two non-trivial finite subfields (see Issue #16509):

sage: K = GF(5).algebraic_closure()
sage: z = K.gen(5) - K.gen(5) + K.gen(2)
sage: z.as_finite_field_element(minimal=True)
(Finite Field in z2 of size 5^2, z2, Ring morphism:
   From: Finite Field in z2 of size 5^2
   To:   Algebraic closure of Finite Field of size 5
   Defn: z2 |--> z2)

>>> from sage.all import *
>>> K = GF(Integer(5)).algebraic_closure()
>>> z = K.gen(Integer(5)) - K.gen(Integer(5)) + K.gen(Integer(2))
>>> z.as_finite_field_element(minimal=True)
(Finite Field in z2 of size 5^2, z2, Ring morphism:
   From: Finite Field in z2 of size 5^2
   To:   Algebraic closure of Finite Field of size 5
   Defn: z2 |--> z2)

There are automatic coercions between the various subfields:

sage: a = K.gen(2) + 1
sage: _,b,_ = a.as_finite_field_element()
sage: K4 = K.subfield(4)[0]
sage: K4(b)
z4^3 + z4^2 + z4 + 4
sage: b.minimal_polynomial() == K4(b).minimal_polynomial()
True
sage: K(K4(b)) == K(b)
True

>>> from sage.all import *
>>> a = K.gen(Integer(2)) + Integer(1)
>>> _,b,_ = a.as_finite_field_element()
>>> K4 = K.subfield(Integer(4))[Integer(0)]
>>> K4(b)
z4^3 + z4^2 + z4 + 4
>>> b.minimal_polynomial() == K4(b).minimal_polynomial()
True
>>> K(K4(b)) == K(b)
True

You can also use the inclusions that are implemented at the level of the algebraic closure:

sage: f = K.inclusion(2,4); f
Ring morphism:
  From: Finite Field in z2 of size 5^2
  To:   Finite Field in z4 of size 5^4
  Defn: z2 |--> z4^3 + z4^2 + z4 + 3
sage: f(b)
z4^3 + z4^2 + z4 + 4

>>> from sage.all import *
>>> f = K.inclusion(Integer(2),Integer(4)); f
Ring morphism:
  From: Finite Field in z2 of size 5^2
  To:   Finite Field in z4 of size 5^4
  Defn: z2 |--> z4^3 + z4^2 + z4 + 3
>>> f(b)
z4^3 + z4^2 + z4 + 4
change_level(n)[source]

Return a representation of self as an element of the subfield of degree \(n\) of the parent, if possible.

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: z = F.gen(4)
sage: (z^10).change_level(6)
2*z6^5 + 2*z6^3 + z6^2 + 2*z6 + 2
sage: z.change_level(6)
Traceback (most recent call last):
...
ValueError: z4 is not in the image of Ring morphism:
  From: Finite Field in z2 of size 3^2
  To:   Finite Field in z4 of size 3^4
  Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1

sage: a = F(1).change_level(3); a
1
sage: a.change_level(2)
1
sage: F.gen(3).change_level(1)
Traceback (most recent call last):
...
ValueError: z3 is not in the image of Ring morphism:
  From: Finite Field of size 3
  To:   Finite Field in z3 of size 3^3
  Defn: 1 |--> 1

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> z = F.gen(Integer(4))
>>> (z**Integer(10)).change_level(Integer(6))
2*z6^5 + 2*z6^3 + z6^2 + 2*z6 + 2
>>> z.change_level(Integer(6))
Traceback (most recent call last):
...
ValueError: z4 is not in the image of Ring morphism:
  From: Finite Field in z2 of size 3^2
  To:   Finite Field in z4 of size 3^4
  Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1

>>> a = F(Integer(1)).change_level(Integer(3)); a
1
>>> a.change_level(Integer(2))
1
>>> F.gen(Integer(3)).change_level(Integer(1))
Traceback (most recent call last):
...
ValueError: z3 is not in the image of Ring morphism:
  From: Finite Field of size 3
  To:   Finite Field in z3 of size 3^3
  Defn: 1 |--> 1
is_square()[source]

Return True if self is a square.

This always returns True.

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: F.gen(2).is_square()
True

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> F.gen(Integer(2)).is_square()
True
minimal_polynomial()[source]

Return the minimal polynomial of self over the prime field.

EXAMPLES:

sage: F = GF(11).algebraic_closure()
sage: F.gen(3).minpoly()
x^3 + 2*x + 9

>>> from sage.all import *
>>> F = GF(Integer(11)).algebraic_closure()
>>> F.gen(Integer(3)).minpoly()
x^3 + 2*x + 9
minpoly()[source]

Return the minimal polynomial of self over the prime field.

EXAMPLES:

sage: F = GF(11).algebraic_closure()
sage: F.gen(3).minpoly()
x^3 + 2*x + 9

>>> from sage.all import *
>>> F = GF(Integer(11)).algebraic_closure()
>>> F.gen(Integer(3)).minpoly()
x^3 + 2*x + 9
multiplicative_order()[source]

Return the multiplicative order of self.

EXAMPLES:

sage: K = GF(7).algebraic_closure()
sage: K.gen(5).multiplicative_order()
16806
sage: (K.gen(1) + K.gen(2) + K.gen(3)).multiplicative_order()
7353

>>> from sage.all import *
>>> K = GF(Integer(7)).algebraic_closure()
>>> K.gen(Integer(5)).multiplicative_order()
16806
>>> (K.gen(Integer(1)) + K.gen(Integer(2)) + K.gen(Integer(3))).multiplicative_order()
7353
nth_root(n)[source]

Return an \(n\)-th root of self.

EXAMPLES:

sage: F = GF(5).algebraic_closure()
sage: t = F.gen(2) + 1
sage: s = t.nth_root(15); s
4*z6^5 + 3*z6^4 + 2*z6^3 + 2*z6^2 + 4
sage: s**15 == t
True

>>> from sage.all import *
>>> F = GF(Integer(5)).algebraic_closure()
>>> t = F.gen(Integer(2)) + Integer(1)
>>> s = t.nth_root(Integer(15)); s
4*z6^5 + 3*z6^4 + 2*z6^3 + 2*z6^2 + 4
>>> s**Integer(15) == t
True

Todo

This function could probably be made faster.

pth_power(k=1)[source]

Return the \(p^k\)-th power of self, where \(p\) is the characteristic of self.parent().

EXAMPLES:

sage: K = GF(13).algebraic_closure('t')
sage: t3 = K.gen(3)
sage: s = 1 + t3 + t3**2
sage: s.pth_power()
10*t3^2 + 6*t3
sage: s.pth_power(2)
2*t3^2 + 6*t3 + 11
sage: s.pth_power(3)
t3^2 + t3 + 1
sage: s.pth_power(3).parent() is K
True

>>> from sage.all import *
>>> K = GF(Integer(13)).algebraic_closure('t')
>>> t3 = K.gen(Integer(3))
>>> s = Integer(1) + t3 + t3**Integer(2)
>>> s.pth_power()
10*t3^2 + 6*t3
>>> s.pth_power(Integer(2))
2*t3^2 + 6*t3 + 11
>>> s.pth_power(Integer(3))
t3^2 + t3 + 1
>>> s.pth_power(Integer(3)).parent() is K
True
pth_root(k=1)[source]

Return the unique \(p^k\)-th root of self, where \(p\) is the characteristic of self.parent().

EXAMPLES:

sage: K = GF(13).algebraic_closure('t')
sage: t3 = K.gen(3)
sage: s = 1 + t3 + t3**2
sage: s.pth_root()
2*t3^2 + 6*t3 + 11
sage: s.pth_root(2)
10*t3^2 + 6*t3
sage: s.pth_root(3)
t3^2 + t3 + 1
sage: s.pth_root(2).parent() is K
True

>>> from sage.all import *
>>> K = GF(Integer(13)).algebraic_closure('t')
>>> t3 = K.gen(Integer(3))
>>> s = Integer(1) + t3 + t3**Integer(2)
>>> s.pth_root()
2*t3^2 + 6*t3 + 11
>>> s.pth_root(Integer(2))
10*t3^2 + 6*t3
>>> s.pth_root(Integer(3))
t3^2 + t3 + 1
>>> s.pth_root(Integer(2)).parent() is K
True
sqrt(all=False)[source]

Return a square root of self.

If the optional keyword argument all is set to True, return a list of all square roots of self instead.

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: F.gen(2).sqrt()
z4^3 + z4 + 1
sage: F.gen(2).sqrt(all=True)
[z4^3 + z4 + 1, 2*z4^3 + 2*z4 + 2]
sage: (F.gen(2)^2).sqrt()
z2
sage: (F.gen(2)^2).sqrt(all=True)
[z2, 2*z2]

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> F.gen(Integer(2)).sqrt()
z4^3 + z4 + 1
>>> F.gen(Integer(2)).sqrt(all=True)
[z4^3 + z4 + 1, 2*z4^3 + 2*z4 + 2]
>>> (F.gen(Integer(2))**Integer(2)).sqrt()
z2
>>> (F.gen(Integer(2))**Integer(2)).sqrt(all=True)
[z2, 2*z2]
class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_generic(base_ring, name, category=None)[source]

Bases: Field

Algebraic closure of a finite field.

Element[source]

alias of AlgebraicClosureFiniteFieldElement

algebraic_closure()[source]

Return an algebraic closure of self.

This always returns self.

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F = AlgebraicClosureFiniteField(GF(5), 'z')
sage: F.algebraic_closure() is F
True

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> F = AlgebraicClosureFiniteField(GF(Integer(5)), 'z')
>>> F.algebraic_closure() is F
True
characteristic()[source]

Return the characteristic of self.

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: p = next_prime(1000)
sage: F = AlgebraicClosureFiniteField(GF(p), 'z')
sage: F.characteristic() == p
True

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> p = next_prime(Integer(1000))
>>> F = AlgebraicClosureFiniteField(GF(p), 'z')
>>> F.characteristic() == p
True
gen(n)[source]

Return the \(n\)-th generator of self.

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F = AlgebraicClosureFiniteField(GF(5), 'z')
sage: F.gen(2)
z2

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> F = AlgebraicClosureFiniteField(GF(Integer(5)), 'z')
>>> F.gen(Integer(2))
z2
gens()[source]

Return a family of generators of self.

OUTPUT:

  • a Family, indexed by the positive integers, whose \(n\)-th element is self.gen(n).

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: F = AlgebraicClosureFiniteField(GF(5), 'z')
sage: g = F.gens(); g
Lazy family (...(i))_{i in Positive integers}
sage: g[3]
z3

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> F = AlgebraicClosureFiniteField(GF(Integer(5)), 'z')
>>> g = F.gens(); g
Lazy family (...(i))_{i in Positive integers}
>>> g[Integer(3)]
z3
inclusion(m, n)[source]

Return the canonical inclusion map from the subfield of degree \(m\) to the subfield of degree \(n\).

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: F.inclusion(1, 2)
Ring morphism:
  From: Finite Field of size 3
  To:   Finite Field in z2 of size 3^2
  Defn: 1 |--> 1
sage: F.inclusion(2, 4)
Ring morphism:
  From: Finite Field in z2 of size 3^2
  To:   Finite Field in z4 of size 3^4
  Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> F.inclusion(Integer(1), Integer(2))
Ring morphism:
  From: Finite Field of size 3
  To:   Finite Field in z2 of size 3^2
  Defn: 1 |--> 1
>>> F.inclusion(Integer(2), Integer(4))
Ring morphism:
  From: Finite Field in z2 of size 3^2
  To:   Finite Field in z4 of size 3^4
  Defn: z2 |--> 2*z4^3 + 2*z4^2 + 1
ngens()[source]

Return the number of generators of self, which is infinity.

EXAMPLES:

sage: from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
sage: AlgebraicClosureFiniteField(GF(5), 'z').ngens()
+Infinity

>>> from sage.all import *
>>> from sage.rings.algebraic_closure_finite_field import AlgebraicClosureFiniteField
>>> AlgebraicClosureFiniteField(GF(Integer(5)), 'z').ngens()
+Infinity
some_elements()[source]

Return some elements of this field.

EXAMPLES:

sage: F = GF(7).algebraic_closure()
sage: F.some_elements()
(1, z2, z3 + 1)

>>> from sage.all import *
>>> F = GF(Integer(7)).algebraic_closure()
>>> F.some_elements()
(1, z2, z3 + 1)
subfield(n)[source]

Return the unique subfield of degree \(n\) of self together with its canonical embedding into self.

EXAMPLES:

sage: F = GF(3).algebraic_closure()
sage: F.subfield(1)
(Finite Field of size 3,
 Ring morphism:
   From: Finite Field of size 3
   To:   Algebraic closure of Finite Field of size 3
   Defn: 1 |--> 1)
sage: F.subfield(4)
(Finite Field in z4 of size 3^4,
 Ring morphism:
   From: Finite Field in z4 of size 3^4
   To:   Algebraic closure of Finite Field of size 3
   Defn: z4 |--> z4)

>>> from sage.all import *
>>> F = GF(Integer(3)).algebraic_closure()
>>> F.subfield(Integer(1))
(Finite Field of size 3,
 Ring morphism:
   From: Finite Field of size 3
   To:   Algebraic closure of Finite Field of size 3
   Defn: 1 |--> 1)
>>> F.subfield(Integer(4))
(Finite Field in z4 of size 3^4,
 Ring morphism:
   From: Finite Field in z4 of size 3^4
   To:   Algebraic closure of Finite Field of size 3
   Defn: z4 |--> z4)
class sage.rings.algebraic_closure_finite_field.AlgebraicClosureFiniteField_pseudo_conway(base_ring, name, category=None, lattice=None, use_database=True)[source]

Bases: WithEqualityById, AlgebraicClosureFiniteField_generic

Algebraic closure of a finite field, constructed using pseudo-Conway polynomials.

EXAMPLES:

sage: F = GF(5).algebraic_closure(implementation='pseudo_conway')
sage: F.cardinality()
+Infinity
sage: F.algebraic_closure() is F
True
sage: x = F(3).nth_root(12); x
z4^3 + z4^2 + 4*z4
sage: x**12
3

>>> from sage.all import *
>>> F = GF(Integer(5)).algebraic_closure(implementation='pseudo_conway')
>>> F.cardinality()
+Infinity
>>> F.algebraic_closure() is F
True
>>> x = F(Integer(3)).nth_root(Integer(12)); x
z4^3 + z4^2 + 4*z4
>>> x**Integer(12)
3