Paper 2019/307
Solving $x^{2^k+1}+x+a=0$ in $\mathbb{F}_{2^n}$ with $\gcd(n,k)=1$
Kwang Ho Kim and Sihem Mesnager
Abstract
Let $N_a$ be the number of solutions to the equation $x^{2^k+1}+x+a=0$ in $\mathbb F_{n}$ where $\gcd(k,n)=1$. In 2004, by Bluher it was known that possible values of $N_a$ are only 0, 1 and 3. In 2008, Helleseth and Kholosha have got criteria for $N_a=1$ and an explicit expression of the unique solution when $\gcd(k,n)=1$. In 2014, Bracken, Tan and Tan presented a criterion for $N_a=0$ when $n$ is even and $\gcd(k,n)=1$. This paper completely solves this equation $x^{2^k+1}+x+a=0$ with only condition $\gcd(n,k)=1$. We explicitly calculate all possible zeros in $\mathbb F_{n}$ of $P_a(x)$. New criterion for which $a$, $N_a$ is equal to $0$, $1$ or $3$ is a by-product of our result.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Muller-Cohen-Matthewspolynomials Dickson polynomialZeros of polynomialIrreducible polynomials
- Contact author(s)
- smesnager @ univ-paris8 fr
- History
- 2019-03-20: received
- Short URL
- https://ia.cr/2019/307
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/307,
author = {Kwang Ho Kim and Sihem Mesnager},
title = {Solving $x^{2^k+1}+x+a=0$ in $\mathbb{F}_{2^n}$ with $\gcd(n,k)=1$},
howpublished = {Cryptology ePrint Archive, Paper 2019/307},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/307}},
url = {https://eprint.iacr.org/2019/307}
}
