Idempotent computation over finite fields (Q1333163)

Let \(K= \mathrm{GF}(p^m)\), \(A\) be a commutative artinian \(K\)-algebra (with unity 1), and \(d\) a divisor of \(m\). Then define \(A(d)= \{a\in A: a^{p^d}= a\}\) and \(K(d)^+ = \mathrm{GF}(p^d)\). Given any \(K(d)\) basis \(B= \{b_1, \ldots, b_n\}\) for \(A(d)\), the author gives a ``basic algorithm'' for computing the primitive idempotents of \(A\). An estimate of the computational cost is given in terms of field and algebra operations. A key step in the ``basic algorithm'' is the determination of a set of eigenvectors associated to the elements in \(B\). Several techniques for the computation of these eigenvectors are given as well as the corresponding cost estimates of the ``basic algorithm'' if it were to employ these techniques. The author also discusses a modified ``basic algorithm'' for the specific case, \(K= \mathrm{GF}(2)\) with \(A\) being the group algebra of a finite abelian group of odd order. As an application, the author shows how the algorithms can be used in conjunction with Berlekamp's and McEliece's algorithms for the factorization of univariate polynomials over \(K\).