Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Root Finding Algorithm for GF(28): Polynomial Equations of Degree Up To 4

IP.com Disclosure Number: IPCOM000121643D
Original Publication Date: 1991-Sep-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 5 page(s) / 115K

Publishing Venue

IBM

Related People

Anderson, RW: AUTHOR [+5]

Abstract

In this article, expressions that can be implemented for roots of Reed-Solomon GF(28), error locator polynomials of degree of up to 4, are presented.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 62% of the total text.

Root Finding Algorithm for GF(28): Polynomial Equations of Degree
Up To 4

      In this article, expressions that can be implemented for
roots of Reed-Solomon GF(28), error locator polynomials of degree of
up to 4, are presented.

      Algorithms for the computation of roots of GF(28) - polynomial
equations of degree up to 4 are presented.  The roots are given as
algebraic functions of the polynomial coefficients.  For Reed-Solomon
error locator polynomials, these coefficients are rational functions
of the syndromes. The roots, i.e., the error locations, are thus
directly expressible by formulas which are algebraic functions of the
syndromes.

      This article extends previously reported work [1] in which an
algorithm for the radical solution of a quadratic equation in a
finite field was described.  For the particular realization of GF(28)
as {ai}254i=0 U {0} with a being a primitive root of the polynomial
equation a8+a4+a3+a2+1=0 over GF(2) we have computed, by the method
described in [1], the fixed matrix multiplier that is used to solve
quadratic equations.

      The radical solution of an arbitrary cubic polynomial as well
as the solution of an arbitrary quadratic polynomial equation reduce,
by the Lagrange resolvent methods, to solving the pure cubic X3=c,
ceGF (28).  We solve this congruence and present solutions
Xi=a85ic57, i=0,1,2.  We are not aware of any publication regarding
this closed form solution.  For iterative methods see [1].  Th...