Finite field morphisms#

This file provides several classes implementing:

  • embeddings between finite fields

  • Frobenius isomorphism on finite fields

EXAMPLES:

sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic

>>> from sage.all import *
>>> from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic

Construction of an embedding:

sage: k.<t> = GF(3^7)
sage: K.<T> = GF(3^21)
sage: f = FiniteFieldHomomorphism_generic(Hom(k, K)); f # random
Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T

sage: f(t) # random
T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
sage: f(t) == f.im_gens()[0]
True

>>> from sage.all import *
>>> k = GF(Integer(3)**Integer(7), names=('t',)); (t,) = k._first_ngens(1)
>>> K = GF(Integer(3)**Integer(21), names=('T',)); (T,) = K._first_ngens(1)
>>> f = FiniteFieldHomomorphism_generic(Hom(k, K)); f # random
Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T

>>> f(t) # random
T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
>>> f(t) == f.im_gens()[Integer(0)]
True

The map \(f\) has a method section which returns a partially defined map which is the inverse of \(f\) on the image of \(f\):

sage: g = f.section(); g # random
Section of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
sage: a = k.random_element()
sage: g(f(a)) == a
True
sage: g(T)
Traceback (most recent call last):
...
ValueError: T is not in the image of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: ...

>>> from sage.all import *
>>> g = f.section(); g # random
Section of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
>>> a = k.random_element()
>>> g(f(a)) == a
True
>>> g(T)
Traceback (most recent call last):
...
ValueError: T is not in the image of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: ...

There is no embedding of \(GF(5^6)\) into \(GF(5^11)\):

sage: k.<t> = GF(5^6)
sage: K.<T> = GF(5^11)
sage: FiniteFieldHomomorphism_generic(Hom(k, K))
Traceback (most recent call last):
...
ValueError: No embedding of Finite Field in t of size 5^6 into Finite Field in T of size 5^11

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(6), names=('t',)); (t,) = k._first_ngens(1)
>>> K = GF(Integer(5)**Integer(11), names=('T',)); (T,) = K._first_ngens(1)
>>> FiniteFieldHomomorphism_generic(Hom(k, K))
Traceback (most recent call last):
...
ValueError: No embedding of Finite Field in t of size 5^6 into Finite Field in T of size 5^11

Construction of Frobenius endomorphisms:

sage: k.<t> = GF(7^14)
sage: Frob = k.frobenius_endomorphism(); Frob
Frobenius endomorphism t |--> t^7 on Finite Field in t of size 7^14
sage: Frob(t)
t^7

