mersenneforum.org Why LMH doesn't sieve
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-11, 16:57 #1 geoff     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 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.
2005-04-13, 17:51   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

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.

 2005-04-13, 19:12 #3 wblipp     "William" May 2003 New Haven 1001001101102 Posts 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.
2005-04-18, 09:53   #4

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

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

 2005-04-18, 10:37 #5 geoff     Mar 2003 New Zealand 13×89 Posts 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.
 2005-04-23, 04:24 #6 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 6 2014-02-12 14:15 kolen Information & Answers 5 2013-06-02 20:31 binu Factoring 3 2013-04-13 16:32 pdlouis Information & Answers 3 2009-04-17 22:30 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

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.