So for awhile we've been talking about finding polynomial ladders. This is an interesting topic since a given ladder of degree k, has 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 (where p could be the unknown prime factor we wish to find).
For example, consider the polynomial . This polynomial has only two roots, namely . On the other hand, over , this polynomial can have up to and including 60 roots.
For example, when , has exactly 60 roots over Z_61 by Fermat's test. As a result, if we wish to factor an integer like ( ), an obvious choice would be to use the polynomial .
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 over .
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 roots over the prime number .