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

Ryuichi Harasawa; Yutaka Sueyoshi; Aichi Kudo; Liang Cui

Paper 2009/471

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

Ryuichi Harasawa, Yutaka Sueyoshi, Aichi Kudo, and 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 PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: factorization Berlekamp algorithm binomial
Contact author(s): harasawa @ cis nagasaki-u ac jp
History: 2009-09-26: received
Short URL: https://ia.cr/2009/471
License: CC BY

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}
}