## TreeSieve: Fast individual trial factoring

Expand Messages
• 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
Message 1 of 2 , Mar 21, 2004
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
Message 2 of 2 , Mar 21, 2004
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,