> >No two Mersenne (numbers) can have the same prime divisor, as I recall.
Yes, every odd prime *belongs* to a given Mersenne exponent x, (the exponent
of 2 mod p). Then p divides 2^n-1 if and only if x divides n. x certainly
divides p-1, but x may not necessarily be a prime.
> >prime), we can get a list of primes that no longer need to be tried as
> >divisors of 2^p - 1. So sure, use the +/-1 mod 8 rules, eliminating a
> >series of trial divisors, and pare the list even more by comparing to
known
> >divisors of Mersenne primes.
> I don't think this would be very effective for the simple reason that it
would
> take longer to read from disk than it would to just check the factor.
Almost definitely. If we have a candidate prime divisor, X=2kp+1, we'd have
to look for all the entries for the divisors of 2k in a database, while the
value of 2^p-1 mod X can be calculated in about two dozen squarings and
shifts (mod X).
> It is possible to do this using methods like Chris Nash's PriMers method.
> In this, you calculate all the prime numbers ==+/-1 mod 8 up to a certain
> point. Then you can factor that prime-1, and test the mersenne exponents
that
> are factors.
That's the theory. Given a prime p, find x above. The algorithm is not too
difficult
get an admissible prime (+-1 mod 8)
begin with x=p-1
for every prime factor q of x, test 2^(x/q) mod p. If it's one, then replace
x by x/q and repeat. If none of these are 1, then x is the exponent to which
p belongs.
x however is very rarely much smaller than p-1 - I'll leave a full analysis
to others, but typically you'll see (p-1), (p-1)/2, maybe a few others, but
rarely much smaller. (To be (p-1)/d, 2 would have to be a d'th root of
unity, and the probability of that is "about" 1/d). For even a 32-bit prime,
the probability it belongs to an exponent in the current search range (2^23)
is very small indeed (1000 to 1?), not to mention of course that the
exponent it belongs to will probably be composite. While testing is quite
quick, expect to scan many thousands of primes before you get an
'interesting' factor this way (even more with larger factors). In theory
it's quicker than testing the same prime a handful of times for many
different exponents, but in practice it generates many results for composite
exponents, or huge exponents, which we may not necessarily be interested
in - at least, not for a long time. I have a very silly result somewhere
that M(some 62-bit exponent) is composite with a known factor - the Mersenne
number itself would have 10^18 digits...
Chris Nash
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
