Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] A new (sort of) factoring method

Expand Messages
  • Décio Luiz Gazzoni Filho
    Sorry for top-replying, but here goes my analysis. What you re doing is basically a pseudorandom cycle method of sorts (a la Pollard rho), except that you try
    Message 1 of 2 , Mar 30, 2005
    • 0 Attachment
      Sorry for top-replying, but here goes my analysis.

      What you're doing is basically a pseudorandom cycle method of sorts (a la
      Pollard rho), except that you try to restrict yourself to ever smaller
      subgroups of (Z/pZ)*, where p is the prime factor of n being sought. This
      idea is well known (it was used for instance in the factorization of the 7th
      Fermat number by Pollard and Brent), but it only works when you have some
      information about the group structure of (Z/pZ)*. For instance, in the case
      of Fermat numbers, it's known that factors of F_n = 2^2^n + 1 lie in the
      residue class 1 mod 2^(n+2), so 2^(n+2) divides p-1. In that case one can
      replace quadratic polynomials by degree-2^(n+2) polynomials and restrict
      oneself to subgroups of (Z/pZ)* of order divisible by (p-1)/2^(n+2). In the
      general case, the best we can say is that p-1 is even, and thus a quadratic
      polynomial is used.

      The difficult part is deducing this sort of information. For certain prime
      forms this can be done, but I don't think a general method is known that
      figures out divisors of p-1, or even residue classes of p modulo an arbitrary
      prime. Provided such a method existed, and that it could run in a reasonable
      amount of time for an arbitrary prime q or lots of small ones, in which case
      one could glue them using the CRT (a la Schoof for elliptic curve order
      computation), then one could apply Lenstra's divisors in residue classes
      algorithm (hello David!) once q > n^(1/3), or once q > n^(1/4) if one were to
      employ Coppersmith's improvements to Lenstra's algorithm.

      Décio

      On Wednesday 30 March 2005 18:16, you wrote:
      > Here's a different method of factoring I've been
      > playing with. There's nothing really inovative in
      > this, it's just a slightly different approach to a
      > well-known property.
      >
      > Given a composite N = PQ, if two integers X and Y both
      > have the same residue (mod P) then (X-Y) == 0 mod P
      > and GCD(N,X-Y) obviously reveals P to be a factor of
      > N. But how can we best go about finding such a pair?
      > This is the new part.
      >
      > Taking, for example, P=17, list all the possible
      > residues mod 17. These are { 0 1 2 3 4 5 6 7 8 9 10
      > 11 12 13 14 15 16 17 }. So any randomly picked number
      > will have one of those residues mod 17, and the
      > probability that any two of them share the same
      > residue is 1/17 = 0.0588. Now take those two random
      > numbers and replace them with r <- (r+1)^2 mod P. Now
      > the set of possible residues consists of only these
      > eight: { 0 1 2 4 9 13 15 16 } (Zero and the quadratic
      > residues of 17). After this step the probability that
      > our two values share the same residue mod 17 is 1/8 =
      > 0.125.
      >
      > Next replace those two residues with r <- (2r+4)^4.
      > After this second step the set of possible residues is
      > { 0 1 4 13 16 } and the probability of our two numbers
      > matching now is 1/5 = 0.200. Next we take these two
      > numbers and run them through r <- (3r+7)^6 and get the
      > set { 2 9 13 16 } giving us a probability of match of
      > 1/4 = 0.250. (This assumes that the residues are
      > distributed uniformly, which they are not. The
      > lopsided distribution actually gives us a higher
      > probability of a match.)
      >
      > Now if we continue to subject our two randomly picked
      > numbers X and Y to this iteration:
      > r <- (Ar+B)^C
      > A = A+1
      > B = B+3
      > C = C+2
      >
      > The probability that these two randomly picked numbers
      > will end up with the same residue mod 17 gets better
      > and better. So if we do this enough times the factor
      > will be revealed.
      >
      > I use a different function for each iteration because
      > when I use the same function over and over the number
      > of residues quickly stops shrinking and settles on one
      > constant number of residues that repeat periodically.
      > This is the essence of the Pollard rho method, but is
      > not desirable in this method. Each iteration needs to
      > use a different function to keep the residue set
      > shrinking.
      >
      > The good news is, using 10 or 20 random starting
      > values instead of just two, the method does work, and
      > works as quickly as ECM for numbers with prime factors
      > of 5 or 6 digits. (Both implemented in UBASIC) But by
      > the time I tried numbers with 8-digit factors it was
      > already taking 5 to 10 times longer than ECM, and one
      > number with a 9-digit factor that ECM solved in less
      > than 2 seconds ran for several hours without ever
      > finding the factor.
      >
      > The problem is that I thought the number of unique
      > residues mod P would continue to shrink at more or
      > less the same rate. What happens instead is that for
      > large values of P the size of the set shrinks at a
      > nearly constant rate per iteration, but then suddenly
      > stops shrinking at all. I suspect it has something to
      > do with the fact that R^X (mod P) = R^(X+(P-1)/k) (mod
      > P) whenever R^((P-1)/k) = 1 so that beyond that point
      > every iteration is essentially using the same function
      > that had already been used (P-1)/k iterations
      > previously, and the residue set cannot be made smaller
      > by applying the same function over again. If truly
      > unique functions could be applied at every iteration
      > then it _seems_ as if the set of surviving residues
      > could be shrunk to a single residue in K*log(P) steps
      > for some reasonable K and that any number that has P
      > as a factor could be factored in k*log(P) time. But
      > alas, the holy grail remains hidden.
      >
      > --gary shannon
      >
      >
      >
      >
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      >
      > Yahoo! Groups Links
      >
      >
      >


      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.