On the solution of algebraic equations over finite fields

This article gives new fast methods for decoding certain error-correcting codes by solving certain algebraic equations. As described by Peterson (1961), the locations of a Bose-Chaudhuri Hocquenghem code over a field of characteristic p are associated with the elements of an extension field, GF(pk). The code is designed in such a way that the weighted power-sum symmetric functions of the error locations can be obtained directly by computing appropriately chosen parity checks on the received word. Good methods for computing the elementary symmetric functions from the weighted power-sum symmetric functions have been presented by Berlekamp (1967). The elementary symmetric functions, σ1, σ2, …, σt are the coefficients of an algebraic equation whose roots are the error locations xt+σ1xt−1+σ2xt−1+⋯+σt=0Previous methods for finding the roots of this equation have searched all of the elements in GF(pk) (Chien, 1964) or looked up the answer in a large table (Polkinghorn, 1966). We present here improved procedures for extracting the roots of algebraic equations of small degrees