The generation of rimitive olynomials in GF(q) with independent roots and their applications for ower residue codes, VLSI testing and finite field multipliers using normal basis

Abstract

The interest of this research is in finding rimitive olynomials with linearly independent roots over the Galois field of q elements, GF(q). Existing methods are sufficient only to generate a single olynomial. Here they need to be enumerated in order to apply further selections in view of the applications. The olynomials are generated through a search algorithm extensively runed using some known results and newly derived corollaries. Tables of these olynomials are given over fields up to GF(19) for the first time. The common background for the applications is in forming a normal basis from the linearly independent roots. Three applications are discussed, each including new results: the transformation of ower residue codes to quasi-cyclic codes; the VLSI implementation of multiplication and inverse operations over Galois fields and the acceleration of BCH error correcting code decoding; and the superior aliasing robabilities for the digital testing of integrated circuits