Standard Lattices of Compatibly Embedded Finite Fields - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Standard Lattices of Compatibly Embedded Finite Fields

Résumé

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.
Fichier principal
Vignette du fichier
gf-h90.pdf (728.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02136976 , version 1 (22-05-2019)

Identifiants

Citer

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⟩
316 Consultations
212 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More