# Lattices of compatibly embedded finite fields in Nemo/Flint¶

Luca De Feo, Hugues Randriambololona, Édouard Rousseau

Demonstrating the newly implemented lattices of compatibly embedded finite fields in Nemo.

## Jupyter¶

In [ ]:
2^12


## Nemo and Flint¶

• Nemo is a computer algebra package for the Julia programming language [maintained by Hart, Hofmann, Fieker, Johansson, and others]
• among many things, it includes a Flint wrapper
• Flint is a number theory library for the C programming language [maintained by William Hart]

## Nemo and Flint¶

A quick taste of Julia:

In [ ]:
function foo(L)
m = L[1]
for i in 2:length(L)
if m < L[i]
m = L[i]
end
end
return m
end

In [ ]:
L = [2, 4, 1, 5, 7, 11, 17, 3]
foo(L)


## Nemo and Flint¶

In [ ]:
using Nemo


We can play with standard mathematical objects

In [ ]:
p = 13
k, x = FiniteField(p, 4, "x")
R, T = PolynomialRing(k, "T")
P = rand(R, 3)


## The embedding problem¶

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

In [ ]:
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)


We really want to factor it in degree $2$ factors in $\mathbb F_{13^8}[U]$:

In [ ]:
K, y = FiniteField(p, 8, "y")
S, U = PolynomialRing(K, "U")
Q = S(P)
factor(Q)


## The embedding problem¶

• $f$ irreducible polynomial of degree $m$ in $\mathbb F_p[X]$
• $g$ irreducible polynomial of degree $n$ in $\mathbb F_p[Y]$
• $m\;|\;n$
• $E = \mathbb F_p[X]/(f(X))$
• $F = \mathbb F_p[Y]/(g(Y))$
$E\cong \mathbb F_{p^m} \hookrightarrow F\cong \mathbb F_{p^n}$
• **Embedding problem:** how to compute the embedding from $E$ to $F$ ?

## Description and evaluation¶

