Trial factoring benchmark interpretation

[__HRB__]

http://www.mersenne.org/report_bench...Get+Benchmarks

How do I interpret the value in the last column?
Doesn't it matter how many bits 2^N-1 has?
Does it describe the time taken to check whether 2^N-1 is divisible by all possible factors with less than 65 bits?

If it describes the average time taken to check whether 2^N-1 is divisible by a 65 bit number, wouldn't this be very slow, since we're only checking about 10 million factors per day?

Because, if one multiplies ~500.000 factors with divide-and-conquer, then computes the remainders with divide-and-conquer (using Newton's method and fast multiplication for the division), then one could check 10 million factors for a 33 million bit Mersenne number in a couple of minutes.

[Prime95]

I'd have to check the code to answer your question exactly.

It is something like the time it takes to trial factor M35000001 with all possible factors in a 12KB sieve. A 12KB sieve = 96K bits. The small factors sieve would eliminate a large percentage (maybe 75-90% ?). So the benchmark times ~10-15 thousand trial factoring attempts? Maybe someone can look at the code and give you a more accurate answer.

[Mini-Geek]

http://mersenne-aries.sili.net/throughput.php contains some reverse-engineered estimates for the number of iterations used for various TF bit levels. (i.e. (the timing listed for bit level 65) * (iterations for bit level 65) = (total time for bit level 65))

[__HRB__]

Originally Posted by Prime95

I'd have to check the code to answer your question exactly.

It is something like the time it takes to trial factor M35000001 with all possible factors in a 12KB sieve. A 12KB sieve = 96K bits. The small factors sieve would eliminate a large percentage (maybe 75-90% ?). So the benchmark times ~10-15 thousand trial factoring attempts? Maybe someone can look at the code and give you a more accurate answer.

That sounds reasonable.

If we assume that we can do a multiply in 1.5x-3x the time for an LL-iteration, the division/mod is 2x-3x multiplies, then for ~600.000 possible factors with 64-bits, the run-time for the method that wouldn't assume any special form would be something around 15x-30x an LL-iteration for M35000001, which is slower (but in the same ballpark).

Originally Posted by Mini-Geek

http://mersenne-aries.sili.net/throughput.php contains some reverse-engineered estimates for the number of iterations used for various TF bit levels. (i.e. (the timing listed for bit level 65) * (iterations for bit level 65) = (total time for bit level 65))

Thanks. Interesting info.