Results 1 to 3 of 3

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

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: April 21st 2010, 04:28 PM
  2. Finding integer roots of quadratic
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 20th 2009, 10:39 AM
  3. Integer roots of integer polynomials
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 3rd 2009, 01:39 PM
  4. Square roots between two integer values?
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 10th 2009, 03:48 AM
  5. find integer roots
    Posted in the Algebra Forum
    Replies: 10
    Last Post: September 15th 2007, 05:20 PM

Search Tags


/mathhelpforum @mathhelpforum