Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \(\mathbb{F}_ q\) (Q1311315)

Let \(F_q\) be the finite field with \(q\) elements and \(f\in F_q[X]\) be a monic polynomial of degree \(d\geq 1\). Assume \(f\) to be square-free, \(f= g_1\cdots g_m\), \(g_i\) irreducible, and note that \({\mathcal A}_f+ F_q[X]/(f)\) is a direct sum with each summand isomorphic to an extension field of \(F_q\). Let \(e_i\in {\mathcal A}_f\) be such that \(\{e_1+ (f),\cdots, e_m+ (f)\}\) form primitive orthogonal idempotents in \({\mathcal A}_f\). Define \[ {\mathcal D}_f= \langle e_1+ (f),\cdots, e_m+ (f)\rangle_{F_q}\leq {\mathcal A}_f. \] The method of Berlekamp for factoring polynomials reduces the problem to a solution of linear equations. The more recent method of Niederreiter is based on the analysis of certain differential equations in the field of rational functions \(F_q(X)\). It is shown here that the solution spaces of both algorithms are isomorphic, both producing a basis of the algebra \({\mathcal D}_f\). The fact can be used to produce a procedure combining the benefits of both methods.