# 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]#

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]#

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.