TreeSieve: Fast individual trial factoring
- I have made a new fast program for individual trial factoring of large numbers.
TreeSieve 1.0 alpha is at http://hjem.get2net.dk/jka/math/treesieve.zip
The speed relies on asymptotically fast modulus by the GMP (GNU Multiple
Precision) library from http://www.swox.com/gmp
The program can cooperate somewhat with pfgw.exe but I recommend the algorithm
is implemented directly in PFGW instead - a job for Phil Carmody?
My Athlon timings show trial factoring by TreeSieve is around 6 times faster
than PFGW (using libgmp-3.dll for Athlon) at 10000 digits, 12 times faster at
50000 digits, and 17 times faster at 100000 digits.
Maybe Woltman's FFT code instead of GMP on large numbers could make it even
faster. I don't know the workings of Woltman's code and PFGW source.
Jens Kruse Andersen
- Yes, Jens, it would be good if you could liaise with Phil.
As I recall, he got a factor of 14 speed-up for individual
factoring of GenLuc numbers, perhaps around 10k digits.
However, let us not be misled by such large-sounding
possible speed-ups of pfgw -f.
Suppose, for example, that pfgw -f were 10 times faster.
Then one could, say, trial factor to 10G, instead of, say, 1G,
using the same trial-factoring_time/PrPing_time ratio.
That results in a 10% saving in the PrPing-time,
and a somewhat smaller saving in the total time.
Moral: for factor of 10 in pfgw -f,
read 10% in total time;
worth having, but not sensational.