Polynesian Journal of Mathematics

Volume 2, Issue 2

Using Tschirnhaus transformations to find roots in quintic polynomials over 𝔽_2^m

Peter Beelen and Emil Astrup Wrisberg

Abstract:

In this article we present an algorithm to find the roots of a quintic polynomial with coefficients in ${𝔽}_{2^m}$, the finite field with $2^m$ elements, provided that the polynomial has five distinct roots in this field. The algorithm uses algebraic transformations, called Tschirnhaus transformations, to convert a given quintic polynomial into a normal form, namely $x^5+x+f$ or $x^5+f$. A table lookup is then applied to read off the roots of a polynomial in normal form, after which the roots are transformed back. The size of the lookup table is roughly $2^m∕60$, implying that for practical values of $m$ (such as $m=8,10,12$) the lookup table size is very modest (namely $7,17,71$). We also describe a polynomial $P_m\left(T\right)$ whose roots correspond to the values of $f\in {𝔽}_{q^m}$ such that the polynomial $x^{q+1}-x-f$ has $q+1$ distinct roots in ${𝔽}_{q^m},$ generalizing a result of Berlekamp, Rumsey, and Solomon from 1966.

Keywords: Root finding, quintic polynomials over a finite field, Tschirnhaus transformation.

Citation:

Peter Beelen and Emil Astrup Wrisberg. Using Tschirnhaus transformations to find roots in quintic polynomials over 𝔽_2^m. Polynesian Journal of Mathematics, Volume 2, Issue 2, Pages 1–16. (Apr. 2025) DOI: 10.69763/polyjmath.2.2

Download citation in BIBTEX format

Milestones:

Received 14 Dec 2024
Accepted 27 Mar 2025
Published 11 Apr 2025
Communicated by Gaetan Bisson

The above content is released under the terms of the Creative Commons Attribution 4.0 International license.