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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.