Factoring polynomials over special finite fields (Q5927536)

The main result of this paper is a theoretical algorithm to factorize polynomials over large finite fields (Theorem~1 below). Let \(\Phi_k\) be the \(k\)th cyclotomic polynomial. Then the authors prove the following results. Theorem 1. There is a deterministic algorithm such that, for some constant \(c>0\) -- given a prime \(p\), positive integers \(n\) and \(k\), a non-zero polynomial \(f\in {\mathbb F}_q[X]\), where \(q=p^n\), and for each prime number \(r\) coprime with \(n\) but dividing \(l-1\) for some prime divisor \(l\) of \(\Phi_k(p)\) an irreducible polynomial \(g_r\in {\mathbb F}_p [X]\) of degree \(r\) -- this algorithm finds the factorization of \(f\) in time at most \(\bigl(s(p^k)+\deg (f)+n \log p\bigr)^c\), where \(s(p^k)\) denotes the largest prime divisor of \(\Phi_k(p)\). Theorem 2. There is a deterministic algorithm that, for some constant \(c>0\), has the following property: given two primes \(p\) and \(l\), a positive integer \(h\) for which \(p^h\equiv 1\pmod l\), and for each prime \(r\) dividing \(l-1\) but not dividing \(h\), an irreducible polynomial \(g_r\in {\mathbb F}_p [X]\) of degree \(r\), this algorithm constructs in time at most \((l+h\log p)^c\) a primitive \(l\)th root of unity in \({\mathbb F}_{p^h} \). Theorem 3. There is a deterministic algorithm that, for some constant \(c>0\), has the following property: given a prime number \(p\), a positive integer \(k\), and for each prime divisor \(l\) of \(\Phi_k(p)\) a primitive \(l\)-th root of unity in \({\mathbb F}_{p^k} \), the algorithm constructs in time at most \((s(p^k)+k \log p)^c\) an element of \({\mathbb F}_{p^k} \) that is not an \(l\)-th power in this field. The proofs make deep use of certain Gauss sums. The statements assume that the involved finite fields are given with ``explicit data''.