# Thread: Integer roots over Z_p

1. ## Integer roots over Z_p

So for awhile we've been talking about finding polynomial ladders. This is an interesting topic since a given ladder of degree k, has $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 $Z_p$ (where p could be the unknown prime factor we wish to find).

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

For example, when $p = 61$, $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 $5429$ ( $= 61*89$), an obvious choice would be to use the polynomial $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 $x^2 + x^{-1} + 1$ over $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 $2^5$ roots over the prime number $Z_{97}$.

2. 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 $f$ from $Z_n$ to $Z_n$ such that the range of $f$ is much smaller than its domain.

For example, if we use the function $f(x) = x^{lcm(1,M)} - 1 mod(n)$, then for large M, this will have a small range regardless of what $Z_n$ 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 $P(x;a) = (a^dx - 1).....(a^2x - 1)(ax - 1)$ where $a = 2^{lcm(1,M)} mod(n)$ and evaluate it for values of $x = k^i$, where $k = a^{d} mod(n)$, for consecutive values of $i$ starting at 1.

The polynomial $P(x)$ 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 $i$ for which $gcd(P(k^i),n) = p$, maybe fairly small if $p - 1$ (where p is the unknown factor of n) is such that $L = gcd(p-1,lcm(1,M))$ is large, as $p-1 / L$ would be much smaller.

There are of course other maps from $Z_n$ to $Z_n$ which have small range (for example, consider $f(x) = (x^2 + x^{-2} + 1)^2 mod(n))$, however in general it is hard to find a function that has uniformly small ranges over arbitrary $Z_n$, 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.

3. ## Clarifying a point

I should probably clarify something with regards to the above post.

Any function $f$ from $Z_n$ to $Z_n$ must satisfy the condition that for any divisor $d$ of $n$, we have that if $u \equiv v mod(d)$, then $f(u) \equiv f(v) mod(d)$, where $f$ is our function from $Z_n$ to $Z_n$.

The reason the above must hold is because otherwise we cannot use this map to obtain a factorization of $n$, regardless of how small the range of $f$ is over $Z_n$.

The only type of functions $f$ that satisfy the above are polynomials (note that we can include polynomials which have negative exponents).

Another type of function we should avoid is the constant function $f(x) = c$. This satisfies the above condition, but clearly we cannot utilize it to obtain any information regarding the factors of $n$.