Square-Chain polynomials

A bit more on the mathy side here. Here's an idea I read about to factor integers that could make for a probabilistic polynomial-time algorithm:

Find a polynomial of the form \( ((\cdots((x^{2}-c_{1})^{2}-c_{2})^{2}\cdots)^{2}-c_{k-1})^{2}-c_{k} \) which factors completely over integers. That's just repeated squaring and subtraction, so it's easy to compute. If you make it long enough (i.e \( k \) is sufficiently large), then this polynomial will have lots and lots of roots: indeed, somewhere around \( 2^{k} \) distinct roots.

Now evaluate that polynomial modulo \( n = pq \), a semiprime. Because the polynomial has a lot of roots over the integers, it must also have a lot of roots modulo \( p \) and modulo \( q \). But there's every reason to believe that the numbers which are roots modulo \( p \) would be different from those which are roots modulo \( q \). Just pick such a number, and you're a single (efficient) GCD away from factoring \( n \).

What are the issues? Well, you have to pick \( k \) so you get enough distinct roots, but not too many. In theory, this shouldn't be too hard: just pick \( k \) somewhere near \( \log_{2}(n) / 2\).

The hard part is finding those coefficients \( c_i \) that make for a polynomial that factors right.

Polynomials like this are known up to \( k = 4 \), not nearly large enough to do any real work with. Are there any larger?

This is a research problem posed by Richard Crandall and Carl Pomerance in their wonderful book "Prime Numbers: A Computational Perspective."

This problem really caught my fancy for a bit. I don't believe that square-chain polynomials as described above exist for \( k \) much larger than 4. But I'm far from convinced. The best I personally could show was that the coefficients of such a polynomial have to get really big, really quick. So quickly as to make a naive polynomial-time algorithm laughable.

You can read about that here, if you're interested in learning more: https://arxiv.org/abs/1902.11164