Factoring polynomials over finite fields

From MaRDI portal





Let f be a polynomial of degree n, such that all roots of f are in the prime field \({\mathbb{F}}_ p\). The author gives an algorithm to factor f over the field \({\mathbb{F}}_ p\). This algorithm uses a given r-th non- residue in the r-th cyclotomic field \({\mathbb{F}}\) over \({\mathbb{F}}_ p\), where r is a prime divisor of n. The running time of this algorithm is polynomial in log(p) and n r. In order to find the factorization the authors construct an \(m\times m\) matrix A over \({\mathbb{F}}\), with \((m,r)=1\), such that the eigenvalues of A are all zeroes of f. The matrix A then can be used to factor f. - This method can be used for general factorization of a polynomial over an arbitrary finite field. This follows from the fact that this problem can be reduced in polynomial time to the problem of factoring a polynomial, which has all its roots in the prime field, over this prime field. The problem of finding an r-th non-residue can be solved in polynomial time, if some generalized Riemann hypothesis is true.




Cited in
(39)








This page was built for publication: Factoring polynomials over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3795755)