[Brieulle, De Feo, Doliskani, Flori, Schost '17]

Two steps:

• Description: find $\alpha_1, \alpha_2$ such that:
• $E = \mathbb F_p(\alpha_1)$
• there exists an embedding $\phi:E\to F$ mapping $\alpha_1\mapsto\alpha_2$
• Evaluation:
• Compute $\phi(\gamma)\in F$ for $\gamma\in E$
• Test if $\delta\in\phi(E)$ for $\delta\in F$
• If $\delta\in\phi(E)$, compute $\phi^{-1}(\delta)\in E$

## Description - naive algorithm¶

Context:

• $E = \mathbb{F}_p[X]/(f)$
• $F=\mathbb{F}_p[Y]/(g)$

Algorithm:

• Find a root $\rho$ of $f$ in $F$
• $\alpha_1 = \overline X$
• $\alpha_2 = \rho$

Other algorithms exist:

• [Lenstra '91]
• [Allombert '02]
• [Rains '96]
• [Narayanan '18]

## Description - naive algorithm¶

Compute an embedding with embed.

In [ ]:
E, x = FiniteField(13, 6, "x")
F, y = FiniteField(13, 12, "y")
ϕ = embed(E, F)


and evaluate it

In [ ]:
ϕ(x)


## Some sanity checks¶

We can check that ϕ is indeed a morphism:

In [ ]:
a = rand(E)
b = rand(E)
ϕ(a^2 + b^7) == ϕ(a)^2 + ϕ(b)^7


and that the image of ϕ is in the subfield of $F$ with $13^6$ elements

In [ ]:
ϕ(a)^(13^6) == ϕ(a), ϕ(b)^(13^6) == ϕ(b)


# No!¶

## The compatibility problem¶

Assume the user wants to use many extensions of $\mathbb F_p$:

## The compatibility problem¶

Context:

• $E$, $F$, $G$ fields
• $E$ subfield of $F$ and $F$ subfield of $G$
• $\phi_{E\hookrightarrow F}$, $\phi_{F\hookrightarrow G}$, $\phi_{E\hookrightarrow G}$ embeddings
$\phi_{F\hookrightarrow G}\circ\phi_{E\hookrightarrow F}\overset{?}{=}\phi_{E\hookrightarrow G}$

## The compatibility problem¶

Solutions:

• Conway polynomials [Parker '90], [Heath, Loehr '98]
• used in Magma, Sage, PARI, ...
• only practical with small finite fields
• Bosma, Cannon and Steel framework [Bosma, Cannon, Steel '97]

## Bosma, Cannon and Steel framework¶

• Allows to work with arbitrary, user-defined finite fields
• Allows to build the embeddings in arbitrary order
• Used in MAGMA
• based on the naive algorithm

## Bosma, Cannon and Steel framework¶

• Consider $\alpha$ such that $F=\mathbb{F}_p(\alpha)$
• Take $\rho$ a root of $\phi_{E\hookrightarrow G}(\text{Minpoly}_E(\alpha))$
• Map $\alpha\mapsto\rho$

## Bosma, Cannon and Steel framework¶

It works with multiple subfields!

• Consider $\alpha$ such that $F=\mathbb{F}_p(\alpha)$
• Take $\rho$ a root of $\text{gcd}_i(\phi_{E_i\hookrightarrow G}(\text{Minpoly}_{E_i}(\alpha)))$
• Map $\alpha\mapsto\rho$

## The compatibility problem¶

We define some finite fields $E = \mathbb F_{p^2}$, $F = \mathbb F_{p^4}$ and $G = \mathbb F_{p^8}$.

In [ ]:
p = 5

E, x2 = FiniteField(p, 2, "x2")
F, x4 = FiniteField(p, 4, "x4")
G, x8 = FiniteField(p, 8, "x8")


and we compute the embeddings $\phi_{E\hookrightarrow F}$, $\phi_{F\hookrightarrow G}$, $\phi_{E\hookrightarrow G}$

In [ ]:
ϕE_F = embed(E, F)
ϕE_G = embed(E, G)
ϕF_G = embed(F, G)


## The compatibility problem¶

Morphisms are compatible!

In [ ]:
a = rand(E)
ϕE_G(a) == (ϕF_G ∘ ϕE_F)(a)


## The compatibility problem II¶

$\phi_{G\hookrightarrow H}\circ\phi_{E\hookrightarrow G}\overset{?}{=}\phi_{F\hookrightarrow H}\circ\phi_{E\hookrightarrow F}$

## The compatibility problem II¶

We create new finite fields

In [ ]:
G, x6 = FiniteField(p, 6, "x6")
H, x12 = FiniteField(p, 12, "x12")


and embeddings between them

In [ ]:
ϕE_G = embed(E, G)
ϕF_H = embed(F, H)
ϕG_H = embed(G, H)


## The compatibility problem II¶

Morphisms are still compatible!

In [ ]:
a = rand(E)
(ϕG_H ∘ ϕE_G)(a) == (ϕF_H ∘ ϕE_F)(a)


## Implicit conversion¶

We do not need to explicitly call embed. Standard object oriented conversion also works.

In [ ]:
k3, x3 = FiniteField(p, 3, "x3")
k24, x24 = FiniteField(p, 24, "x24")

In [ ]:
z = k24(x3)

In [ ]:
z^(p^3) == z

In [ ]:
k3(z)


## Sections¶

We can also compute sections of morphisms.

In [ ]:
k7, x7 = FiniteField(p, 7, "x7")
k21, x21 = FiniteField(p, 21, "x21")

In [ ]:
f7_21 = embed(k7, k21)

In [ ]:
s21_7 = section(f7_21)


## Sections¶

Sections give the preimage of an element if it is in the codomain of the embedding

In [ ]:
a = rand(k7)
(s21_7 ∘ f7_21)(a) == a


And throw an error otherwise

In [ ]:
s21_7(x21)


## Sections¶

This can also be called implicitly

In [ ]:
k7(k21(x7))

In [ ]:
k7(x21)


## Behind the scenes¶

• root finding is done by Flint (in C)
• minimal polynomials are computed by Nemo (in Julia)
• additionnal requirements of Bosma, Cannon and Steel framework are done in Nemo
• (almost) all the time is spent in root finding
• embedding evaluation is done via matrix-vector multiplication

## More features planned¶

• Vector space morphisms,
• Algorithmic improvements,
• more efficient framework using Lenstra/Allombert embedding algorithm as building block