mersenneforum.org > Math How are composite Mersenne's sieved (weeded) out?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-12-15, 17:34 #1 jshort   "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 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.
 2019-12-15, 18:26 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 59×163 Posts
2019-12-15, 22:48   #3
jshort

"James Short"
Mar 2019

17 Posts

Quote:
 Originally Posted by Batalov https://www.mersenne.org/various/math.php
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.

2019-12-16, 02:22   #4
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22·1,481 Posts

Quote:
 Originally Posted by jshort 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

2019-12-16, 07:21   #5
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 Originally Posted by jshort 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post TheGuardian GPU Computing 25 2019-05-09 21:53 jshort Factoring 9 2019-04-09 16:34 wblipp ElevenSmooth 7 2013-01-17 02:54 ATH Math 3 2009-06-15 13:11 TTn Math 5 2002-11-23 03:54

All times are UTC. The time now is 11:34.

Sun Dec 5 11:34:18 UTC 2021 up 135 days, 6:03, 0 users, load averages: 1.13, 1.09, 1.21