 mersenneforum.org Doubt about P-1 algorithm
 Register FAQ Search Today's Posts Mark Forums Read  2011-11-09, 13:23   #1
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·2,417 Posts Doubt about P-1 algorithm

I'm stuck. I'm trying to figure out how the P-1 algorithm works.

From the math page of the Mersenne site, i read:

Quote:
 We compute E - the product of all primes less than B1. Then we compute x = 3E*2*P.
From Mersennewiki i get:

Quote:
 Suppose we want to find a factor of 229-1 with B1 = 10. Then E = 23 × 32 × 5 × 7 × 29.
I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description.

But in the "Step 1" section, I read:

Quote:
 Suppose that the largest prime factor of p-1 is less than a bound B1. Then the method proceeds to compute aE(mod N) where N is the number to factor. E = 2E[SUB]2[/SUB] * 3E[SUB]3[/SUB] * 5E[SUB]5[/SUB] * ... * B where E2 is selected so that 2E[SUB]2[/SUB] is about B1 and the same for the other prime numbers. B is the greatest prime number less than or equal to B1.
while in the example B is equal to 29.

Luigi

Last fiddled with by ET_ on 2011-11-09 at 13:35   2011-11-09, 13:32   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by ET_ I'm stuck. I'm trying to figure out how the P-1 algorithm works. From the math page of the Mersenne site, i read: From Mersennewiki i get: I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description. May I please have some confirmation/explanation about it? Luigi
I see what you mean it makes no sense to me either, because E=#B1 ( #=primorial) in one case and not the other. the other case seems to fit E=(#B1)*2^2*3*P   2011-11-09, 14:24   #3
R.D. Silverman

Nov 2003

746010 Posts Quote:
 Originally Posted by ET_ I'm stuck. I'm trying to figure out how the P-1 algorithm works. From the math page of the Mersenne site, i read: From Mersennewiki i get: I suppose that the Math page is a short summary of the algorithm, and that the Mersennewiki has the actual description. But in the "Step 1" section, I read: while in the example B is equal to 29. May I please have some confirmation/explanation about it? Luigi
B1 = 10 is a typo.   2011-11-09, 14:26   #4
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by R.D. Silverman B1 = 10 is a typo.
I assume, that they are NOT using step 2 here. If they are,
B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.   2011-11-09, 14:34   #5
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×2,417 Posts Quote:
 Originally Posted by R.D. Silverman I assume, that they are NOT using step 2 here. If they are, B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.
I see, thank you! Luigi   2011-11-09, 14:37   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts Quote:
 Originally Posted by R.D. Silverman I assume, that they are NOT using step 2 here. If they are, B1 = 10 is OK. It just means that they used step 2 with B2 >= 30.
B1=10 only appears to work in my mind if they use the definition of E in stage one that is at:

http://mersennewiki.org/index.php/P-1

#(B1) != #B1*2^2*3*P but then either:

http://mersennewiki.org/index.php/P-1

or

