mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-12-15, 17:34   #1
jshort
 
"James Short"
Mar 2019
Canada

1010 Posts
Default How are composite Mersenne's sieved (weeded) out?

Is there a sieving process that is done before the Lucas-Lehmer 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 gcd(n,p) where n is the primordial up to 10,000 and p 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 M_{p} = 2^{p} - 1, we know that any possible prime factor q is going to have to have the form 1 + k \cdot 2 \cdot p, which effectively guarantees that almost any Mersenne is going to pass this kind of weeding/screening out process since gcd(n,2^{p} - 1) = 1 almost all the time.

Of course I suppose if one is using an extremely large primordial like say up to 10^{12}, this procedure could have a bit of merit since you've essentially got yourself a polynomial-time factoring algorithm with 10^{12} as your upper limit.

As an aside, I noticed that the Lucas-Lehmer primality test can sort of be used as a bit of a Pollard-rho factoring algorithm, with x_{1} = 4 and a = -2.

For example, if we were determining the primality of the Mersenne M = 2^{23} - 1, the LL-test says we need to calculate x_{22} over Z_{M} where x_{1} = 4 and x_{n+1} = x_{n}^{2} - 2. However if you stop at x_{12} and compute gcd(x_{12} - x_{1}, 2^{23} - 1) you obtain the prime factor 47 and the LL-test no longer needs to continued since we know now that 2^{23} - 1 is not prime.
jshort is offline   Reply With Quote
Old 2019-12-15, 18:26   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(3,3^1118781+1)/3

11·19·43 Posts
Default

https://www.mersenne.org/various/math.php
Batalov is offline   Reply With Quote
Old 2019-12-15, 22:48   #3
jshort
 
"James Short"
Mar 2019
Canada

2×5 Posts
Default

Quote:
Originally Posted by Batalov View Post
Thank you sir.

Interesting that the p-1 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.
jshort is offline   Reply With Quote
Old 2019-12-16, 02:22   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

7×499 Posts
Default

Quote:
Originally Posted by jshort View Post
Interesting that the p-1 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.
The order of TF first, lowest bits first, P-1 later is the outcome of doing first, what gives the most factored per unit effort, and so maximizing time saved.
https://www.mersenneforum.org/showpo...23&postcount=6
P-1 bounds are typically optimized to maximize probable time saved, also.
https://www.mersenneforum.org/showpo...7&postcount=23
An appropriate set of P-1 bounds is a rather lengthy computation compared to the beginning TF levels.

Last fiddled with by kriesel on 2019-12-16 at 02:23
kriesel is online now   Reply With Quote
Old 2019-12-16, 07:21   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×29×101 Posts
Default

Quote:
Originally Posted by jshort View Post
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 gcd(n,p) where n is the primordial up to 10,000 and p 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 M_{p} = 2^{p} - 1, we know that any possible prime factor q is going to have to have the form 1 + k \cdot 2 \cdot p, which effectively guarantees that almost any Mersenne is going to pass this kind of weeding/screening out process since gcd(n,2^{p} - 1) = 1 almost all the time.
Right. As an improvement you could use a product of just the numbers of the appropriate form, but the numbers are just so big that taking a single gcd is very time-consuming. If you're doing a double-check the numbers are about 50 MB, and if you gather together 50 MB worth of factors (this would be about 8 million) you'd need tens of seconds, or ~10^4 clock cycles per factor. Trial division -- or rather the specialized operation that we call trial division in this context -- is much more efficient.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne number with exponent 333333367 is composite TheGuardian GPU Computing 25 2019-05-09 21:53
Factoring composite Mersenne numbers using Pollard Rho jshort Factoring 9 2019-04-09 16:34
New Factor leaves a C168 Mersenne Composite wblipp ElevenSmooth 7 2013-01-17 02:54
Mersenne primes have highly composite p-1? ATH Math 3 2009-06-15 13:11
Mersenne composite using fibonacci TTn Math 5 2002-11-23 03:54

All times are UTC. The time now is 21:40.

Thu Apr 9 21:40:45 UTC 2020 up 15 days, 19:13, 0 users, load averages: 3.34, 2.36, 2.03

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.