20050411, 16:57  #1 
Mar 2003
New Zealand
13·89 Posts 
Why LMH doesn't sieve
My message in the Welcome thread didn't make sense, but it is related to LMH. Maybe someone can find a nicer way to explain it.
Say we are trial factoring 2^{p}1. Then we know that any factor q must be of the form q=2kp+1 (where q and p are both prime). So the only other Mersenne numbers that q could possibly divide are 2^r1 where r is a prime factor of k. Now for LMH we are looking at numbers with exponents p > 25*10^{6}, so for factors in the range say 2^{60} < q < 2^{61} we have 2kp+1 < 2^{61}, and so k < 2^{61}/2*25*10^{6}, or k < 46*10^{9}. Since 25*10^{6} < 46*10^{9} < (25*10^{6})^{2}, there can only be one possible LMH Mersenne number other than 2^{p}1 that q could divide, and even then only in the relatively rare case that one of the factors of k was a prime larger than 25*10^{6}. I think this means that a sieve would be worthwhile for range a < p < b of exponents p where b/a is very large, but for LMH the range is a=25*10^{6} < p < b=79*10^{6} and so b/a is too small. 
20050413, 17:51  #2  
"Richard B. Woods"
Aug 2002
Wisconsin USA
16024_{8} Posts 
Quote:
So, just as you first correctly stated in the Welcome thread, "... sieving has no advantage over individual trial factoring"  regardless of b/a ratio. 

20050413, 19:12  #3 
"William"
May 2003
New Haven
924_{16} Posts 
I think geoff has it right. The point is that 2*p*q+1 might possibly divide 2^p1 and it might possibly divide 2^q1, even though it cannot possibly divide both of them.

20050418, 09:53  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×599 Posts 
I based my answer on interpreting
Quote:
If that's not correct, will someone please rephrase the "Say we ..." paragraph to make it clearer to me? Last fiddled with by cheesehead on 20050418 at 09:57 

20050418, 10:37  #5 
Mar 2003
New Zealand
13·89 Posts 
How about:
"Say we want to find a prime q that divides 2^{p}1. Then we know that q must be of the form q=2kp+1, and the only other Mersenne numbers that q could possibly divide are 2^r1 where r is a prime factor of k." I think GIMPS did sieve in the early days, so another explaination would be that since the efficiency of the sieve decreases as the range of the numbers being factored decreases, and GIMPS has already stopped sieving the range 179 million, then there is no point further sieving the smaller range 2579 million. 
20050423, 04:24  #6 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·599 Posts 
Oh, now I get it  Prior to performing the test, _candidate_ q is not yet known to be a factor of 2^p1. What you're trying to determine is whether it would be efficient to arrange to test q as a possible factor of any other primeexponent Mersenne if TF shows q not to be a factor of 2^p1. (... and the other primeexponent Mersennes to test would be 2^r1 where r is a prime factor of k.)
I'll bet many readers understood right away. Thank you for your patience, Geoff. :) Last fiddled with by cheesehead on 20050423 at 04:26 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Just because it looks like it MIGHT be racism doesn't mean it is  jasong  jasong  6  20140212 14:15 
Prime95 doesn't run on Mac  kolen  Information & Answers  5  20130602 20:31 
Advantage of lattice sieve over line sieve  binu  Factoring  3  20130413 16:32 
CPU days doesn't update  pdlouis  Information & Answers  3  20090417 22:30 
SkipTrialFactoring=1 doesn't work?  cmokruhl  Software  1  20021015 19:04 