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

Re: {Spam?} [PrimeNumbers] Performance of factoring algorithms

Expand Messages
  • 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 1 of 2 , Apr 23 2:09 AM
    View Source
    • 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.