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

Toward a Polynomial Time Factoring Algorithm.

Expand Messages
  • Kermit Rose
    Toward a Polynomial Time Factoring Algorithm. Goal: To factor positive integer z. Select positive integer t, slightly larger than sqrt(z). t**2 - z = d s**2
    Message 1 of 1 , Mar 6, 2008
    • 0 Attachment
      Toward a Polynomial Time Factoring Algorithm.

      Goal: To factor positive integer z.


      Select positive integer t, slightly larger than sqrt(z).

      t**2 - z = d s**2

      where d is the square free part of ( t**2 - z).

      In the ring of integers adjoin sqrt(d),

      z factors as ( t - s sqrt(d) ) ( t + s sqrt(d) )

      If we can factor ( t + s sqrt(d) ) in that ring, then we will
      have the factors of z.

      Suppose (a1 + b1 sqrt(d) ) (a2 + b2 sqrt(d) ) = t + s sqrt(d)

      (a1 a2 + b1 b2 d) + ( a1 b2 + b1 a2) sqrt(d) = t + s sqrt(d)

      t = a1 a2 + b1 b2 d

      s = a1 b2 + b1 a2

      Factor t = t1 t2 and s = s1 s2.

      We may choose t so that its factors are known.

      If s is not easily factored, we may apply this very algorithm
      recursively to factor s.

      Alternatively, we could try a few different t's to see if any of them
      yielded an value for s that is easy to factor.


      t = a1 a2 + b1 b2 d

      becomes

      a1 a2 + b1 b2 d = t1 t2

      and

      s = a1 b2 + b1 a2

      becomes

      a1 b2 + b1 a2 = s1 s2


      Set

      t1 = e1 h1 + f1 g1
      t2 = e2 h2 + f2 g2
      s1 = e3 h3 + f3 g3
      s2 = e4 h4 + f4 g4


      At this stage, t1,t2, s1,s2 are known values, and

      e1,e2,e3,e4,f1,f2,f3,f4,g1,g2,g3,g4,h1,h2,h3,h4 are unknown parameters.


      t1 t2 = ( e1 h1 + f1 g1 ) ( e2 h2 + f2 g2 )
      = (e1 e2 - f1 g2)(-g1 f2 + h1 h2) + (e1 f2 + f1 h2) (g1 e2 + h1 g2)


      = t = a1 a2 + b1 b2 d


      Set

      a1 = e1 e2 - f1 g2

      a2 = -g1 g2 + h1 h2

      d b1 = e1 f2 + f1 h2

      b2 = g1 e2 + h1 g2


      s1 s2 = ( e3 h3 + f3 g3 ) ( e4 h4 + f4 g4 )
      = (e3 e4 - f3 g4)(-g3 f4 + h3 h4) + (e3 f4 + f3 h4) (g3 e4 + h3 g4)

      = s = a1 b2 + b1 a2


      Set

      a1 = (e3 e4 - f3 g4)

      b2 = (-g3 f4 + h3 h4)

      b1 = (e3 f4 + f3 h4)

      a2 = (g3 e4 + h3 g4)


      Comparing the two equation sets, we see that

      a1 = e1 e2 - f1 g2 = (e3 e4 - f3 g4)

      a2 = -g1 g2 + h1 h2 = (g3 e4 + h3 g4)

      d b1 = e1 f2 + f1 h2 = d (e3 f4 + f3 h4)

      b2 = g1 e2 + h1 g2 = (-g3 f4 + h3 h4)



      We may use two by two matrices to simplify the explanation.


      a1 = e1 e2 - f1 g2 = (e3 e4 - f3 g4)


      e1 e2 - f1 g2 is the determinant of

      [ e1 f1 ]
      [ g2 e2 ]


      e3 e4 - f3 g4 is the determinant of

      [ e3 f3 ]
      [ g4 e4 ]

      For these two matrices to have the same determinant, one of them is the
      other
      times a matrix with determinant equal to 1.

      Set

      [ e1 f1] = [ u1/v1 u2/v2 ] [ e3 f3 ] = [(u1/v1) e3 +(u2/v2) g4
      (u1/v1) f3 +(u2/v2) e4 ]
      [ g2 e2] = [ u3/v3 u4/v4 ] [ g4 e4 ] = [(u3/v3) e3 +(u4/v4) g4
      (u3/v3) f3 +(u4/v4) e4 ]


      where ( u1/v1) (u4/v4) - (u2/v2)(u3/v3) = 1

      which yields

      e1 = (u1/v1) e3 +(u2/v2) g4
      f1 = (u1/v1) f3 +(u2/v2) e4
      g2 = (u3/v3) e3 +(u4/v4) g4
      e2 = (u3/v3) f3 +(u4/v4) e4




      a2 = -g1 g2 + h1 h2 = (g3 e4 + h3 g4)

      -g1 g2 + h1 h2 is the determinant of

      [ h1 g1 ]
      [ g2 h2 ]


      (g3 e4 + h3 g4)

      is the determinant of

      [ g3 -h3 ]
      [ g4 e4 ]


      (g3 e4 + h3 g4)

      is the determinant of

      [g3 -h3 ]
      [g4 e4 ]

      Set

      [ h1 g1 ] = [ u5/v5 u6/v6 ] [ g3 -h3 ]= [ (u5/v5) g3 + (u6/v6) g4
      -(u5/v5) h3 + (u6/v6) e4]
      [ g2 h2 ] = [ u7/v7 u8/v8 ] [ g4 e4 ]= [ (u7/v7) g3 + (u8/v8) g4
      -(u7/v7) h3 + (u8/v8) e4]


      Which yields

      h1 = (u5/v5) g3 + (u6/v6)
      g1 = -(u5/v5) h3 + (u6/v6) e4
      g2 = (u7/v7) g3 + (u8/v8)
      h2 = -(u7/v7) h3 + (u8/v8) e4


      d b1 = e1 f2 + f1 h2 = d (e3 f4 + f3 h4)


      e1 f2 + f1 h2

      is the determinant of

      [ e1 -f1 ]
      [ h2 f2 ]


      d (e3 f4 + f3 h4)

      is the determinant of


      [ d e3 -d f3 ]
      [ h4 f4 ]




      Set



      [e1 -f1]=[u9/v9 u10/v10 ][d e3 -d f3]=[(u9/v9)d e3+(u10/v10)h4
      -(u9/v9)d f3+(u10/v10) f4 ]
      [h2 f2]=[u11/v11 v12/v12 ][ h4 f4 ]=[(u11/v11)d e3+(u12/v12)h4
      -(u11/v11)d f3+(u12/v12)f4]



      Yielding

      e1 = (u9/v9)d e3+(u10/v10)h4
      -f1 = -(u9/v9)d f3+(u10/v10) f4
      h2 = (u11/v11)d e3+(u12/v12)h4
      f2 = -(u11/v11)d f3+(u12/v12)f4



      b2 = g1 e2 + h1 g2 = (-g3 f4 + h3 h4)


      g1 e2 + h1 g2

      is the determinant of

      [g1 h1]
      [g2 e2]




      (-g3 f4 + h3 h4)

      is the determinant of

      [h3 g3]
      [f4 h4]



      Set




      [g1 h1]=[u13/v13 u14/v14][h3 g3]=[(u13/v13)h3+(u14/v14)f4
      (u13/v13)g3+(u14/v14)h4]
      [g2 e2]=[u15/v15 u16/v16][f4 h4]=[(u15/v15)h3+(u16/v16)f4
      (u15/v15)g3+(u16/v16)h4]


      which yields

      g1 = (u13/v13)h3+(u14/v14)f4
      h1 = (u13/v13)g3+(u14/v14)h4
      g2 = (u15/v15)h3+(u16/v16)f4
      e2 = (u15/v15)g3+(u16/v16)h4

      We now have 16 equations in the 16 variables

      e1,e2,e3,e4,f1,f2,f3,f4,g1,g2,g3,g4,h1,h2,h3,h4

      with the parameter variables to be considered as if they were constants
      at this time.







      e1 = (u1/v1) e3 +(u2/v2) g4
      f1 = (u1/v1) f3 +(u2/v2) e4
      g2 = (u3/v3) e3 +(u4/v4) g4
      e2 = (u3/v3) f3 +(u4/v4) e4




      h1 = (u5/v5) g3 + (u6/v6)
      g1 = -(u5/v5) h3 + (u6/v6) e4
      g2 = (u7/v7) g3 + (u8/v8)
      h2 = -(u7/v7) h3 + (u8/v8) e4




      e1 = (u9/v9)d e3+(u10/v10)h4
      -f1 = -(u9/v9)d f3+(u10/v10) f4
      h2 = (u11/v11)d e3+(u12/v12)h4
      f2 = -(u11/v11)d f3+(u12/v12)f4




      g1 = (u13/v13)h3+(u14/v14)f4
      h1 = (u13/v13)g3+(u14/v14)h4
      g2 = (u15/v15)h3+(u16/v16)f4
      e2 = (u15/v15)g3+(u16/v16)h4



      Solve these 16 equations for



      e1,e2,e3,e4,f1,f2,f3,f4,g1,g2,g3,g4,h1,h2,h3,h4

      in terms of

      u1,v1,u2,v2,u3,v3,u4,v4,u5,v5,u6,v6,u7,v7,u8,v8,
      u9,v9,u10,v10,u11,v11,u12,v12,u13,v13,u14,v14,u15,v15,u16,v16


      Note the constraint that

      (u1/v1) (u4/v4) - (u2/v2) (u3/v3) = 1


      (u5/v5) (u8/v8) - (u6/v6) (u7/v7) = 1


      (u9/v9) (u12/v12) - (u10/v10) (u11/v11) = 1


      (u13/v13) (u16/v16) - (u14/v14) (u15/v15) = 1



      These constraints are easy to satisfy by using
      the fact that the determinant of the product of matrices is
      the product of their determinants.


      Define

      [u1/v1 u2/v2]=[1 m1/n1] [1 0] [1 m3/n3]
      [u3/v3 u4/v4]=[0 1 ] [m2/n2 1] [0 1 ]



      And similarily for the other u and v parameters.


      We should be able to find numerical or parametric solutions to these 16
      equations
      in terms of the m's and n's.



      e1 = (u1/v1) e3 +(u2/v2) g4
      f1 = (u1/v1) f3 +(u2/v2) e4
      g2 = (u3/v3) e3 +(u4/v4) g4
      e2 = (u3/v3) f3 +(u4/v4) e4




      h1 = (u5/v5) g3 + (u6/v6)
      g1 = -(u5/v5) h3 + (u6/v6) e4
      g2 = (u7/v7) g3 + (u8/v8)
      h2 = -(u7/v7) h3 + (u8/v8) e4




      e1 = (u9/v9)d e3+(u10/v10)h4
      -f1 = -(u9/v9)d f3+(u10/v10) f4
      h2 = (u11/v11)d e3+(u12/v12)h4
      f2 = -(u11/v11)d f3+(u12/v12)f4




      g1 = (u13/v13)h3+(u14/v14)f4
      h1 = (u13/v13)g3+(u14/v14)h4
      g2 = (u15/v15)h3+(u16/v16)f4
      e2 = (u15/v15)g3+(u16/v16)h4











      A solution to those equations can be pluged into


      a1 = e1 e2 - f1 g2

      a2 = -g1 g2 + h1 h2

      d b1 = e1 f2 + f1 h2

      b2 = g1 e2 + h1 g2



      x = a1 **2 - d b1**2

      and

      y = a2**2 - d b2**2


      Since

      (a1 + b1 sqrt(d) ) (a2 + b2 sqrt(d) ) = t + s sqrt(d)



      I have not worked out yet the details of the equation solution because

      solving 16 linear equations in 16 variables is tedious by hand.


      Thus I have not been able to verify what actually happens at the step after
      I have the solutions to the equations.

      Also, since I have done all of this preceeding derivation by hand
      calculation,
      please proofread what I've done. Assume that I may have made many
      mistakes is the
      details of the derivation.

      In spite of this, the overall theory is simple.


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