View Single Post
 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.