P-1 factoring anyone?

[LaurV]

Originally Posted by owftheevil

Hi LaurV,

Very nice description of a p-1 algorithm with e = 1 and d = 6, <snip>

You know that it is the only algorithm I know!

But as said:

Originally Posted by LaurV

In stage 2, say we use the algorithm as it is explained here, which is the simplest stage 2 form,

Btw, your post is a very and a nice description of stage's 2 extensions. People who want to better understand p-1 algorithm must read your posts. For the guys who don't know, owftheevil is the one who implemented P-1 algorithm for GPU (nVidia cuda cards), so he certainly knows what he is talking about.

My comment to your post: With the "deeper" stage 2 which you describe, you just have different "partitions" of the B1...B2 interval, but for each "partition", the things go exactly the same as I described. Say, instead of "+/-1 (mod 6)" you take numbers which are "+/-1,7,11,13 (mod 30)", you compute F^2, F^8, etc, and you do 8 GCD's instead of 2, at each "step" in stage 2, the things go "mathematically" exactly the same as I described. What you are explaining, it is just "highly optimization", which is confusing for the guy who doesn't know p-1 algorithm very good. You can go higher, and instead of 8 classes may have "more classes (mod 210)", you can take them into account only if they are prime, whatever, but at the end, those are just optimizations of the basic idea, to make the algorithm more efficient.

The takeaway point is that just because 1013^2 is less than b2, it is not a foregone conclusion that a factor containing 1013^2 will be found.

Sure! Here we have no disagreement I 101% agree with this conclusion.

[henryzz]

Originally Posted by cheesehead

Clarification request:

Did you mean that stage 1 would include in its exponentiation, in addition to what it now includes, [the powers {of all the primes up to B1} that are between B1 and B2]"?

That is what I meant.
It would mean that all cases like 1013^2 would get hit.

[Bdot]

Thank you all for your explanations, , these have been very helpful postings that are worth saving (to the wiki?).

I now understand that James' site correctly displays the B1/B2 limits that are required for a 100% chance of finding the factor. P-1 using a lower B1 value would still have some chance of finding the factor, depending on those limits and the chosen d and e values. But similarly to factors found with the help of the Brent-Suyama extension, this is nothing that could easily be displayed there.

Is there a chance that B2 < 1013² will find the factor as well?
I think yes, because the stage.1 result is already a multiple of 1013. It should be sufficient if any multiple of 1013 (and not necessarily 1013²) would be paired up with a prime in stage.2 (that's what I understood of LaurV's explanation). owftheevil's example showed how 1013² can be multiplied into the accumulated product, which should even reveal factors if their k was a multiple of 1013³. Is that right?

[LaurV]

Originally Posted by Bdot

Is that right?

Yes. You got it right.

It all starts with Fermat's little theorem, which says that for every prime q, and every base b which is not a multiple of q, we have b^(q-1)=1 (mod q).

In our case, q is the (unknown) factor we need to find, and therefore q=2kp+1, so q-1=2kp, where p is known, the mersenne exponent in m=2^p-1.

By renaming c=b^(2p), and applying Fermat, we have b^(q-1)=b^(2kp)=(b^(2p))^k=c^k=1 (mod q).

We can compute c, as we know p, and we chose any b which is not a power of 2 or its negative (b=3 for Prime95). But we don't know k, and we have to find it.

We then compute F=c^E, where E is that product everybody is talking about . If by any chance E is a multiple of k (any multiple! i.e. E=z*k) then we apply the result above, and we have F=c^E=c^(zk)=(c^k)^z=(1)^z=1 (mod q). Therefore, F=1 (mod q), or F-1=0 (mod q). If m=2^p-1 is a multiple of q, taking a GCD of m and F-1 will reveal the factor q.

In our case, taking F at a power of any multiple of 1013 will work, as the resulted power is a multiple of k. If we raise F to a multiple of 1013^2, we might even find a factor having 1013^3 in its k, indeed, if that factor exists.

----------------
[edit: as i said sometime ago, without any disrespect for Mr. Pollard (some people say "p" in the name of the method comes from the initial of the founder), when we talk about the method applied to mersenne numbers, we should call it "q-1" algorithm, to avoid confusion with the exponent p in m=2^p-1, which we usually denote it "p" to show that is a prime number].