I've been thinking about this problem somewhat. I realize its actually probably better to not consider using a polynomial ladder at all in this case (at least not if we wish to optimize the factoring algorithm). Generally, what we want is a polynomial (or map) function from to such that the range of is much smaller than its domain.

For example, if we use the function , then for large M, this will have a small range regardless of what is.

A factoring algorithm which is actually a combination of the Pollard Strassen Polynomial Evaluation Method (PSPEM) and the

P - 1 Method (both of these factoring algorithms can be found in chapter 5 of Pomerance book Prime Numbers: A Computational Perspective) can be done as follows:

Consider the polynomial map where and evaluate it for values of , where , for consecutive values of starting at 1.

The polynomial would take the same amount of time to compute as any other polynomial (and we'd use Horner's Scheme to evaluate it most likely). However the value of for which , maybe fairly small if (where p is the unknown factor of n) is such that is large, as would be much smaller.

There are of course other maps from to which have small range (for example, consider , however in general it is hard to find a function that has uniformly small ranges over arbitrary , that aren't also increasingly more time consuming to compute. If we could find a polynomial ladder for very large k, this would be good, since we would know that many values of x in the domain would go to 0.