AN ALGORISM FOR FACTORING Xn- 1 OVER A FINITE FIELD

摘要

An algorism is given for factoring Xn -1 over the finite field Fq of q elements. This can be of use in constructing another finite field over Fq . in constructing a linear recursion of period n over Fq , or in constructing cyclic error-correcting group codes. The algorism has two parts:Step 1, the construction of the multi¬plicative identities of the minimal ideals of Fq [ X] /[ Xn -1 ]; Step 2, the use of these idempotents in the construction of the irreducible factors of Xn-1.