Jupyter Notebook TeX C++ Python Makefile Shell
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
implementation
misc
notebooks
paper
.gitignore
.gitmodules
Dockerfile
README.md

README.md

Computing isomorphisms and embeddings of finite fields

a research project in Computer Algebra

by Ludovic Brieulle, Luca De Feo, Javad Doliskani, Jean-Pierre Flori and Éric Schost.

Abstract

Let 𝔽q be a finite field. Given two irreducible polynomials f, g over 𝔽q, with deg f dividing deg g, the finite field embedding problem asks to compute an explicit description of a field embedding of 𝔽q[X]/f(X) into 𝔽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 open source. Our experiments show that our new variants consistently outperform available software.

Research paper

The research paper has been submitted for publication in AMS Mathematics of Computation.

A preprint version is available at https://arxiv.org/abs/1705.01221.

The LaTeX sources to the paper can be found in the paper folder. They are subject to the copying restriction enforced by the editor.

Software launch binder

The implementation folder contains source code for the algorithms implemented by the project. See the folder README.md for instructions on compiling and running the software on your own machine.

The notebooks folder contains Jupyter notebooks showing sample usage of the software and benchmarks. Notebooks can be statically viewed on GitHub, or executed in Binder, thus saving you the time to compile and install the software.

All source code is distributed under the MIT license.

Related material

The misc folder contains material related to the project, such as

  • conference posters,
  • presentation slides,
  • experimental data gathered on the conjecture formulated in the paper.

Contributing

We do not accept pull requests, but if you see any problem with this repository, plese open an issue.