Smoothness and factoring polynomials over finite fields (Q1178194): Difference between revisions

The author proves the following theorem: There is a deterministic algorithm for factoring polynomials over \(\mathbb{F}_ p\) (\(p\) prime), which on polynomials over \(\mathbb{F}_ p\) of degree \(n\) is running in time \([S(p-1)]^{1/2}[n\log p]^{O(1)}\), under the assumption of the Extended Riemann Hypothesis (ERH). Here \(S(m)\) is the largest prime divisor of \(m\). The algorithm refines algorithms due to \textit{J. von zur Gathen} [Theor. Comput. Sci. 52, 77-89 (1987; Zbl 0633.12009)] and \textit{L. Rónyai} [Combinatorica 9, 199-206 (1989; Zbl 0694.68039)] which required running time \(S(p-1)[n\log p]^{O(1)}\). If ERH indeed holds, then the proposed algorithm is more efficient than the currently best- known for factoring arbitrary polynomials over \(\mathbb{F}_ p\).