Standard Lattices of Compatibly Embedded Finite Fields

Luca De Feo, Hugues Randriam, Édouard Rousseau

Lattices of compatibly embedded finite fields are useful in computer algebra systems for managing many extensions of a finite field $\mathbb{F}_p$ at once. They can also be used to represent the algebraic closure $\bar{\mathbb{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 $\bar{\mathbb{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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment