Improving the Berlekamp Algorithm for Binomials x n  − a

Access this Article


In this paper, we describe an improvement of the Berlekamp algorithm, a method for factoring univariate polynomials over finite fields, for binomials xn −a over finite fields Fq. More precisely, we give a deterministic algorithm for solving the equation h(x)q≡h(x) (mod xn−a) directly without applying the sweeping-out method to the corresponding coefficient matrix. We show that the factorization of binomials using the proposed method is performed in O˜, (n log q) operations in Fq if we apply a probabilistic version of the Berlekamp algorithm after the first step in which we propose an improvement. Our method is asymptotically faster than known methods in certain areas of q, n and as fast as them in other areas.


  • Lecture Notes in Computer Science

    Lecture Notes in Computer Science (7369), 225-235, 2012-07-02

    Springer Berlin


  • NII Article ID (NAID)
  • Text Lang
  • Article Type
    journal article
  • ISSN
  • Data Source
Page Top