View Single Post
Old 2019-12-16, 07:21   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

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