mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Lone Mersenne Hunters

Reply
 
Thread Tools
Old 2005-04-11, 16:57   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default 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 2p-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^r-1 where r is a prime factor of k.

Now for LMH we are looking at numbers with exponents p > 25*106, so for factors in the range say 260 < q < 261 we have 2kp+1 < 261, and so k < 261/2*25*106, or k < 46*109. Since 25*106 < 46*109 < (25*106)2, there can only be one possible LMH Mersenne number other than 2p-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*106.

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*106 < p < b=79*106 and so b/a is too small.
geoff is offline   Reply With Quote
Old 2005-04-13, 17:51   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Quote:
Originally Posted by geoff
Say we are trial factoring 2p-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^r-1 where r is a prime factor of k.
But you already linked (in the Welcome thread) to a proof that no prime number can divide more than one prime-exponent Mersenne number! If q and p are prime as you specify, then q cannot divide any 2^r-1 for any prime r not equal to p.

So, just as you first correctly stated in the Welcome thread, "... sieving has no advantage over individual trial factoring" -- regardless of b/a ratio.
cheesehead is offline   Reply With Quote
Old 2005-04-13, 19:12   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

1001001101102 Posts
Default

I think geoff has it right. The point is that 2*p*q+1 might possibly divide 2^p-1 and it might possibly divide 2^q-1, even though it cannot possibly divide both of them.
wblipp is offline   Reply With Quote
Old 2005-04-18, 09:53   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

I based my answer on interpreting
Quote:
Originally Posted by geoff
Say we are trial factoring 2p-1. Then we know that any factor q must be of the form q=2kp+1 (where q and p are both prime).
to mean that q is a factor of 2p-1.

If that's not correct, will someone please re-phrase the "Say we ..." paragraph to make it clearer to me?

Last fiddled with by cheesehead on 2005-04-18 at 09:57
cheesehead is offline   Reply With Quote
Old 2005-04-18, 10:37   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

How about:

"Say we want to find a prime q that divides 2p-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^r-1 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 1-79 million, then there is no point further sieving the smaller range 25-79 million.
geoff is offline   Reply With Quote
Old 2005-04-23, 04:24   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

Oh, now I get it -- Prior to performing the test, _candidate_ q is not yet known to be a factor of 2^p-1. What you're trying to determine is whether it would be efficient to arrange to test q as a possible factor of any other prime-exponent Mersenne if TF shows q not to be a factor of 2^p-1. (... and the other prime-exponent Mersennes to test would be 2^r-1 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 2005-04-23 at 04:26
cheesehead is offline   Reply With Quote
Reply

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 2014-02-12 14:15
Prime95 doesn't run on Mac kolen Information & Answers 5 2013-06-02 20:31
Advantage of lattice sieve over line sieve binu Factoring 3 2013-04-13 16:32
CPU days doesn't update pdlouis Information & Answers 3 2009-04-17 22:30
SkipTrialFactoring=1 doesn't work? cmokruhl Software 1 2002-10-15 19:04

All times are UTC. The time now is 08:25.

Sat Sep 26 08:25:51 UTC 2020 up 16 days, 5:36, 0 users, load averages: 1.46, 1.40, 1.34

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.