# 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 $\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}$.

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

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

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

There are of course other maps from $\displaystyle Z_n$ to $\displaystyle Z_n$ which have small range (for example, consider $\displaystyle 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 $\displaystyle 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 $\displaystyle f$ from $\displaystyle Z_n$ to $\displaystyle Z_n$ must satisfy the condition that for any divisor $\displaystyle d$ of $\displaystyle n$, we have that if $\displaystyle u \equiv v mod(d)$, then $\displaystyle f(u) \equiv f(v) mod(d)$, where $\displaystyle f$ is our function from $\displaystyle Z_n$ to $\displaystyle Z_n$.

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

The only type of functions $\displaystyle 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 $\displaystyle f(x) = c$. This satisfies the above condition, but clearly we cannot utilize it to obtain any information regarding the factors of $\displaystyle n$.