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

Speeding up trial division algorithm

Expand Messages
  • Kermit Rose
    I implemented an idea that I thought might speed up the trial division method of finding the factors of an integer. These are the times I recorded for 5
    Message 1 of 2 , Mar 29, 2008
    • 0 Attachment
      I implemented an idea that I thought might speed up the trial division
      method of finding the factors of an integer.

      These are the times I recorded for 5 integers of 14 digits.

      >>> SuperWheel30Factor(m14[0])
      Found factor after 103756 turns of the wheel.
      Found factor after 3.2610001564 seconds.
      [3112687L, 5524481L]


      >>> SuperWheel30Factor(m14[1])
      Found factor after 174799 turns of the wheel.
      Found factor after 5.50600004196 seconds.
      [5243971L, 6350647L]


      >>> SuperWheel30Factor(m14[2])
      Found factor after 156296 turns of the wheel.
      Found factor after 4.91499996185 seconds.
      [4688897L, 6919361L]


      >>> SuperWheel30Factor(m14[3])
      Found factor after 258797 turns of the wheel.
      Found factor after 8.37300014496 seconds.
      [7763923L, 9247993L]


      >>> SuperWheel30Factor(m14[4])
      Found factor after 117267 turns of the wheel.
      Found factor after 3.6779999733 seconds.
      [3518017L, 8590889L]


      Has anyone else experimented with trial division algorithm?

      I'm wondering if these times represent a significant speed up of the
      algorithm.

      I know that there exist other algorithms that are much much faster.

      I'm not asking if these are short times for factoring algorithms in general.

      I'm asking if these are short times for the trial division algorithm.


      Kermit Rose



      < kermit@... >
    • Paul Leyland
      ... Wow! I m impressed that you have a clock capable of measuring the time of a computation with 100ps accuracy! ... Many many times over the last few
      Message 2 of 2 , Apr 11, 2008
      • 0 Attachment
        On Sun, 2008-03-30 at 04:52, Kermit Rose wrote:
        > I implemented an idea that I thought might speed up the trial division
        > method of finding the factors of an integer.

        > Found factor after 3.6779999733 seconds.

        Wow! I'm impressed that you have a clock capable of measuring the time
        of a computation with 100ps accuracy!

        > Has anyone else experimented with trial division algorithm?

        Many many times over the last few centuries.

        > I'm wondering if these times represent a significant speed up of the
        > algorithm.

        Who knows? They're faster than I can do on my fingers, or even with
        pencil and paper. Perhaps if you told us how many machine cycles they
        took, and with the machine architecture, rather than just the elapsed
        time we might then have enough information to make an informed comment.


        Paul



        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.