>>> from sage.all import *
>>> k = GF(Integer(7)**Integer(14), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism(); Frob
Frobenius endomorphism t |--> t^7 on Finite Field in t of size 7^14
>>> Frob(t)
t^7

Some basic arithmetics is supported:

sage: Frob^2
Frobenius endomorphism t |--> t^(7^2) on Finite Field in t of size 7^14
sage: f = k.frobenius_endomorphism(7); f
Frobenius endomorphism t |--> t^(7^7) on Finite Field in t of size 7^14
sage: f*Frob
Frobenius endomorphism t |--> t^(7^8) on Finite Field in t of size 7^14

sage: Frob.order()
14
sage: f.order()
2

>>> from sage.all import *
>>> Frob**Integer(2)
Frobenius endomorphism t |--> t^(7^2) on Finite Field in t of size 7^14
>>> f = k.frobenius_endomorphism(Integer(7)); f
Frobenius endomorphism t |--> t^(7^7) on Finite Field in t of size 7^14
>>> f*Frob
Frobenius endomorphism t |--> t^(7^8) on Finite Field in t of size 7^14

>>> Frob.order()
14
>>> f.order()
2

Note that simplifications are made automatically:

sage: Frob^16
Frobenius endomorphism t |--> t^(7^2) on Finite Field in t of size 7^14
sage: Frob^28
Identity endomorphism of Finite Field in t of size 7^14

>>> from sage.all import *
>>> Frob**Integer(16)
Frobenius endomorphism t |--> t^(7^2) on Finite Field in t of size 7^14
>>> Frob**Integer(28)
Identity endomorphism of Finite Field in t of size 7^14

And that comparisons work:

sage: Frob == Frob^15
True
sage: Frob^14 == Hom(k, k).identity()
True

>>> from sage.all import *
>>> Frob == Frob**Integer(15)
True
>>> Frob**Integer(14) == Hom(k, k).identity()
True

AUTHOR:

  • Xavier Caruso (2012-06-29)

class sage.rings.finite_rings.hom_finite_field.FiniteFieldHomomorphism_generic[source]#

Bases: RingHomomorphism_im_gens

A class implementing embeddings between finite fields.

is_injective()[source]#

Return True since a embedding between finite fields is always injective.

EXAMPLES:

sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
sage: k.<t> = GF(3^3)
sage: K.<T> = GF(3^9)
sage: f = FiniteFieldHomomorphism_generic(Hom(k, K))
sage: f.is_injective()
True

>>> from sage.all import *
>>> from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
>>> k = GF(Integer(3)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> K = GF(Integer(3)**Integer(9), names=('T',)); (T,) = K._first_ngens(1)
>>> f = FiniteFieldHomomorphism_generic(Hom(k, K))
>>> f.is_injective()
True
is_surjective()[source]#

Return True if this embedding is surjective (and hence an isomorphism.

EXAMPLES:

sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
sage: k.<t> = GF(3^3)
sage: K.<T> = GF(3^9)
sage: f = FiniteFieldHomomorphism_generic(Hom(k, K))
sage: f.is_surjective()
False
sage: g = FiniteFieldHomomorphism_generic(Hom(k, k))
sage: g.is_surjective()
True

>>> from sage.all import *
>>> from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
>>> k = GF(Integer(3)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> K = GF(Integer(3)**Integer(9), names=('T',)); (T,) = K._first_ngens(1)
>>> f = FiniteFieldHomomorphism_generic(Hom(k, K))
>>> f.is_surjective()
False
>>> g = FiniteFieldHomomorphism_generic(Hom(k, k))
>>> g.is_surjective()
True
section()[source]#

Return the inverse of this embedding.

It is a partially defined map whose domain is the codomain of the embedding, but which is only defined on the image of the embedding.

EXAMPLES:

sage: from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
sage: k.<t> = GF(3^7)
sage: K.<T> = GF(3^21)
sage: f = FiniteFieldHomomorphism_generic(Hom(k, K))
sage: g = f.section(); g # random
Section of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
sage: a = k.random_element()
sage: b = k.random_element()
sage: g(f(a) + f(b)) == a + b
True
sage: g(T)
Traceback (most recent call last):
...
ValueError: T is not in the image of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: ...

>>> from sage.all import *
>>> from sage.rings.finite_rings.hom_finite_field import FiniteFieldHomomorphism_generic
>>> k = GF(Integer(3)**Integer(7), names=('t',)); (t,) = k._first_ngens(1)
>>> K = GF(Integer(3)**Integer(21), names=('T',)); (T,) = K._first_ngens(1)
>>> f = FiniteFieldHomomorphism_generic(Hom(k, K))
>>> g = f.section(); g # random
Section of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: t |--> T^20 + 2*T^18 + T^16 + 2*T^13 + T^9 + 2*T^8 + T^7 + T^6 + T^5 + T^3 + 2*T^2 + T
>>> a = k.random_element()
>>> b = k.random_element()
>>> g(f(a) + f(b)) == a + b
True
>>> g(T)
Traceback (most recent call last):
...
ValueError: T is not in the image of Ring morphism:
  From: Finite Field in t of size 3^7
  To:   Finite Field in T of size 3^21
  Defn: ...
class sage.rings.finite_rings.hom_finite_field.FrobeniusEndomorphism_finite_field[source]#

Bases: FrobeniusEndomorphism_generic

A class implementing Frobenius endomorphisms on finite fields.

fixed_field()[source]#

Return the fixed field of self.

OUTPUT:

  • a tuple \((K, e)\), where \(K\) is the subfield of the domain consisting of elements fixed by self and \(e\) is an embedding of \(K\) into the domain.

Note

The name of the variable used for the subfield (if it is not a prime subfield) is suffixed by _fixed.

EXAMPLES:

sage: k.<t> = GF(5^6)
sage: f = k.frobenius_endomorphism(2)
sage: kfixed, embed = f.fixed_field()
sage: kfixed
Finite Field in t_fixed of size 5^2
sage: embed # random
Ring morphism:
  From: Finite Field in t_fixed of size 5^2
  To:   Finite Field in t of size 5^6
  Defn: t_fixed |--> 4*t^5 + 2*t^4 + 4*t^2 + t

sage: tfixed = kfixed.gen()
sage: embed(tfixed) # random
4*t^5 + 2*t^4 + 4*t^2 + t
sage: embed(tfixed) == embed.im_gens()[0]
True

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(6), names=('t',)); (t,) = k._first_ngens(1)
>>> f = k.frobenius_endomorphism(Integer(2))
>>> kfixed, embed = f.fixed_field()
>>> kfixed
Finite Field in t_fixed of size 5^2
>>> embed # random
Ring morphism:
  From: Finite Field in t_fixed of size 5^2
  To:   Finite Field in t of size 5^6
  Defn: t_fixed |--> 4*t^5 + 2*t^4 + 4*t^2 + t

>>> tfixed = kfixed.gen()
>>> embed(tfixed) # random
4*t^5 + 2*t^4 + 4*t^2 + t
>>> embed(tfixed) == embed.im_gens()[Integer(0)]
True
inverse()[source]#

Return the inverse of this Frobenius endomorphism.

EXAMPLES:

sage: k.<a> = GF(7^11)
sage: f = k.frobenius_endomorphism(5)
sage: (f.inverse() * f).is_identity()
True

>>> from sage.all import *
>>> k = GF(Integer(7)**Integer(11), names=('a',)); (a,) = k._first_ngens(1)
>>> f = k.frobenius_endomorphism(Integer(5))
>>> (f.inverse() * f).is_identity()
True
is_identity()[source]#

Return True if this morphism is the identity morphism.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: Frob.is_identity()
False
sage: (Frob^3).is_identity()
True

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> Frob.is_identity()
False
>>> (Frob**Integer(3)).is_identity()
True
is_injective()[source]#

Return True since any power of the Frobenius endomorphism over a finite field is always injective.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: Frob.is_injective()
True

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> Frob.is_injective()
True
is_surjective()[source]#

Return True since any power of the Frobenius endomorphism over a finite field is always surjective.

EXAMPLES:

sage: k.<t> = GF(5^3)
sage: Frob = k.frobenius_endomorphism()
sage: Frob.is_surjective()
True

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(3), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> Frob.is_surjective()
True
order()[source]#

Return the order of this endomorphism.

EXAMPLES:

sage: k.<t> = GF(5^12)
sage: Frob = k.frobenius_endomorphism()
sage: Frob.order()
12
sage: (Frob^2).order()
6
sage: (Frob^9).order()
4

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(12), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> Frob.order()
12
>>> (Frob**Integer(2)).order()
6
>>> (Frob**Integer(9)).order()
4
power()[source]#

Return an integer \(n\) such that this endomorphism is the \(n\)-th power of the absolute (arithmetic) Frobenius.

EXAMPLES:

sage: k.<t> = GF(5^12)
sage: Frob = k.frobenius_endomorphism()
sage: Frob.power()
1
sage: (Frob^9).power()
9
sage: (Frob^13).power()
1

>>> from sage.all import *
>>> k = GF(Integer(5)**Integer(12), names=('t',)); (t,) = k._first_ngens(1)
>>> Frob = k.frobenius_endomorphism()
>>> Frob.power()
1
>>> (Frob**Integer(9)).power()
9
>>> (Frob**Integer(13)).power()
1
class sage.rings.finite_rings.hom_finite_field.SectionFiniteFieldHomomorphism_generic[source]#

Bases: Section

A class implementing sections of embeddings between finite fields.