8
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Dec 31, 2016 at 14:34
  • $\begingroup$ @StevenStadnicki it is not well covered in the book by Knuth aleteya.cs.buap.mx/~jlavalle/papers/books_on_line/… $\endgroup$
    – user94040
    Dec 31, 2016 at 14:41

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • $\begingroup$ So there was no randomized algorithm? $\endgroup$
    – user94040
    Dec 31, 2016 at 21:10
  • $\begingroup$ Not that I know of. $\endgroup$
    – Igor Rivin
    Dec 31, 2016 at 21:33
  • $\begingroup$ where does it say $O(1)$? I do not see it. It is interesting. This is a randomized poly algorithm then right? $\endgroup$
    – user94040
    Jan 1, 2017 at 10:29
  • $\begingroup$ Also it looks like Zassenhaus' algorithm is non-iterative and can be implemented in constant depth right? (that is all the work that needs to be done in Hensel lifting can be done in parallel and all the work that needs to be done for matching factors can be done in parallel right. not much sequentiality like LLL iterative basis search right?). $\endgroup$
    – user94040
    Jan 1, 2017 at 10:51
  • 1
    $\begingroup$ @AJ not sure, I haven't thought about it. $\endgroup$
    – Igor Rivin
    Jan 1, 2017 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.