AN ACCELERATION OF THE NIEDERREITER FACTORIZATION ALGORITHM IN CHARACTERISTIC-2

A new deterministic factorization algorithm for polynomials over finite fields was recently developed by Niederreiter. The bottleneck in this algorithm is the last stage in which the irreducible factors of the polynomial are derived from the solutions of a system of linear equations. In this paper, we consider finite fields of characteristic 2, and we show that in this case there is a more efficient approach to the last stage of the Niederreiter algorithm, which speeds up the algorithm considerably.