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

Performance of factoring algorithms

Expand Messages
  • Kermit Rose
    Hello friends. I ve constructed a factoring algorithm that I call ProportionateFactor because, to factor positive integer z, it seeks to find four integers
    Message 1 of 2 , Apr 21, 2012
    • 0 Attachment
      Hello friends.

      I've constructed a factoring algorithm that I call ProportionateFactor
      because, to factor positive integer z, it seeks to find four integers
      t0,t1,t2,t3 such that

      t0 + t1 + t2 + t3 = z
      and
      t0 t3 = t1 t2.

      Then it checks to see if GCD(t0+t1,z) is strictly between 1 and z.
      It often happens that GCD(t0+t1,z) is exactly equal to z.

      In the following I have tested my new factoring algorithm against
      several other algorithms.

      The third number in the output vector is the number of cycles within the
      algorithm that found the factors.

      ProportionateFactor appears to be in close competition with (p-1)
      factoring algorithm.

      I had had hopes that ProportionateFactor would be much faster, but I did
      not anticipate that most of the time
      GCD(z,t0+t1) would be exactly equal to z.


      >>> Factor(10**14+13)

      In Factor. z = 100000000000013
      [[173L, 578034682081L, 27], 'ProportionateFactor: Level A2']


      >>> Factor(10**14+27)

      In Factor. z = 100000000000027
      [[751L, 133155792277L, 3], 'ProportionateFactor: Level A2']


      >>> Factor(10**14+37)

      In Factor. z = 100000000000037
      Found factor by p-1.
      [[53799857L, 1858741L], 1452]


      >>> Factor(10**14+39)

      In Factor. z = 100000000000039
      Found factor by p-1.
      [[2596823L, 38508593L], 49]


      >>> Factor(10**14+49)

      In Factor. z = 100000000000049
      [[109L, 917431192661L, 16], 'ProportionateFactor: Level A3']


      >>> Factor(10**14+51)

      In Factor. z = 100000000000051
      [[6653L, 15030813167L, 2795], 'ProportionateFactor: Level A3']


      In Factor. z = 100000000000057
      [[23L, 4347826086959L, 1], 'ProportionateFactor: Level A4']
      >>> Factor(10**14+61)


      >>> Factor(10**14+63)

      In Factor. z = 100000000000063
      [[572587L, 174645949L, 11175], 'ProportionateFactor: Level A4']
      >>> Factor(10**14+67)



      In Factor. z = 100000000000073
      Found factor by Pollard Rho.
      [[13371821L, 7478413L], 961]
      >>> Factor(10**14+79)

      In Factor. z = 100000000000079
      Found factor by trial division.
      [[19, 5263157894741L], 3]
      >>> Factor(10**14+81)

      In Factor. z = 100000000000081
      [[47309L, 2113762709L, 11545], 'ProportionateFactor: Level A3']
    • Paul Leyland
      ... Without any information on how you propose to find the t_i it s next to impossible to give any meaningful analysis of your algorithm. Paul
      Message 2 of 2 , Apr 23, 2012
      • 0 Attachment
        On Sat, 2012-04-21 at 19:21 -0400, Kermit Rose wrote:
        >
        > Hello friends.
        >
        > I've constructed a factoring algorithm that I call ProportionateFactor
        > because, to factor positive integer z, it seeks to find four integers
        > t0,t1,t2,t3 such that
        >
        > t0 + t1 + t2 + t3 = z
        > and
        > t0 t3 = t1 t2.
        >
        > Then it checks to see if GCD(t0+t1,z) is strictly between 1 and z.
        > It often happens that GCD(t0+t1,z) is exactly equal to z.
        >
        > In the following I have tested my new factoring algorithm against
        > several other algorithms.
        >
        > The third number in the output vector is the number of cycles within
        > the
        > algorithm that found the factors.
        >
        > ProportionateFactor appears to be in close competition with (p-1)
        > factoring algorithm.
        >
        > I had had hopes that ProportionateFactor would be much faster, but I
        > did
        > not anticipate that most of the time
        > GCD(z,t0+t1) would be exactly equal to z.

        Without any information on how you propose to find the t_i it's next to
        impossible to give any meaningful analysis of your algorithm.


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