Deciding Properties of Polynomials without Factoring

The polynomial time algorithm of Lenstra, Lenstra, and Lovasz [17] for factoring integer polynomials and variants thereof have been widely used to show that various computational problems in number theory have polynomial time solutions. Among them is the problem of factoring polynomials over algebraic number fields which is used itself as a major subroutine for several other algorithms. Although a theoretical breakthrough, algorithms based on factorization of polynomials over number fields are notoriously slow and hard to implement, with running times ranging between O(n^12+?) and O(n^18+?) depending on which variant of the lattice basis reduction is used. Here, n is an upper bound for the maximum of the degrees and the bit-lengths of the coefficients of the polynomials involved. On the other hand, in many situations one does not need the full power of factorization, so one may ask whether there exist faster algorithms in these cases. In this paper we develop more efficient Monte Carlo algorithms to decide certain properties of roots of integer polynomials, without factoring them. Such problems arise, e.g., when solving systems of algebraic equations. Our methods applied to this situation give thus information about the solutions of such systems of equations. Assuming the validity of the Extended Riemann Hypothesis, our algorithms run in time O(n^l+?) in worst case, though they usually terminate much faster if the input polynomials do not have the properties the algorithm is testing. Besides this substantial improvement in the running time, our algorithms have the advantage of being conceptually easy. Their building blocks are gcd-computations in polynomial rings over finite fields, and primality tests for integers. However, despite the simplicity of our algorithms, their analysis is involved and uses tools from algebraic and analytic number theory. Our methods yield polynomial time algorithms even in cases where the factorization method does not. We exhibit such an example by showing that the language consisting of pairs (g,m) where g is a monic irreducible polynomial such that all its roots are integral linear combinations of mth roots of unity, is in co-RP. Currently, we do not know of any deterministic polynomial time algorithm to decide this problem, even if we assume the validity of the Extended Riemann Hypothesis. We will also show that computing the minimal m such that (g,m) belongs to this language is intractable by means of present methods: we prove that this problem is polynomial time equivalent to that of computing the largest square free divisor of an integer.

ICSI Technical Report TR-97-027

Technical Report