HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Standard Lattices of Compatibly Embedded Finite Fields

Abstract : Lattices of compatibly embedded finite fields are useful in computer algebra systems for managing many extensions of a finite field F_p at once. They can also be used to represent the algebraic closure F̄_p , and to represent all finite fields in a standard manner. The most well known constructions are Conway polynomials, and the Bosma–Cannon–Steel framework used in Magma. In this work, leveraging the theory of the Lenstra-Allombert isomorphism algorithm, we generalize both at the same time. Compared to Conway polynomials, our construction defines a much larger set of field extensions from a small pre-computed table; however it is provably as inefficient as Conway polynomials if one wants to represent all field extensions, and thus yields no asymptotic improvement for representing F̄_p . Compared to Bosma–Cannon–Steel lattices, it is considerably more efficient both in computation time and storage: all algorithms have at worst quadratic complexity, and storage is linear in the number of represented field extensions and their degrees. Our implementation written in C/Flint/Julia/Nemo shows that our construction in indeed practical.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02136976
Contributor : Edouard Rousseau Connect in order to contact the contributor
Submitted on : Wednesday, May 22, 2019 - 3:24:08 PM
Last modification on : Wednesday, January 26, 2022 - 2:38:50 PM

File

gf-h90.pdf
Files produced by the author(s)

Identifiers

Citation

Luca de Feo, Hugues Randriambololona, Édouard Rousseau. Standard Lattices of Compatibly Embedded Finite Fields. ISSAC 2019, Jul 2019, Beijing, China. ⟨10.1145/3326229.3326251⟩. ⟨hal-02136976⟩

Share

Metrics

Record views

258

Files downloads

119