Sander Hoogendoorn writes:
Last weekend when i was testing Prime 95 i noticed that factoring
low numbers took much longer as high numbers.
Factoring M17XXX from 2^52 to 2^54 took minutes per pass while
factoring M9XXXXXX from 2^52 to 2^54 took about one minute to
complete the whole factoring. How is this possible?
All factors of a Mersenne number with a prime exponent, p, are of the
form 2*k*p + 1 where k is a natural number (positive integer). So the
larger p is, the fewer the number of possible factors between two
constants like 2^52 and 2^54. In this case, 17XXX divided by 9XXXXXX
is at most 0.2%, so checking all the possible factors of M17XXX takes
about 500 times as much CPU as checking all the possible factors of
M9XXXXXX within the same range of numbers.
This a large part of why higher exponent Mersennes are trial factored
farther than lower exponent Mersennes.
While I'm here, I'll mention for the newcomers that I collect all
sorts of factoring data on Mersenne numbers, including George
Woltman's ECM & GIMPS data, the Cunningham Project ftp site data
maintained by Paul Leyland, Conrad Curry's Factor98 data, and directly
from interested individuals like yourself; just send it to me in
email, plain text or as MIME attachment(s). The data I've collected
for exponents under 200,000 is available below. I have data for many
larger exponents, including all primes thru 21.5 million or so, but do
not have room on my ISP's web server to upload it.
Will
http://www.garlic.com/~wedgingt/mersenne.html (proofs, links, etc.)
mersfmt.txt (data format description)
mersdata.zip (data, zip'd)
mersdata.tgz (same data, different packing)
factoredM.txt (completely factored Mersennes)
...
