Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Computing isomorphisms and embeddings of finite fields
HTML articles powered by AMS MathViewer

by Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori and Éric Schost HTML | PDF
Math. Comp. 88 (2019), 1391-1426


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.

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:
  • Luca De Feo
  • Affiliation: Laboratoire de Mathématiques de Versailles, UVSQ, CNRS & Inria, Université Paris-Saclay
  • MR Author ID: 923705
  • Email:
  • Javad Doliskani
  • Affiliation: Institute for Quantum Computing, University of Waterloo
  • MR Author ID: 1041035
  • Email:
  • Jean-Pierre Flori
  • Affiliation: Agence nationale de la sécurité des systèmes d’information
  • MR Author ID: 962856
  • Email:
  • Éric Schost
  • Affiliation: Cheriton School of Computer Science, University of Waterloo
  • MR Author ID: 672551
  • Email:
  • 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
  • © Copyright 2018 Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori, and Éric Schost
  • Journal: Math. Comp. 88 (2019), 1391-1426
  • MSC (2010): Primary 13P05, 68W30
  • DOI:
  • MathSciNet review: 3904150