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.

The Art Of Computer Programmingvol. 2; that discusses polynomial factorization and the first couple of editions predate LLL. I don't know that they'reexplicitlyprobabilistic 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. $\endgroup$ – Steven Stadnicki Dec 31 '16 at 14:34