mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2011-11-09, 13:23   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·74 Posts
Default 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.

May I please have some confirmation/explanation about it?

Luigi

Last fiddled with by ET_ on 2011-11-09 at 13:35
ET_ is offline   Reply With Quote
Old 2011-11-09, 13:32   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by ET_ View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-11-09, 14:24   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by ET_ View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-09, 14:26   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-09, 14:34   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×74 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
ET_ is offline   Reply With Quote
Old 2011-11-09, 14:37   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-11-09, 14:59   #7
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

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
Mr. P-1 is offline   Reply With Quote
Old 2011-11-09, 15:09   #8
axn
 
axn's Avatar
 
Jun 2003

23·607 Posts
Default

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.
axn is offline   Reply With Quote
Old 2011-11-09, 15:42   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

220738 Posts
Default

@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
LaurV is offline   Reply With Quote
Old 2011-11-09, 17:45   #10
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·74 Posts
Default

OK, now I am SURE that someone should at least update the mersennewiki page on P-1.

Back to Riesel and C&P...

Luigi
ET_ is offline   Reply With Quote
Old 2011-11-09, 19:18   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by LaurV View Post
@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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A doubt about the correctness of the Four Colour Theorem Raman Puzzles 4 2016-12-25 06:55
doubt with PARI and modular operations skan Software 16 2013-04-01 16:54
TF algorithm(s) davieddy Miscellaneous Math 61 2011-07-06 20:13
Is there an algorithm which solves this? Unregistered Homework Help 0 2007-08-09 17:40
Maybe new sieving algorithm nuggetprime Riesel Prime Search 5 2007-04-20 04:19

All times are UTC. The time now is 06:10.

Thu Mar 4 06:10:05 UTC 2021 up 91 days, 2:21, 1 user, load averages: 2.47, 2.46, 2.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.