## Cryptology ePrint Archive: Report 2009/471

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

Ryuichi Harasawa and Yutaka Sueyoshi and 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.

Category / Keywords: foundations / factorization, Berlekamp algorithm, binomial