Improving the Berlekamp algorithm for binomials \boldmath$x^{n} - a$

Ryuichi Harasawa; Yutaka Sueyoshi; Aichi Kudo; Liang Cui

Paper 2009/471 Original: eprint.iacr.org/2009/471 ↗

Improving the Berlekamp algorithm for binomials \boldmath$x^{n} - a$

Ryuichi Harasawa

Yutaka Sueyoshi

Aichi Kudo

Liang Cui

Abstract

In this paper, we describe an improvement of the Berlekamp algorithm for binomials $x^n - a$ over prime fields $\mathbb{F}_{p}$. We implement the proposed method for various cases and compare the results with the original Berlekamp method. The proposed method can be extended easily to the case where the base field is not a prime field.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
History: 2009-09-26: last updated; 2009-09-26: published
Short URL: https://ia.cr/2009/471
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2009/471,
      author = {Ryuichi Harasawa and Yutaka Sueyoshi and Aichi Kudo and Liang Cui},
      title = {Improving the Berlekamp algorithm for binomials \boldmath$x^{n} - a$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/471},
      year = {2009},
      url = {https://eprint.iacr.org/2009/471}
}