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

Detailed illustration of polynomial time factoring algorithm

Expand Messages
  • Kermit Rose
    I am working on programming this algorithm in python. I expect to be able to prove that this algorithm works and is a polynomial time algorithm by factoring
    Message 1 of 4 , Jan 5, 2009
      I am working on programming this algorithm in python.

      I expect to be able to prove that this algorithm works and is a

      polynomial time algorithm by factoring
      the RSA challenge large integers.

      Detailed illustration of polynomial time factoring algorithm

      Factoring z = 105 = 3 * 5 * 7 by polynomial time factoring

      algorithm.


      1 105
      d1=0 2 52 even
      d2=0 4 26 even
      d3=1 8 13 odd
      d4=0 16 6 even
      d5=1 32 3 odd
      d6=1 64 1 odd


      1 + 8 + 32 + 64 = 105

      Test if there is a divisor of 105 between 2 and 4.

      (1+2 w1)
      (1+2 w1 +4 w2 + 8 [1-w3] + 16 w4 + 32 [1-w5] + 64[1-w6])
      =105

      *******************************************************

      1 + 8 + 32 + 64
      + 2 w1 + 2 w1 + 4 w1 + 16 w1 + 64 w1 + 128 w1
      + 4 w2
      - 8 w3
      +16 w4
      -32 w5
      -64 w6
      + 8 w1 w2
      -16 w1 w3
      +32 w1 w4
      -64 w1 w5
      -128 w1 w6 = 105


      *******************************************************


      + 2 w1 + 2 w1 + 4 w1 + 16 w1 + 64 w1 + 128 w1
      + 4 w2
      - 8 w3
      +16 w4
      -32 w5
      -64 w6
      + 8 w1 w2
      -16 w1 w3
      +32 w1 w4
      -64 w1 w5
      -128 w1 w6 = 0


      *******************************************************


      + 8 w1 + 16 w1 + 64 w1 + 128 w1
      + 4 w2
      - 8 w3
      +16 w4
      -32 w5
      -64 w6
      + 8 w1 w2
      -16 w1 w3
      +32 w1 w4
      -64 w1 w5
      -128 w1 w6 = 0


      *******************************************************


      + 2**3 w1 + 2**4 w1 + 2**6 w1 + 2**7 w1
      + 2**2 w2
      - 2**3 w3
      +2**4 w4
      -2**5 w5
      -2**6 w6
      + 2**3 w1 w2
      -2**4 w1 w3
      +2**5 w1 w4
      -2**6 w1 w5
      -2**7 w1 w6 = 0


      *******************************************************
      Divided by 2**2

      + 2**1 w1 + 2**2 w1 + 2**4 w1 + 2**5 w1
      + 2**0 w2
      - 2**1 w3
      +2**2 w4
      -2**3 w5
      -2**4 w6
      + 2**1 w1 w2
      -2**2 w1 w3
      +2**3 w1 w4
      -2**4 w1 w5
      -2**5 w1 w6 = 0


      w2 = 0


      *******************************************************

      w2 = 0

      + 2**1 w1 + 2**2 w1 + 2**4 w1 + 2**5 w1
      - 2**1 w3
      +2**2 w4
      -2**3 w5
      -2**4 w6
      -2**2 w1 w3
      +2**3 w1 w4
      -2**4 w1 w5
      -2**5 w1 w6 = 0




      *******************************************************
      Divided by 2**1

      w2 = 0

      + 2**0 w1 + 2**1 w1 + 2**3 w1 + 2**4 w1
      - 2**0 w3
      +2**1 w4
      -2**2 w5
      -2**3 w6
      -2**1 w1 w3
      +2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6 = 0

      w3 = w1




      *******************************************************


      w2 = 0
      w3 = w1

      + 2**0 w1 + 2**1 w1 + 2**3 w1 + 2**4 w1
      - 2**0 w1
      +2**1 w4
      -2**2 w5
      -2**3 w6
      -2**1 w1 w1
      +2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6 = 0

      *******************************************************


      w2 = 0
      w3 = w1

      + 2**3 w1 + 2**4 w1
      +2**1 w4
      -2**2 w5
      -2**3 w6
      +2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6 = 0

      *******************************************************
      Divided by 2

      w2 = 0
      w3 = w1

      + 2**2 w1 + 2**3 w1
      +2**0 w4
      -2**1 w5
      -2**2 w6
      +2**1 w1 w4
      -2**2 w1 w5
      -2**3 w1 w6 = 0

      w4 = 0

      *******************************************************


      w2 = 0
      w3 = w1
      w4 = 0

      + 2**2 w1 + 2**3 w1
      -2**1 w5
      -2**2 w6
      -2**2 w1 w5
      -2**3 w1 w6 = 0


      *******************************************************
      Divided by 2**1

      w2 = 0
      w3 = w1
      w4 = 0

      + 2**1 w1 + 2**2 w1
      -2**0 w5
      -2**1 w6
      -2**1 w1 w5
      -2**2 w1 w6 = 0

      w5 = 0

      *******************************************************


      w2 = 0
      w3 = w1
      w4 = 0
      w5 = 0

      + 2**1 w1 + 2**2 w1
      -2**1 w6
      -2**2 w1 w6 = 0


      *******************************************************

      Divided by 2**1

      w2 = 0
      w3 = w1
      w4 = 0
      w5 = 0

      + 2**0 w1 + 2**1 w1
      -2**0 w6
      -2**1 w1 w6 = 0

      w6 = w1

      *******************************************************


      w2 = 0
      w3 = w1
      w4 = 0
      w5 = 0
      w6 = w1


      + 2**0 w1 + 2**1 w1
      -2**0 w1
      -2**1 w1 w1 = 0

      w1 is indeterminate.

      *******************************************************




      w2 = 0
      w3 = w1
      w4 = 0
      w5 = 0
      w6 = w1
      w1 is indeterminate.

      x = 1 + 2 w1
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      If w1 = 0, then w2 = w3 = w4 = w5 = w6 = 0

      x = 1 + 0
      y = 1 + 2**3 + 2**5 + 2**6 = 105

      if w1 = 1, then w2 = 0, w3 = 1, w4 = w5 = 0, w6 = 1.

      x = 1 + 2**1 = 3
      y = 1 + 2**1 + 2**5 = 35


      *******************************************************
      $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$





      Test for divisor between 4 and 8.

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]



      1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]
      + 2 w1 + 2**2 w1 + 2**3 w1 w2 + 2**4 w1 [1 - w3] + 2**5 w1 w4
      + 2**6 w1 [1 - w5] + 2**7 w1 [1 - w6]
      2**2 w2 + 2**3 w1 w2 + 2**4 w2 + 2**5 w2 [1 - w3] + 2**6 w2 w4
      + 2**7 w2 [1 - w5] + 2**8 w2 [1 - w6]
      =105


      *******************************************************


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]



      1 + 2 w1 + 2**2 w2 + [2**3 - 2**3 w3] + 2**4 w4
      + [2**5 -2**5 w5] + [2**6 -2**6 w6]
      + 2 w1 + 2**2 w1 + 2**3 w1 w2 + w1 [2**4 -2**4 w3]
      + 2**5 w1 w4 + w1 [2**6 -2**6 w5] + w1 [2**7 -2**7 w6]
      2**2 w2 + 2**3 w1 w2 + 2**4 w2 + w2 [2**5 -2**5 w3]
      + 2**6 w2 w4 + w2 [2**7 -2**7 w5] + w2 [2**8 -2**8 w6]
      =105


      *******************************************************


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]



      + 2 w1 + 2**2 w2 + [ - 2**3 w3] + 2**4 w4
      + [ -2**5 w5] + [ -2**6 w6]
      + 2 w1 + 2**2 w1 + 2**3 w1 w2 + w1 [2**4 -2**4 w3]
      + 2**5 w1 w4 + w1 [2**6 -2**6 w5] + w1 [2**7 -2**7 w6]
      2**2 w2 + 2**3 w1 w2 + 2**4 w2 + w2 [2**5 -2**5 w3]
      + 2**6 w2 w4 + w2 [2**7 -2**7 w5] + w2 [2**8 -2**8 w6]
      =0


      *******************************************************

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]



      + 2**3 w1 + 2**4 w1 + 2**6 w1+ 2**7 w1
      + 2**3 w2 + 2**4 w2 + 2**5 w2 + 2**7 w2 + 2**8 w2
      - 2**3 w3
      + 2**4 w4
      -2**5 w5
      -2**6 w6
      + 2**4 w1 w2
      -2**4 w1 w3
      + 2**5 w1 w4
      -2**6 w1 w5
      -2**7 w1 w6
      -2**5 w2 w3
      + 2**6 w2 w4
      -2**7 w2 w5
      - 2**8 w2 w6
      =0


      *******************************************************

      Divided by 2**3

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]



      + 2**0 w1 + 2**1 w1 + 2**3 w1+ 2**4 w1
      + 2**0 w2 + 2**1 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2
      - 2**0 w3
      + 2**1 w4
      -2**2 w5
      -2**3 w6
      + 2**1 w1 w2
      -2**1 w1 w3
      + 2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6
      -2**2 w2 w3
      + 2**3 w2 w4
      -2**4 w2 w5
      - 2**5 w2 w6
      =0

      w3 = w1.xor.w2

      w3 = (w1 + w2 - 2 w1 w2)



      *******************************************************


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)

      + 2**0 w1 + 2**1 w1 + 2**3 w1+ 2**4 w1
      + 2**0 w2 + 2**1 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2
      - 2**0 (w1 + w2 - 2 w1 w2)
      + 2**1 w4
      -2**2 w5
      -2**3 w6
      + 2**1 w1 w2
      -2**1 w1 (w1 + w2 - 2 w1 w2)
      + 2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6
      -2**2 w2 (w1 + w2 - 2 w1 w2)
      + 2**3 w2 w4
      -2**4 w2 w5
      - 2**5 w2 w6
      =0





      *******************************************************


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)

      + 2**3 w1+ 2**4 w1
      + 2**1 w2 + 2**4 w2 + 2**5 w2
      + 2**1 w1 w2 +2**3 w1 w2
      + 2**1 w4
      -2**2 w5
      -2**3 w6
      + 2**2 w1 w4
      -2**3 w1 w5
      -2**4 w1 w6
      + 2**3 w2 w4
      -2**4 w2 w5
      - 2**5 w2 w6
      =0

      *******************************************************

      Divided by 2**1


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)

      + 2**2 w1+ 2**3 w1
      + 2**0 w2 + 2**3 w2 + 2**4 w2
      + 2**0 w1 w2 +2**2 w1 w2
      + 2**0 w4
      -2**1 w5
      -2**2 w6
      + 2**1 w1 w4
      -2**2 w1 w5
      -2**3 w1 w6
      + 2**2 w2 w4
      -2**3 w2 w5
      - 2**4 w2 w6
      =0

      w4 = w2 .xor. w1 w2 = w2 + w1 w2 - 2 w1 w2 = w2 - w1 w2

      w4 = (w2 (1 - w1))




      *******************************************************



      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))


      + 2**2 w1+ 2**3 w1
      + 2**0 w2 + 2**3 w2 + 2**4 w2
      + 2**0 w1 w2 +2**2 w1 w2
      + 2**0 (w2 (1 - w1))
      -2**1 w5
      -2**2 w6
      + 2**1 w1 (w2 (1 - w1))
      -2**2 w1 w5
      -2**3 w1 w6
      + 2**2 w2 (w2 (1 - w1))
      -2**3 w2 w5
      - 2**4 w2 w6
      =0


      *******************************************************




      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))


      + 2**2 w1+ 2**3 w1
      + 2**1 w2 + 2**2 w2 + 2**3 w2 + 2**4 w2
      -2**1 w5
      -2**2 w6
      -2**2 w1 w5
      -2**3 w1 w6
      -2**3 w2 w5
      - 2**4 w2 w6
      =0


      *******************************************************


      Divided by 2**1


      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))


      + 2**1 w1+ 2**2 w1
      + 2**0 w2 + 2**1 w2 + 2**2 w2 + 2**3 w2
      -2**0 w5
      -2**1 w6
      -2**1 w1 w5
      -2**2 w1 w6
      -2**2 w2 w5
      - 2**3 w2 w6
      =0

      w5 = w2


      *******************************************************



      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2


      + 2**1 w1+ 2**2 w1
      + 2**0 w2 + 2**1 w2 + 2**2 w2 + 2**3 w2
      -2**0 w2
      -2**1 w6
      -2**1 w1 w2
      -2**2 w1 w6
      -2**2 w2 w2
      - 2**3 w2 w6
      =0



      *******************************************************

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2

      + 2**1 w1+ 2**2 w1
      + 2**1 w2 + 2**3 w2
      -2**1 w6
      -2**1 w1 w2
      -2**2 w1 w6
      - 2**3 w2 w6
      =0



      *******************************************************
      Divided by 2**1

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2

      + 2**0 w1+ 2**1 w1
      + 2**0 w2 + 2**2 w2
      -2**0 w6
      -2**0 w1 w2
      -2**1 w1 w6
      - 2**2 w2 w6
      =0

      w1 .xor.w2 .xor. w6 .xor. w1 w2 = 0

      w6 = w1 .xor. w2 .xor. w1 w2

      w6 = (w1 .xor. w2) .xor. w1 w2

      w6 = (w1 + w2 - 2 w1 w2 ) .xor. w1 w2

      w6 = w1 + w2 - 2 w1 w2 + w1 w2 - 2 (w1 + w2 - 2 w1 w2 )w1 w2

      w6 = w1 + w2 - 2 w1 w2 + w1 w2 - 2 w1 w2 - 2 w1 w2 + 4 w1 w2

      w6 = w1 + w2 - w1 w2



      *******************************************************



      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2
      w6 = (w1 + w2 - w1 w2 )


      + 2**0 w1+ 2**1 w1
      + 2**0 w2 + 2**2 w2
      -2**0 (w1 + w2 - w1 w2 )
      -2**0 w1 w2
      -2**1 w1 (w1 + w2 - w1 w2 )
      - 2**2 w2 (w1 + w2 - w1 w2 )
      =0



      *******************************************************

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2
      w6 = (w1 + w2 - w1 w2 )


      0 = 0

      w1 and w2 are indeterminate


      *******************************************************

      w3 = (w1 + w2 - 2 w1 w2)
      w4 = (w2 (1 - w1))
      w5 = w2
      w6 = (w1 + w2 - w1 w2 )
      w1 and w2 are indeterminate

      x = 1 + 2 w1 + 4 w2
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w1 = 0, w2 = 0, w3 = 0, w4 = 0, w5 = 0, w6 = 0
      x = 1, y = 1 + 8 + 32 + 64 = 105

      w1 = 1, w2 = 0, w3 = 1, w4 = 0, w5 = 0, w6 = 1
      x = 3, y = 1 + 2 + 32 = 35

      w1 = 0, w2 = 1, w3 = 1, w4 = 1, w5 = 1, w6 = 1
      x = 1 + 4 = 5, y = 1 + 4 + 16 = 21

      w1 = 1, w2 = 1, w3 = 0, w4 = 0, w5 = 1, w6 = 1
      x = 1 + 2 + 4 = 7, y = 1 + 2 + 4 + 8 = 15


      *******************************************************
      $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$


      Testing if there is a divisor between 2**3 and 2**4.

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      (1 + 2 w1 + 2**2 w2 + 2**3 w3)
      (1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6])
      = 105

      1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      + 2 w1 + 2**2 w1 + 2**3 w1 w2 + 2**4 w1 [1 - w3] + 2**5 w1 w4
      + 2**6 w1 [1 - w5] + 2**7 w1 [1 - w6]

      + 2**2 w2 + 2**3 w1 w2 + 2**4 w2 + 2**5 w2 [1 - w3] + 2**6 w2 w4
      + 2**7 w2 [1 - w5] + 2**8 w2 [1 - w6]

      + 2**3 w3 + 2**4 w1 w3 + 2**5 w2 w3 + 2**6 w3 [1 - w3]
      + 2**7 w3 w4 + 2**8 w3 [1 - w5] + 2**9 w3 [1 - w6]

      = 105

      *******************************************************

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      1 + 2 w1 + 2**2 w2 + [2**3 - 2**3 w3] + 2**4 w4
      + [2**5 - 2**5 w5] + [2**6 -2**6 w6]

      + 2 w1 + 2**2 w1 + 2**3 w1 w2 + [2**4 w1 -2**4 w1 w3]
      + 2**5 w1 w4 + [2**6 w1 - 2**6 w1 w5] + [2**7 w1 - 2**7 w1 w6]

      + 2**2 w2 + 2**3 w1 w2 + 2**4 w2 + [2**5 w2 - 2**5 w2 w3]
      + 2**6 w2 w4 +[2**7 w2 - 2**7 w2 w5] + [2**8 w2 - 2**8 w2 w6]

      + 2**3 w3 + 2**4 w1 w3 + 2**5 w2 w3 + [2**6 w3 - 2**6 w3]
      + 2**7 w3 w4 + [2**8 w3 - 2**8 w3 w5] + [2**9 w3 - 2**9 w3 w6]

      = 105

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      1 + 2**3 + 2**5 + 2**6
      + 2 w1 + 2 w1 + 2**2 w1 + 2**4 w1 + 2**6 w1 + 2**7 w1
      + 2**2 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2 + 2**7 w2 + 2**8 w2
      +[ - 2**3 w3] + 2**3 w3 + 2**6 w3 - 2**6 w3 + 2**8 w3 + 2**9 w3
      + 2**4 w4
      + [ - 2**5 w5]
      + [ -2**6 w6]
      + 2**3 w1 w2 + 2**3 w1 w2
      + [ -2**4 w1 w3]
      + 2**5 w1 w4
      + [ - 2**6 w1 w5]
      + [ - 2**7 w1 w6]
      + [ - 2**5 w2 w3]
      + 2**6 w2 w4
      +[ - 2**7 w2 w5]
      + [- 2**8 w2 w6]
      + 2**4 w1 w3
      + 2**5 w2 w3
      + []
      + 2**7 w3 w4
      + [ - 2**8 w3 w5]
      + [ - 2**9 w3 w6]

      = 105

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      + 2**3 w1 + 2**4 w1 + 2**6 w1 + 2**7 w1
      + 2**3 w2 + 2**4 w2 + 2**5 w2 + 2**7 w2 + 2**8 w2
      + 2**8 w3 + 2**9 w3
      + 2**4 w4
      + [ - 2**5 w5]
      + [ -2**6 w6]
      + 2**4 w1 w2
      + [ -2**4 w1 w3] + 2**4 w1 w3
      + 2**5 w1 w4
      + [ - 2**6 w1 w5]
      + [ - 2**7 w1 w6]
      + [ - 2**5 w2 w3] + 2**5 w2 w3
      + 2**6 w2 w4
      +[ - 2**7 w2 w5]
      + [- 2**8 w2 w6]
      + 2**7 w3 w4
      + [ - 2**8 w3 w5]
      + [ - 2**9 w3 w6]

      = 0

      *******************************************************



      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      + 2**3 w1 + 2**4 w1 + 2**6 w1 + 2**7 w1
      + 2**3 w2 + 2**4 w2 + 2**5 w2 + 2**7 w2 + 2**8 w2
      + 2**8 w3 + 2**9 w3
      + 2**4 w4
      + [ - 2**5 w5]
      + [ -2**6 w6]
      + 2**4 w1 w2
      + 2**5 w1 w4
      + [ - 2**6 w1 w5]
      + [ - 2**7 w1 w6]
      + 2**6 w2 w4
      +[ - 2**7 w2 w5]
      + [- 2**8 w2 w6]
      + 2**7 w3 w4
      + [ - 2**8 w3 w5]
      + [ - 2**9 w3 w6]

      = 0

      *******************************************************
      Divided by 2**3

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      + 2**0 w1 + 2**1 w1 + 2**3 w1 + 2**4 w1
      + 2**0 w2 + 2**1 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2
      + 2**5 w3 + 2**6 w3
      + 2**1 w4
      + [ - 2**2 w5]
      + [ -2**3 w6]
      + 2**1 w1 w2
      + 2**2 w1 w4
      + [ - 2**3 w1 w5]
      + [ - 2**4 w1 w6]
      + 2**3 w2 w4
      +[ - 2**4 w2 w5]
      + [- 2**5 w2 w6]
      + 2**4 w3 w4
      + [ - 2**5 w3 w5]
      + [ - 2**6 w3 w6]

      = 0

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]


      + 2**0 w1
      + 2**0 w2
      + 2**1 w1 + 2**3 w1 + 2**4 w1
      + 2**1 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2
      + 2**5 w3 + 2**6 w3
      + 2**1 w4
      + [ - 2**2 w5]
      + [ -2**3 w6]
      + 2**1 w1 w2
      + 2**2 w1 w4
      + [ - 2**3 w1 w5]
      + [ - 2**4 w1 w6]
      + 2**3 w2 w4
      +[ - 2**4 w2 w5]
      + [- 2**5 w2 w6]
      + 2**4 w3 w4
      + [ - 2**5 w3 w5]
      + [ - 2**6 w3 w6]

      = 0

      w2 = w1


      *******************************************************



      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1

      + 2**0 w1
      + 2**0 w2
      + 2**1 w1 + 2**3 w1 + 2**4 w1
      + 2**1 w2 + 2**2 w2 + 2**4 w2 + 2**5 w2
      + 2**5 w3 + 2**6 w3
      + 2**1 w4
      + [ - 2**2 w5]
      + [ -2**3 w6]
      + 2**1 w1 w2
      + 2**2 w1 w4
      + [ - 2**3 w1 w5]
      + [ - 2**4 w1 w6]
      + 2**3 w2 w4
      +[ - 2**4 w2 w5]
      + [- 2**5 w2 w6]
      + 2**4 w3 w4
      + [ - 2**5 w3 w5]
      + [ - 2**6 w3 w6]

      = 0



      *******************************************************




      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1

      + 2**0 w1
      + 2**0 w1
      + 2**1 w1 + 2**3 w1 + 2**4 w1
      + 2**1 w1 + 2**2 w1 + 2**4 w1 + 2**5 w1
      + 2**5 w3 + 2**6 w3
      + 2**1 w4
      + [ - 2**2 w5]
      + [ -2**3 w6]
      + 2**1 w1 w1
      + 2**2 w1 w4
      + [ - 2**3 w1 w5]
      + [ - 2**4 w1 w6]
      + 2**3 w1 w4
      +[ - 2**4 w1 w5]
      + [- 2**5 w1 w6]
      + 2**4 w3 w4
      + [ - 2**5 w3 w5]
      + [ - 2**6 w3 w6]

      = 0



      *******************************************************

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1

      + 2**0 w1 + 2**0 w1 + 2**1 w1 + 2**3 w1 + 2**4 w1 + 2**1 w1
      + 2**2 w1 + 2**4 w1 + 2**5 w1 + 2**1 w1
      + 2**5 w3 + 2**6 w3
      + 2**1 w4
      + [ - 2**2 w5]
      + [ -2**3 w6]
      + 2**2 w1 w4 + 2**3 w1 w4
      + [ - 2**3 w1 w5] +[ - 2**4 w1 w5]
      + [ - 2**4 w1 w6]+ [- 2**5 w1 w6]
      + 2**4 w3 w4
      + [ - 2**5 w3 w5]
      + [ - 2**6 w3 w6]

      = 0



      *******************************************************
      Divided by 2**1

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1

      + 2**1 w1 + 2**3 w1 + 2**5 w1
      + 2**4 w3 + 2**5 w3
      + 2**0 w4
      + [ - 2**1 w5]
      + [ -2**2 w6]
      + 2**1 w1 w4 + 2**2 w1 w4
      + [ - 2**2 w1 w5] +[ - 2**3 w1 w5]
      + [ - 2**3 w1 w6]+ [- 2**4 w1 w6]
      + 2**3 w3 w4
      + [ - 2**4 w3 w5]
      + [ - 2**5 w3 w6]

      = 0

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1

      + 2**0 w4

      + 2**1 w1 + 2**3 w1 + 2**5 w1
      + 2**4 w3 + 2**5 w3

      + [ - 2**1 w5]
      + [ -2**2 w6]
      + 2**1 w1 w4 + 2**2 w1 w4
      + [ - 2**2 w1 w5] +[ - 2**3 w1 w5]
      + [ - 2**3 w1 w6]+ [- 2**4 w1 w6]
      + 2**3 w3 w4
      + [ - 2**4 w3 w5]
      + [ - 2**5 w3 w6]

      = 0

      w4 = 0


      *******************************************************



      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0

      + 2**1 w1 + 2**3 w1 + 2**5 w1
      + 2**4 w3 + 2**5 w3
      + [ - 2**1 w5]
      + [ -2**2 w6]
      + [ - 2**2 w1 w5] +[ - 2**3 w1 w5]
      + [ - 2**3 w1 w6]+ [- 2**4 w1 w6]
      + [ - 2**4 w3 w5]
      + [ - 2**5 w3 w6]

      = 0

      *******************************************************
      Divided by 2**1

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0

      + 2**0 w1 + 2**2 w1 + 2**4 w1
      + 2**3 w3 + 2**4 w3
      + [ - 2**0 w5]
      + [ -2**1 w6]
      + [ - 2**1 w1 w5] +[ - 2**2 w1 w5]
      + [ - 2**2 w1 w6]+ [- 2**3 w1 w6]
      + [ - 2**3 w3 w5]
      + [ - 2**4 w3 w6]

      = 0

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0

      + 2**0 w1
      + [ - 2**0 w5]

      + 2**2 w1 + 2**4 w1
      + 2**3 w3 + 2**4 w3
      + [ -2**1 w6]
      + [ - 2**1 w1 w5] +[ - 2**2 w1 w5]
      + [ - 2**2 w1 w6]+ [- 2**3 w1 w6]
      + [ - 2**3 w3 w5]
      + [ - 2**4 w3 w6]

      = 0

      w5 = w1

      *******************************************************



      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1

      + 2**0 w1
      + [ - 2**0 w1]

      + 2**2 w1 + 2**4 w1
      + 2**3 w3 + 2**4 w3
      + [ -2**1 w6]
      + [ - 2**1 w1 w1] +[ - 2**2 w1 w1]
      + [ - 2**2 w1 w6]+ [- 2**3 w1 w6]
      + [ - 2**3 w3 w1]
      + [ - 2**4 w3 w6]

      = 0


      *******************************************************




      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1


      + [ - 2**1 w1 ]+ 2**2 w1 +[ - 2**2 w1 ] + 2**4 w1
      + 2**3 w3 + 2**4 w3
      + [ -2**1 w6]

      + [ - 2**2 w1 w6]+ [- 2**3 w1 w6]
      + [ - 2**3 w1 w3 ]
      + [ - 2**4 w3 w6]

      = 0


      *******************************************************

      Divided by 2**1

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1


      + [ - 2**0 w1 ]+ 2**1 w1 +[ - 2**1 w1 ] + 2**3 w1
      + 2**2 w3 + 2**3 w3
      + [ -2**0 w6]

      + [ - 2**1 w1 w6]+ [- 2**2 w1 w6]
      + [ - 2**2 w1 w3 ]
      + [ - 2**3 w3 w6]

      = 0


      *******************************************************



      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1


      + [ - 2**0 w1 ]
      + [ -2**0 w6]

      + 2**1 w1 +[ - 2**1 w1 ] + 2**3 w1
      + 2**2 w3 + 2**3 w3


      + [ - 2**1 w1 w6]+ [- 2**2 w1 w6]
      + [ - 2**2 w1 w3 ]
      + [ - 2**3 w3 w6]

      = 0

      w6 = w1


      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1
      w6 = w1


      + [ - 2**0 w1 ]
      + [ -2**0 w1]

      + 2**1 w1 +[ - 2**1 w1 ] + 2**3 w1
      + 2**2 w3 + 2**3 w3


      + [ - 2**1 w1 w1]+ [- 2**2 w1 w1]
      + [ - 2**2 w1 w3 ]
      + [ - 2**3 w3 w1]

      = 0

      *******************************************************

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1
      w6 = w1


      + 2**2 w3 + 2**3 w3

      + [ - 2**2 w1 w3 ] + [ - 2**3 w1 w3]

      = 0

      *******************************************************
      Divided by 2**2

      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1
      w6 = w1


      + 2**0 w3 + 2**1 w3

      + [ - 2**0 w1 w3 ] + [ - 2**1 w1 w3]

      = 0

      *******************************************************


      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w4 = 0
      w5 = w1
      w6 = w1


      + 2**0 w3 + [ - 2**0 w1 w3 ]

      + 2**1 w3 + [ - 2**1 w1 w3]

      = 0

      w3 (1-w1) = 0



      *******************************************************




      x = 1 + 2 w1 + 2**2 w2 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w2 + 2**3 [1 - w3] + 2**4 w4
      + 2**5 [1 - w5] + 2**6 [1 - w6]

      w2 = w1
      w3 (1-w1) = 0
      w4 = 0
      w5 = w1
      w6 = w1

      x = 1 + 2 w1 + 2**2 w1 + 2**3 w3
      y = 1 + 2 w1 + 2**2 w1 + 2**3 [1 - w3] + 2**5 [1 - w1]
      + 2**6 [1 - w1]

      If w1 = 0, w3 = 0.
      If w1 = 1, w3 is indeterminate.

      Three values of xy pairs.

      w1 = 0, w3 = 0, x = 1, y = 1 + 2**3 + 2**5 + 2**6 = 105
      w1 = 1, w3 = 0, x = 1 + 2 + 2**2 = 7, y = 1 + 2 + 4 + 8 = 15
      w1 = 1, w3 = 1, x = 1 + 2 + 4 + 8 = 15, y = 1 + 2 + 4 = 7


      *******************************************************
      $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
    • Mark Underwood
      ... Good luck Kermit. At least, the proof will be in the pudding. I hope you are rewarded for your work. I found out about python when I was exploring ways to
      Message 2 of 4 , Jan 6, 2009
        --- In primenumbers@yahoogroups.com, Kermit Rose <kermit@...> wrote:
        >
        >
        > I am working on programming this algorithm in python.
        >
        > I expect to be able to prove that this algorithm works and is a
        >
        > polynomial time algorithm by factoring
        > the RSA challenge large integers.
        >
        > Detailed illustration of polynomial time factoring algorithm
        >
        > Factoring z = 105 = 3 * 5 * 7 by polynomial time factoring
        >
        > algorithm.
        >

        Good luck Kermit. At least, the proof will be in the pudding. I hope
        you are rewarded for your work.

        I found out about python when I was exploring ways to get gp pari
        working on my mac. It turns out there is a free new program called
        'sage' which is primarily based on python, and it gathers several
        math programs out there under its umbrella, including gp pari.

        Mark
      • Alex Petty
        it appears that the RSA challenge is no longer open. is this true? -alex ... -- alex petty alexander.petty@gmail.com skype: alex.petty skypein:
        Message 3 of 4 , Jan 6, 2009
          it appears that the RSA challenge is no longer open. is this true?

          -alex


          Mark Underwood wrote:
          >
          > --- In primenumbers@yahoogroups.com
          > <mailto:primenumbers%40yahoogroups.com>, Kermit Rose <kermit@...> wrote:
          > >
          > >
          > > I am working on programming this algorithm in python.
          > >
          > > I expect to be able to prove that this algorithm works and is a
          > >
          > > polynomial time algorithm by factoring
          > > the RSA challenge large integers.
          > >
          > > Detailed illustration of polynomial time factoring algorithm
          > >
          > > Factoring z = 105 = 3 * 5 * 7 by polynomial time factoring
          > >
          > > algorithm.
          > >
          >
          > Good luck Kermit. At least, the proof will be in the pudding. I hope
          > you are rewarded for your work.
          >
          > I found out about python when I was exploring ways to get gp pari
          > working on my mac. It turns out there is a free new program called
          > 'sage' which is primarily based on python, and it gathers several
          > math programs out there under its umbrella, including gp pari.
          >
          > Mark
          >
          >
          >


          --
          alex petty
          alexander.petty@...
          skype: alex.petty
          skypein: +001.540.322.3922
          mobile: +001.540.272.7970



          [Non-text portions of this message have been removed]
        • Phil Carmody
          ... Given that that s a stand-alone question, why did you not trim the couple of dozens of lines of cruft that followed it and was no longer required for
          Message 4 of 4 , Jan 6, 2009
            --- On Tue, 1/6/09, Alex Petty <alexander.petty@...> wrote:
            > it appears that the RSA challenge is no longer open. is this
            > true?

            Given that that's a stand-alone question, why did you not trim the couple of dozens of lines of cruft that followed it and was no longer required for context?

            Anyway, to answer your question, yup, the beancounters finally pushed the final academic out of RSA, and decided that such challenges didn't look good on the balance sheet.

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