Paper 2019/560

Solutions of $x^{q^k}+\cdots+x^{q}+x=a$ in $GF(2^n)$

Kwang Ho Kim, Jong Hyok Choe, Dok Nam Lee, Dae Song Go, and Sihem Mesnager

Abstract

Though it is well known that the roots of any affine polynomial over finite field can be computed by a system of linear equations by using a normal base of the field, such solving approach appears to be difficult to apply when the field is fairly large. Thus, it may be of great interest to find explicit representation of the solutions independently of the field base. This was previously done only for quadratic equations over binary finite field. This paper gives explicit representation of solutions for much wider class of affine polynomials over binary prime field.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Linear equationBinary finite fieldZeros of polynomialsIrreducible polynomials.
Contact author(s)
smesnager @ univ-paris8 fr
History
2019-05-25: received
Short URL
https://ia.cr/2019/560
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/560,
      author = {Kwang Ho Kim and Jong Hyok Choe and Dok Nam Lee and Dae Song Go and Sihem Mesnager},
      title = {Solutions of $x^{q^k}+\cdots+x^{q}+x=a$ in $GF(2^n)$},
      howpublished = {Cryptology ePrint Archive, Paper 2019/560},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/560}},
      url = {https://eprint.iacr.org/2019/560}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.