Improving the Berlekamp Algorithm for Binomials x n  − a

Access this Article

Abstract

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.

Journal

  • Lecture Notes in Computer Science

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

    Springer Berlin

Codes

  • NII Article ID (NAID)
    120004397539
  • Text Lang
    ENG
  • Article Type
    journal article
  • ISSN
    0302-9743
  • Data Source
    IR 
Page Top