View Single Post
2019-12-16, 07:21   #5
CRGreathouse

Aug 2006

3·1,993 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.