Trial factoring speed

Hello,

I am using Windows XP (32-bit) with 32-bit Prime95 (25.9 build 3). I have an AMD Athlon 64 3200+.

For fun I started trial factoring exponents in the 99,000,000 range. I also started trial factoring exponents in the 199,000,000 range.

It seems that the exponents in the 199 million range trial factor *faster* than the smaller ones in the 99 million range. Is there a mathematical reason for this?

My worktodo.txt:

Factor=199999673,0,63
Factor=99999073,0,63

Trial factoring to 63 bits is faster on the bigger exponent. Does anyone else see similar results?

[akruppa]

Yes, there's a mathematical reason. A Mersenne number 2^[I]p[/I]-1 can only have factors of the form 2kp+1, so a larger exponent means there are fewer candidate factors to test below a given bound. There is some more info on the math behind GIMPS at http://www.mersenne.org/various/math.php

Alex

Ahhh, that makes sense. As p gets higher, there's less potential factors due to 2kp+1.

I had the mindset that for general numbers, the bigger the number, the longer the number of calculations and the longer the time it would take to trial factor all primes < 2^X.

Thanks for your quick response.

[ATH]

It's because the bitdepth is the "standard" choice for measuring trialfactoring, but for mersennenumbers it's not very logical, since we only test every 2*k*p from k=1,2,3.....

For your exponent 99999073 k-values up to 2^63/(2*99999073) = 46.1*10⁹ are tested, but for 199999673 only k-values up to 2^63/(2*199999673) = 23.1 * 10⁹ are tested. So if you test 199999673 to 64bit instead it will correspond to almost the same number of tests and you'll see that 199999673 will take longer.