http://www.mersenne.org/various/math.php seems wrong, figured it out is it that one of them is the "trivial" case of e3=e3=e5=....=1 because really that's the only way I can figure the 2 are using the same formula.   2011-11-09, 14:59 #7 Mr. P-1   Jun 2003 100100100012 Posts Neither math page nor wiki is completely correct. The P-1 method will find a prime factor p in stage 1 if p-1 divides E. This will work however you construct E. For arbitrary N, an optimal choice of E - one that gives you the greatest chance of success for a given amount of work - is one in which E is the product of prime powers less than some bound B1. The wiki is correct in this respect. However for the algorithm to find p, it is not sufficient "that the largest prime factor of p-1 is less than a bound B1". Rather, the largest prime power which divides p-1 must be less than B1. Similarly, stage 2 will find p if one prime factor is p-1 is between B1 and B2, and all other prime powers dividing p-1 are less than B1. if p-1 has known factors, for example 2q in the case of the Mersenne number Mq, the E must necessarily have these as factors, and optimally have these as additional factors. Last fiddled with by Mr. P-1 on 2011-11-09 at 15:10   2011-11-09, 15:09 #8 axn   Jun 2003 144916 Posts Remember that for mersennes, you're allowed a 'p' for free. So for 2^29-1 will use a 29. This has nothing to do with B1 or B2.   2011-11-09, 15:42 #9 LaurV Romulan Interpreter   "name field" Jun 2011 Thailand 24·613 Posts @RDS: got you this time! :P you also make mistakes, unbelievable! :P B1=10 is not a typo. The product is 2^3*3^2*5*7, the LCM of all numbers smaller then 10. "B is the greatest prime number less than or equal to B1" is right, and that is 7. 29 has nothing to do with it. 29 comes from the fact that the order of 3 in Mp is always a multiple of 2*p. Imagine you start with 3^29 instead of 3. That is all. For example, the order of 3 in 2^11-1 is 88, because 3^88 is 1 mod 2047. If you start with 3, you have to raise it at the power of 88, but you can safely start with 3^11 (in fact 3^22) and do less iterations (translated in a much smaller B1). Must have in mind that P-1 tries to find a factor of the order of 3. Here the prime p (29 in the example) is for free, due to the form of mersenne factors, always 2*k*p+1, so the order of 3 in any factor f of Mp is a factor of 2*k*p, assuming the factor f is prime. So it can only be a multiple of 2p, that is a multiple of p. So you rise (3^29)^E, which is 3^(E*29) and that allows you to use a smaller B1. Last fiddled with by LaurV on 2011-11-09 at 15:56   2011-11-09, 17:45 #10 ET_ Banned   "Luigi" Aug 2002 Team Italia 2×2,417 Posts OK, now I am SURE that someone should at least update the mersennewiki page on P-1. Back to Riesel and C&P... Luigi   2011-11-09, 19:18   #11
R.D. Silverman

Nov 2003

746010 Posts Quote:
 Originally Posted by LaurV @RDS: got you this time! :P you also make mistakes, unbelievable! :P B1=10 is not a typo. The product is 2^3*3^2*5*7, the LCM of all numbers smaller then 10. "B is the greatest prime number less than or equal to B1" is right, and that is 7. 29 has nothing to do with it. 29 comes from the fact that the order of 3 in Mp is always a multiple of 2*p. Imagine you start with 3^29 instead of 3. That is all.
This is false. One can always start with some base b = a^n where n is a
large prime just less than (say) K such that n | p-1.
This is JUST A COINCIDENCE and can not be relied upon.

P-1 is intended to work with ANY base. For the given example, we can use B1 = 30 (or 29) and the algorithm will succeed, or
we can use B1 = 10, B2 = 30.

Since p-1 is divisible by 29, 29 MUST appear in E. It just happens that
from the coincidental choice of 3 as the base that 29 divides the order of 3.
(assuming that your claim is correct; I have no reason to question it)

Try this with a base other than 3, say 11. You will need to take B1 = 30
for the 1-step algorithm or B1 = 10 and B2 = 30 for the 2-step to succeed.

The bound choice for P-1 is intended to be independent of choice of base.
Sometimes, if we are lucky, the chosen base has order divisible by a large
prime that also appears in the factorization of p-1, allowing us to succeed
with a lower B1 FOR THIS CHOICE OF base. It will not be true in general.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Raman Puzzles 4 2016-12-25 06:55 skan Software 16 2013-04-01 16:54 davieddy Miscellaneous Math 61 2011-07-06 20:13 Unregistered Homework Help 0 2007-08-09 17:40 nuggetprime Riesel Prime Search 5 2007-04-20 04:19

All times are UTC. The time now is 20:52.

Sat Dec 4 20:52:24 UTC 2021 up 134 days, 15:21, 1 user, load averages: 0.89, 1.09, 1.18