Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

Computing isomorphisms and embeddings of finite fields


Authors: Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori and Éric Schost
Journal: Math. Comp.
MSC (2010): Primary 13P05, 68W30
DOI: https://doi.org/10.1090/mcom/3363
Published electronically: June 19, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ \mathbb{F}_q$ be a finite field. Given two irreducible polynomials $ f,g$ over $ \mathbb{F}_q$, with $ \deg f$ dividing $ \deg g$, the finite field embedding problem asks to compute an explicit description of a field embedding of $ \mathbb{F}_q[X]/f(X)$ into $ \mathbb{F}_q[Y]/g(Y)$. When $ \deg f = \deg g$, this is also known as the isomorphism problem.

This problem, a special instance of polynomial factorization, plays a central role in computer algebra software. We review previous algorithms, due to Lenstra, Allombert, Rains, and Narayanan, and propose improvements and generalizations. Our detailed complexity analysis shows that our newly proposed variants are at least as efficient as previously known algorithms, and in many cases significantly better.

We also implement most of the presented algorithms, compare them with the state of the art computer algebra software, and make the code available as an open source. Our experiments show that our new variants consistently outperform available software.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 13P05, 68W30

Retrieve articles in all journals with MSC (2010): 13P05, 68W30


Additional Information

Ludovic Brieulle
Affiliation: Laboratoire de Mathématiques de Versailles, UVSQ, CNRS, Université Paris-Saclay
Email: l.brieulle@gmail.com

Luca De Feo
Affiliation: Laboratoire de Mathématiques de Versailles, UVSQ, CNRS & Inria, Université Paris-Saclay
Email: luca.de-feo@uvsq.fr

Javad Doliskani
Affiliation: Institute for Quantum Computing, University of Waterloo
Email: javad.doliskani@uwaterloo.ca

Jean-Pierre Flori
Affiliation: Agence nationale de la sécurité des systèmes d’information
Email: jean-pierre.flori@ssi.gouv.fr

Éric Schost
Affiliation: Cheriton School of Computer Science, University of Waterloo
Email: eschost@uwaterloo.ca

DOI: https://doi.org/10.1090/mcom/3363
Received by editor(s): May 5, 2017
Received by editor(s) in revised form: July 3, 2017, and December 18, 2017
Published electronically: June 19, 2018
Article copyright: © Copyright 2018 Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori, and Éric Schost

American Mathematical Society