Demonstrating lattices of compatibly embedded finite fields in Nemo.
Alt + r
to enter/quit slide mode if you are using the RISE extension5*8
40
A quick taste of Julia:
function foo(L)
m = L[1]
for i in 2:length(L)
if m < L[i]
m = L[i]
end
end
return m
end
foo (generic function with 1 method)
L = [2, 4, 1, 5, 7, 11, 3]
foo(L)
11
using Nemo
Welcome to Nemo version 0.14.3 Nemo comes with absolutely no warranty whatsoever
We can play with standard mathematical objects
p = 13
k, x = FiniteField(p, 4, "x")
R, T = PolynomialRing(k, "T")
P = rand(R, 3)
(5*x^3+x^2+8*x+8)*T^3+(6*x^3+9*x^2+9*x+8)*T^2+(9*x^2+5*x+10)*T+(6*x^3+12*x^2+5*x+1)
Example inspired by "On the powers of 2" [Granger, Kleinjung, Zumbrägel '14].
Let $P$ be an irreducible polynomial in $\mathbb F_{13^4}[T]$
P = T^4+(8*x^3+6*x^2+12*x+2)*T^3+(8*x^3+3*x^2+2*x+2)*T^2+(2*x^3+5*x^2+7*x+12)*T+(3*x^3+4*x^2+6*x+5)
factor(P)
1 * (T^4+(8*x^3+6*x^2+12*x+2)*T^3+(8*x^3+3*x^2+2*x+2)*T^2+(2*x^3+5*x^2+7*x+12)*T+(3*x^3+4*x^2+6*x+5))
We really want to factor it in degree $2$ factors in $\mathbb F_{13^8}[U]$:
K, y = FiniteField(p, 8, "y")
S, U = PolynomialRing(K, "U")
Q = S(P)
factor(Q)
1 * (T^2+(12*y^7+2*y^6+4*y^5+2*y^4+2*y^3+4*y^2+y+7)*T+(5*y^6+2*y^5+2*y^4+9*y^3+6*y+2)) * (T^2+(12*y^7+2*y^6+8*y^5+4*y^4+3*y^3+11*y^2+6)*T+(5*y^7+7*y^6+8*y^5+5*y^4+7*y^3+4*y^2+9*y+2))
[Brieulle, De Feo, Doliskani, Flori, Schost '17]
Two steps:
Context:
Algorithm:
Other algorithms exist:
Compute an embedding with embed
.
E, x = FiniteField(13, 6, "x")
F, y = FiniteField(13, 12, "y")
ϕ = embed(E, F)
Morphism from Finite field of degree 6 over F_13 to Finite field of degree 12 over F_13
and evaluate it
ϕ(x)
6*y^11+8*y^10+8*y^9+9*y^8+9*y^7+9*y^6+3*y^5+y^4+7*y^3+8*y^2+4
We can check that ϕ
is indeed a morphism:
a = rand(E)
b = rand(E)
ϕ(a^2 + b^7) == ϕ(a)^2 + ϕ(b)^7
true
and that the image of ϕ is in the subfield of $F$ with $13^6$ elements
ϕ(a)^(13^6) == ϕ(a), ϕ(b)^(13^6) == ϕ(b)
(true, true)
Context:
Solutions:
It works with multiple subfields!
We define some finite fields $E = \mathbb F_{p^2}$, $F = \mathbb F_{p^4}$ and $G = \mathbb F_{p^8}$.
p = 5
E, x2 = FiniteField(p, 2, "x2")
F, x4 = FiniteField(p, 4, "x4")
G, x8 = FiniteField(p, 8, "x8")
(Finite field of degree 8 over F_5, x8)
and we compute the embeddings $\phi_{E\hookrightarrow F}$, $\phi_{F\hookrightarrow G}$, $\phi_{E\hookrightarrow G}$
ϕE_F = embed(E, F)
ϕE_G = embed(E, G)
ϕF_G = embed(F, G)
Morphism from Finite field of degree 4 over F_5 to Finite field of degree 8 over F_5
Morphisms are compatible!
a = rand(E)
ϕE_G(a) == (ϕF_G ∘ ϕE_F)(a)
true
We create new finite fields
G, x6 = FiniteField(p, 6, "x6")
H, x12 = FiniteField(p, 12, "x12")
(Finite field of degree 12 over F_5, x12)
and embeddings between them
ϕE_G = embed(E, G)
ϕF_H = embed(F, H)
ϕG_H = embed(G, H)
Morphism from Finite field of degree 6 over F_5 to Finite field of degree 12 over F_5
Morphisms are still compatible!
a = rand(E)
(ϕG_H ∘ ϕE_G)(a) == (ϕF_H ∘ ϕE_F)(a)
true
We do not need to explicitly call embed
. Standard object oriented conversion also works.
k3, x3 = FiniteField(p, 3, "x3")
k24, x24 = FiniteField(p, 24, "x24")
(Finite field of degree 24 over F_5, x24)
z = k24(x3)
3*x24^23+4*x24^22+3*x24^20+4*x24^19+3*x24^18+3*x24^17+2*x24^14+4*x24^12+x24^11+4*x24^10+2*x24^9+4*x24^8+3*x24^6+3*x24^5+2*x24^4+4*x24^3+x24^2+1
z^(p^3) == z
true
k3(z)
x3
We can also compute sections of morphisms.
k7, x7 = FiniteField(p, 7, "x7")
k21, x21 = FiniteField(p, 21, "x21")
(Finite field of degree 21 over F_5, x21)
f7_21 = embed(k7, k21)
Morphism from Finite field of degree 7 over F_5 to Finite field of degree 21 over F_5
s21_7 = section(f7_21)
Section from Finite field of degree 21 over F_5 to Finite field of degree 7 over F_5
Sections give the preimage of an element if it is in the codomain of the embedding
a = rand(k7)
(s21_7 ∘ f7_21)(a) == a
true
And throw an error otherwise
s21_7(x21)
ArgumentError: not an element in the subfield of degree 7 over F_5 Stacktrace: [1] (::Nemo.FinFieldSection{FqNmodFiniteField})(::fq_nmod) at /home/erou/.julia/packages/Nemo/gWAgl/src/FinFieldsTypes.jl:49 [2] top-level scope at In[26]:1
This can also be called implicitly
k7(k21(x7))
x7
k7(x21)
ArgumentError: not an element in the subfield of degree 7 over F_5 Stacktrace: [1] (::Nemo.FinFieldSection{FqNmodFiniteField})(::fq_nmod) at /home/erou/.julia/packages/Nemo/gWAgl/src/FinFieldsTypes.jl:49 [2] (::FqNmodFiniteField)(::fq_nmod) at /home/erou/.julia/packages/Nemo/gWAgl/src/flint/fq_nmod.jl:462 [3] top-level scope at In[28]:1