A new efficient factorization algorithm for polynomials over small finite fields (Q2366271): Difference between revisions

A new factorization algorithm for polynomials over finite fields is given. The differential equation \(y^{(p-1)}+y^ p=0\) of order \(p-1\) in the rational function field \(F_ p(x)\) is considered. It is noted \(L(y)=y^{(p-1)}+y^ p\) is a linear operator on the vector space \(F_ p(x)\) over \(F_ p\) and that the solutions of the equation with a fixed square-free denominator \(f=g_ 1\cdots g_ m\) are given by \(y=\sum^ m_{i=1} c_ i(\dot g_ i/g_ i)\) with \(c_ 1,\dots,g_ m\in F_ p\). For \(y=h/f\), \(f\) of degree \(d\), the differential equation can be written \(f^ p\Bigl({h\over f}\Bigr)^{(p-1)}=-h^ p\) and both sides are polynomials in \(x^ p\). Let \(M_ p(f)\) be the \(d\times d\) coefficient matrix of the left side. Then: Theorem: \(\text{rank}\bigl(M_ p(f)+I_ d\bigr)=d-m\). -- It follows that \(f\) is of degree \(d\) iff \(\text{rank}\bigl(M_ p(f)+I_ d\bigr)=d- 1\). The efficiency of this algorithm is considered with special attention being given to the binary case.