# Existence of Randomized polynomial time algorithm and some arithmetic analog of $ACC^0$ circuits for Factoring of primitive polynomials before LLL?

Before LLL came along in $1982$ there was no deterministic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$.

However was there a probabilistic polynomial (in degree and number of bits in coefficients) way to factor square free primitive polynomials in $\Bbb Z[x]$? Is there a reference?

The reason for the query is following. The LLL algorithm is highly iterative and in circuit complexity parlance seems to be polynomial size in $O(\log n)$ depth . So I am wondering if there was a randomized or deterministic algorithm which can factor at least a fraction of primitive polynomials in $\Bbb Z[x]$ and that which would still be in $O(1)$ depth and polynomial size.

• You might check (old editions of) The Art Of Computer Programming vol. 2; that discusses polynomial factorization and the first couple of editions predate LLL. I don't know that they're explicitly probabilistic polynomial (in particular, because the main algorithm works over $(\mathbb{Z}/p\mathbb{Z})[x]$ for many $p$ and uses the CRT to staple results together, and as the book notes there are polynomials for which this approach is doomed to failure) but the references therein are probably your best bet. – Steven Stadnicki Dec 31 '16 at 14:34
• @StevenStadnicki it is not well covered in the book by Knuth aleteya.cs.buap.mx/~jlavalle/papers/books_on_line/… – user94040 Dec 31 '16 at 14:41

The Zassenhaus algorithm (see the Wikipedia article on factoring) Is polynomial, except for the exponential dependence on the number of irreducible factors of the polynomial. However, the expected number of irreducible factors is $O(1)$ (see this nice UChicago REU by Alegra Juarez), so Zassenhaus is expected polynomial time. The worst case is horrible, though, and so the Novocin-van Hoeij algorithm (see Novocin's very nice description) cleverly circumvents the problems.
• where does it say $O(1)$? I do not see it. It is interesting. This is a randomized poly algorithm then right? – user94040 Jan 1 '17 at 10:29