COmputational COmmutative Algebra

Villa Gualino, Torino, Italy
May 31 - June 5, 1999

Root finding using p-linear ideals

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.