Comparative implementations of Berlekamp's and Niederreitor's polynomial factorization algorithms
Peter Fleischmann, Peter Roelse · Cambridge University Press eBooks · 1996
New C ++ -implementations of the classical factorization algorithms for polynomials over finite fields of Berlekamp and the new ones of Niederreiter are presented. Their performances on various types of inputs are compared. Introduction The basic problem of factorizing univariate polynomials over the finite field F q has got new impulses in the past few years with a new linearization technique developed by Niederreiter in [8], [9], [10]. Unlike Berlekamp's classical approach, which uses the Frobenius fixed point algebra in A := F q [X]/(f) (where f is the polynomial to be factored), Niederreiter's method is based on the analysis of the solution space of certain differential equations in the field of rational functions F q (X). From the very beginning there have been several striking similarities between Niederreiter's and Berlekamp's algorithms in each step. Suppose for simplicity that the polynomial is monic and squarefree. Then in both algorithms a certain system of linear equations has to be set up and solved, leading to an F q - subspace S of A , whose dimension coincides with the number of irreducible factors of f . Now the elements of S can be used to extract the irreducible factors of f by suitable gcd operations. Niederreiter's algorithm has the following practical advantages: In the case of small fields the linear equations to be solved can be set up very efficiently. In particular in F 2 they can be read off directly from the coefficients of f .