View Single Post
Old 2019-12-15, 17:34   #1
"James Short"
Mar 2019

17 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