ABSTRACT
This chapter presents methods and implementation architectures for root computations. The roots of a general polynomial over finite fields are computed by exhaustive Chien search, which tests each finite field element to see if it is a root. The Chien search needs to test each finite field element; it has very high complexity when the order of the finite field is high. Alternatively, if the polynomial is in an affine format, the root computation can be done in an easier way without Chien search. The irregularity of the finite field elements in a conjugacy class, it is very difficult to label each conjugacy class by a single address that can be easily mapped to the elements in the class and at the same time make the addresses for all conjugacy classes consecutive. The roots for multiple elements in each conjugcay class may need to be stored to trade off the look-up table compression ratio with address generation complexity.
