Results 1 to 3 of 3

Thread: Integer roots over Z_p

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    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}$.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jun 2008
    Posts
    148
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148

    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$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Apr 21st 2010, 03:28 PM
  2. Finding integer roots of quadratic
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Dec 20th 2009, 09:39 AM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 3rd 2009, 12:39 PM
  4. Square roots between two integer values?
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jul 10th 2009, 02:48 AM
  5. find integer roots
    Posted in the Algebra Forum
    Replies: 10
    Last Post: Sep 15th 2007, 04:20 PM

Search Tags


/mathhelpforum @mathhelpforum