20111109, 13:23  #1  
Banned
"Luigi"
Aug 2002
Team Italia
4843_{10} Posts 
Doubt about P1 algorithm
I'm stuck.
I'm trying to figure out how the P1 algorithm works. From the math page of the Mersenne site, i read: Quote:
Quote:
But in the "Step 1" section, I read: Quote:
May I please have some confirmation/explanation about it? Luigi Last fiddled with by ET_ on 20111109 at 13:35 

20111109, 13:32  #2  
"Forget I exist"
Jul 2009
Dumbassville
2·5·839 Posts 
Quote:


20111109, 14:24  #3  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:


20111109, 14:26  #4 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 

20111109, 14:34  #5 
Banned
"Luigi"
Aug 2002
Team Italia
29×167 Posts 

20111109, 14:37  #6  
"Forget I exist"
Jul 2009
Dumbassville
2·5·839 Posts 
Quote:
http://mersennewiki.org/index.php/P1 #(B1) != #B1*2^2*3*P but then either: http://mersennewiki.org/index.php/P1 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. 

20111109, 14:59  #7 
Jun 2003
7·167 Posts 
Neither math page nor wiki is completely correct. The P1 method will find a prime factor p in stage 1 if p1 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 p1 is less than a bound B1". Rather, the largest prime power which divides p1 must be less than B1. Similarly, stage 2 will find p if one prime factor is p1 is between B1 and B2, and all other prime powers dividing p1 are less than B1. if p1 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. P1 on 20111109 at 15:10 
20111109, 15:09  #8 
Jun 2003
5,387 Posts 
Remember that for mersennes, you're allowed a 'p' for free. So for 2^291 will use a 29. This has nothing to do with B1 or B2.

20111109, 15:42  #9 
Romulan Interpreter
"name field"
Jun 2011
Thailand
17·19·31 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^111 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 P1 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 20111109 at 15:56 
20111109, 17:45  #10 
Banned
"Luigi"
Aug 2002
Team Italia
29·167 Posts 
OK, now I am SURE that someone should at least update the mersennewiki page on P1.
Back to Riesel and C&P... Luigi 
20111109, 19:18  #11  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 
Quote:
large prime just less than (say) K such that n  p1. This is JUST A COINCIDENCE and can not be relied upon. P1 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 p1 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 1step algorithm or B1 = 10 and B2 = 30 for the 2step to succeed. The bound choice for P1 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 p1, allowing us to succeed with a lower B1 FOR THIS CHOICE OF base. It will not be true in general. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A doubt about the correctness of the Four Colour Theorem  Raman  Puzzles  4  20161225 06:55 
doubt with PARI and modular operations  skan  Software  16  20130401 16:54 
TF algorithm(s)  davieddy  Miscellaneous Math  61  20110706 20:13 
Is there an algorithm which solves this?  Unregistered  Homework Help  0  20070809 17:40 
Maybe new sieving algorithm  nuggetprime  Riesel Prime Search  5  20070420 04:19 