On 22 Jun 99, at 20:30, [EMAIL PROTECTED] wrote:
> <<Now we can filter out multiples of small primes>>
> I'm assuming that we don't need to divide by factors divisible by 3 or 5,
> etc, because a Mersenne number cannot be divisible by 3 or 5 because they
> don't have the structure 2kp+1 themselves? (Excluding the REALLY low Mersenne
> numbers).
Actually you've missed the obvious point. The smallest factor of
_any_ number is prime. So we've no need to test any candidate factors
which are "obviously" composite (i.e. we can see easily that they're
divisible by any small prime). And, if p is prime, we know
(mathematically) that the smallest possible factor of 2^p-1 is 2p+1.
So 2^p-1 cannot be divisible by _any_ prime < 2p.
> Ideally, we'd like to only test factors that are prime
> themselves.... Am I right?
Yes. But you have to balance out the effort involved in finding out
whether the candidate factor is probably prime against the effort
involved in doing a trial division. I can do a trial division of
2^p-1 by f for any p < 2^32, f < 2^63 in 10 microseconds or less on a
PII-350. Checking whether f is _really_ prime is going to take a lot
longer than that, unless you have a 2^63 bit lookup table lying about
somewhere in RAM ;-)
e.g. consider a Fermat test to base 2 (which is a long way from
proving primality, though it's a good first guess). We need to
compute 2^((2kp+1)-1) (mod 2kp+1). But, to check divisibility of
2^p-1 by 2kp+1, we only need to compute 2^p (mod 2kp+1), which is
obviously less effort!
Regards
Brian Beesley
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
