"Sander Hoogendoorn" <[EMAIL PROTECTED]> asks
> 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?
>
Only primes in [2^52, 2^54] which are congruent to
1 modulo 17XXX (or modulo 9XXXXXX) need be checked. [There are other
restrictions, such as the prime being == +- 1 modulo 8.]
For the larger exponent, the density of candidate divisors
is 17XXX / 9XXXXXX ~= 1/50 times as large.
For the larger exponent, the cost of testing each divisor
(using the binary method of exponentiation) is
log_2(9XXXXXX) / log_2(17XXX) ~= 23/14 times as long.
Overall, when the interval [2^52, 2^54] is fixed,
the checking for the larger exponent proceeds
50 * (14/23) ~= 30 times as fast.
On the other hand LL testing for the larger
exponent takes 50 times as many iterations, and each
iteration takes about 50 * (23/14) ~= 80 times as long,
so this cost grows by a factor of 4000.
Keeping the (LL costs)/(factoring costs) ratio constant,
the factoring could search an interval
30 * 4000 ~= 2^17 times as long. Alas, [2^69, 2^71]
needs more than 64 bits of precision to store candidate
divisors, so you probably stop factoring at 2^64 or switch to
other algorithms.
