Classifying Costas polynomials over extension fields
Let $q = p^r$ with $p$ prime and $r \ge 2$. A Costas polynomial over $\mathbb{F}_q$ is a function $f : \mathbb{F}_q \to \mathbb{F}_q$ with $f(0) = 0$ such that $x \mapsto f(dx) - f(x)$ is a permutation of $\mathbb{F}_q$ for every $d \in \mathbb{F}_q \setminus \{1\}$. Over a prime field these functions correspond to circular Costas sequences. Muratović-Ribić, Pott, Thomson and Wang proved that every monic Costas polynomial over a prime field $\mathbb{F}_p$ is a permutation monomial $x^s$, a conjecture of Golomb and Moreno in equivalent form, and that $L(x^s)$ is a Costas polynomial over $\mathbb{F}_q$ whenever $\gcd(s, q-1) = 1$ and $L$ is a linearized permutation polynomial. Torres and Rubio proved the converse for shifting Costas polynomials, those for which every $d \ne 1$ admits $a \ne 0$ with $f(dx) - f(x) = f(ax)$ for all $x$. Muratović-Ribić and Balašev-Samarski recast the question in terms of orthomorphisms and verified by computer that for $q \le 30$ every Costas polynomial has the form $L(x^s)$.
Problem. For every such $q$, must every Costas polynomial $f$ over $\mathbb{F}_q$ satisfy $f(x) = L(x^s)$ for all $x \in \mathbb{F}_q$, for some positive integer $s$ with $\gcd(s, q-1) = 1$ and some invertible $\mathbb{F}_p$-linear map $L : \mathbb{F}_q \to \mathbb{F}_q$? Equivalently, representing functions by polynomials modulo $x^q - x$, is every Costas polynomial a permutation monomial followed by a linearized permutation polynomial $L(x) = \sum_{j=0}^{r-1} a_j x^{p^j}$?
Source: Muratović-Ribić, Pott, Thomson and Wang (2015), Conjecture 4.4, for every finite field; stated for proper extension fields by AIM — Open Applied Problems, the prime-field case being their Theorem 3.4.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NT — Number Theory
- Secondary
- CO, IT
- Keywords
- AIM Open Applied Problems, Costas polynomials, finite fields, permutation polynomials
References
@incollection{muratovicribic2015,
author = {Muratovi{\'c}-Ribi{\'c}, Amela and Pott, Alexander and Thomson, David and Wang, Qiang},
title = {On the characterization of a semi-multiplicative analogue of planar functions over finite fields},
booktitle = {Topics in Finite Fields},
editor = {Kyureghyan, Gohar and Mullen, Gary L. and Pott, Alexander},
series = {Contemp. Math.},
volume = {632},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = {2015},
pages = {317--325},
doi = {10.1090/conm/632/12635},
}
@article{golomb1996,
author = {Golomb, Solomon W. and Moreno, Oscar},
title = {On periodicity properties of {C}ostas arrays and a conjecture on permutation polynomials},
journal = {IEEE Trans. Inform. Theory},
volume = {42},
number = {6},
year = {1996},
pages = {2252--2253},
doi = {10.1109/18.556616},
}
@article{rubio2023,
author = {Torres, Jaziel and Rubio, Ivelisse},
title = {Circular {C}ostas maps: a multidimensional analog of circular {C}ostas sequences},
journal = {Cryptogr. Commun.},
volume = {15},
number = {5},
year = {2023},
pages = {941--958},
doi = {10.1007/s12095-023-00654-2},
eprint = {2210.16661},
archivePrefix = {arXiv},
}
@misc{muratovicribic2026,
author = {Muratovi{\'c}-Ribi{\'c}, Amela and Bala{\v{s}}ev-Samarski, Aleksandar},
title = {Note on the equivalence of {C}ostas polynomials and orthomorphisms},
year = {2026},
eprint = {2606.07097},
archivePrefix = {arXiv},
}
@misc{aim-costas-polynomial,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Classifying Costas polynomials over extension fields}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/632-costas-polynomial.md},
note = {Entry 632 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00338, "Classifying Costas polynomials over extension fields", clopen.solutions.