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 where is the primordial up to 10,000 and 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 , we know that any possible prime factor is going to have to have the form , which effectively guarantees that almost any Mersenne is going to pass this kind of weeding/screening out process since 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 timeconsuming. If you're doing a doublecheck 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.