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

Factoring program not as good as I first thought

Expand Messages
  • Kermit Rose
    I had made the mistake of not putting in the counting steps for third level and fourth level combining of quadratic residues which were not integer squares.
    Message 1 of 1 , Jan 31, 2008
    • 0 Attachment
      I had made the mistake of not putting in the counting steps for third
      level and fourth level
      combining of quadratic residues which were not integer squares.

      With the revised counting, I see that the factoring of that 12 digit
      number indeed took more steps than
      that expected by trial division by primes.

      >>> x/13
      61556
      >>> steps
      211952

      I also had this thought.

      If we construct the difference matrix of all the mod z differences of
      the power square chain elements,
      and find a difference, d, that has the three properties that

      (1) the difference d is the sum of a chain of differences.
      By chain of differences, I mean a sequence of differences (a1**2 -
      a2**2) , (a2**2 - a3**2), (a3**2 - a4**2), . . .(ak**2 -aj**2)

      and
      (2) the difference d was not originally created by (a1 **2 - aj**2).

      and

      (3) Exactly one of a1, aj occurred in the calculation definition of d.

      That is, d was originally calculated as either (a1 **2 - b1**2) or
      (b2**2 - aj**2)

      which yields that b1**2 = aj**2 mod z or that b2**2 = a1**2 mod z.


      Solving this problem efficiently is thus equivalent to the original
      factoring problem.


      Kermit Rose < kermit@... >







      Kermit Rose < kermit@... >
    Your message has been successfully submitted and would be delivered to recipients shortly.