@comment{ generated by <http://infoscience.epfl.ch/> }

@InProceedings{Sander1997/ALGO,
   abstract    = {The polynomial time algorithm of Lenstra, Lenstra, and
                 Lovász [15] 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 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^6+?)$ 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},
   address     = { },
   affiliation = {OTHER},
   author      = {Sander, T. and Shokrollahi, A},
   booktitle   = {Proceedings of the 28th {IEEE} {S}ymposium on the
                 {F}oundations of {C}omputer {S}cience, {FOCS} 1997},
   details     = {http://infoscience.epfl.ch/record/99698},
   doi         = {10.1109/SFCS.1997.646092},
   keywords    = {algoweb_numbertheory},
   location    = { },
   oai-id      = {oai:infoscience.epfl.ch:99698},
   oai-set     = {conf},
   pages       = {46--55},
   publisher   = { },
   review      = {REVIEWED},
   series      = { },
   status      = {PUBLISHED},
   title       = {Deciding properties of number fields without factoring},
   unit        = {ALGO},
   url         = {http://ieeexplore.ieee.org/iel3/5208/14088/00646092.pdf?isnumber=&arnumber=646092},
   year        = 1997
}