 mersenneforum.org P-1 factoring anyone?
 Register FAQ Search Today's Posts Mark Forums Read  2013-06-19, 06:02   #1442
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

265016 Posts Quote:
 Originally Posted by owftheevil Hi LaurV, Very nice description of a p-1 algorithm with e = 1 and d = 6,
You know that it is the only algorithm I know! But as said:
Quote:
 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.

Quote:
 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.

Last fiddled with by LaurV on 2013-06-19 at 06:54   2013-06-20, 13:32   #1443
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

3×1,979 Posts Quote:
 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.   2013-06-20, 21:12 #1444 Bdot   Nov 2010 Germany 3·199 Posts 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 < 10132 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 10132) would be paired up with a prime in stage.2 (that's what I understood of LaurV's explanation). owftheevil's example showed how 10132 can be multiplied into the accumulated product, which should even reveal factors if their k was a multiple of 10133. Is that right?   2013-06-21, 07:55   #1445
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

24·613 Posts Quote:
 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].

Last fiddled with by LaurV on 2013-06-21 at 08:39   Thread Tools Show Printable Version Email this Page

All times are UTC. The time now is 15:28.

Mon Nov 29 15:28:24 UTC 2021 up 129 days, 9:57, 0 users, load averages: 1.42, 1.38, 1.42