A critical step in the decoding of Reed Solomon error correcting codes is the
determination of the locations of the errors. These locations are specified by
the roots of an error locator polynomial. For many practical applications such
as hard disks, this decoding needs to be performed in real time which excludes
the use of probabilistic root finding algorithms. This talk will present some
deterministic root finding algorithms for polynomials over finite fields,
based on the use of p-linear polynomials and p-linear ideals. These are
characterized by the fact that their zeros form a vector space over Z/p.
We will show that a modified version of the FGLM algorithm for this class
of ideals can compute a groebner basis for an elimination ordering in time
which is polynomial in the log of the degree of the ideal. Using this we can
find a basis for the zeros of the p-linear ideal in time which is polynomial
in the dimension of the solution space. Polynomial factorization in
characteristic 2 using idempotents or using Niederreiter's algorithm can
be done either by linear algebra or by finding solutions to an associated
p-linear ideal. The surprising result is that we can find the solutions
faster using groebner bases for the p-linear ideals than the
more direct approach of finding the roots using linear algebra.
