Sorry, an error occurred while loading the content.
Browse Groups

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

(2)
• NextPrevious
• 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.