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

Date: received 24 Sep 2009

Contact author: harasawa at cis nagasaki-u ac jp

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20090926:033209 (All versions of this report)

Discussion forum: Show discussion | Start new discussion