Loading ...
Sorry, an error occurred while loading the content.
 

TreeSieve: Fast individual trial factoring

Expand Messages
  • Jens Kruse Andersen
    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
    • David Broadhurst
      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,
        read 10% in total time;
        worth having, but not sensational.

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.