So for awhile we've been talking about finding polynomial ladders. This is an interesting topic since a given ladder of degree k, has $\displaystyle 2^k$ roots, and yet the polynomial itself can be calculated in only k multiplications (or k squaring). Unfortunately, it doesn't appear that polynomial ladders can be used to create any kind of fast Integer factoring algorithm (and this is really what inspired the original question in the Crandall/Pomerance book), since it is likely that we cannot find such polynomials for k larger than 4.

On the positive side though, it is worth noting that for the purpose of integer factoring, one doesn't necessarily need to have a polynomial with a large # of integer roots, but rather just has many roots over $\displaystyle Z_p$ (where p could be the unknown prime factor we wish to find).

For example, consider the polynomial $\displaystyle x^{60} - 1$. This polynomial has only two roots, namely $\displaystyle \pm 1$. On the other hand, over $\displaystyle Z_p$, this polynomial can have up to and including 60 roots.

For example, when $\displaystyle p = 61$, $\displaystyle x^{60} - 1$ has exactly 60 roots over Z_61 by Fermat's test. As a result, if we wish to factor an integer like $\displaystyle 5429$ ( $\displaystyle = 61*89$), an obvious choice would be to use the polynomial $\displaystyle x^{60} - 1$.

Another advantage of working over Z_p, is that we can even use polynomials that have negative exponents. For example, we can calculate integer values of a polynomial like $\displaystyle x^2 + x^{-1} + 1$ over $\displaystyle Z_p$.

Anyway, since were working at squaring ladders at the moment, the first question I'd like to pose is this; Find a polynomial squaring ladder with k = 5, such that this polynomial has exactly $\displaystyle 2^5$ roots over the prime number $\displaystyle Z_{97}$.