20191215, 17:34  #1 
"James Short"
Mar 2019
Canada
17 Posts 
How are composite Mersenne's sieved (weeded) out?
Is there a sieving process that is done before the LucasLehmer primality test is run to test if a Mersenne is prime?
Normally (that is for random integers), one simply uses a primordial number  ex, product of all primes up to say 10,000, and then compute where is the primordial up to 10,000 and is some integer whose primality we wish to determine. However when it comes to Mersenne's this simple approach doesn't work too well I imagine since for a given Mersenne , we know that any possible prime factor is going to have to have the form , which effectively guarantees that almost any Mersenne is going to pass this kind of weeding/screening out process since almost all the time. Of course I suppose if one is using an extremely large primordial like say up to , this procedure could have a bit of merit since you've essentially got yourself a polynomialtime factoring algorithm with as your upper limit. As an aside, I noticed that the LucasLehmer primality test can sort of be used as a bit of a Pollardrho factoring algorithm, with and . For example, if we were determining the primality of the Mersenne , the LLtest says we need to calculate over where and . However if you stop at and compute you obtain the prime factor 47 and the LLtest no longer needs to continued since we know now that is not prime. 
20191215, 18:26  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9574_{10} Posts 

20191215, 22:48  #3  
"James Short"
Mar 2019
Canada
17 Posts 
Quote:
Interesting that the p1 test isn't used straight away, but rather a trivial Sieve of Eratosthenes. Anyways, I'd imagine that the bounds B and B' must be awfully small. 

20191216, 02:22  #4  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
37×157 Posts 
Quote:
https://www.mersenneforum.org/showpo...23&postcount=6 P1 bounds are typically optimized to maximize probable time saved, also. https://www.mersenneforum.org/showpo...7&postcount=23 An appropriate set of P1 bounds is a rather lengthy computation compared to the beginning TF levels. Last fiddled with by kriesel on 20191216 at 02:23 

20191216, 07:21  #5  
Aug 2006
3·1,993 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne number with exponent 333333367 is composite  TheGuardian  GPU Computing  25  20190509 21:53 
Factoring composite Mersenne numbers using Pollard Rho  jshort  Factoring  9  20190409 16:34 
New Factor leaves a C168 Mersenne Composite  wblipp  ElevenSmooth  7  20130117 02:54 
Mersenne primes have highly composite p1?  ATH  Math  3  20090615 13:11 
Mersenne composite using fibonacci  TTn  Math  5  20021123 03:54 