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

Restatement of theorem which will enable polynomial time factoring

Expand Messages
  • Kermit Rose
    Factor Theorem Let z be an odd positive integer. Let 2**n be the largest power of 2
    Message 1 of 1 , Jan 3, 2009
    • 0 Attachment
      Factor Theorem

      Let z be an odd positive integer.

      Let 2**n be the largest power of 2 < z.

      Let 1 + 2 d1 + 2**2 d2 + 2**3 d3 + . . . + 2**n d_n
      be the base 2 representation of z.

      Note: Each of d1, d2, . . . d_n are equal to zero or one.

      Let 2**m be the largest power of 2 < sqrt(z).

      Let x be a divisor of z.

      If x is of the form

      1 + 2 w1 + 2**2 w2 + 2**3 w3 + . . . + 2**m w_m

      where each of w1, w2, . . ., w_m are zero or one.

      Then y = z/x

      is of the form

      1 + 2 [ d1 + (1 - 2 d1) w1 ]
      + 2**2 [ d2 + (1 - 2 d2) w2]
      + 2**3 [ d3 + (1 - 2 d3) w3 ]
      + . . .

      + 2**n [ d_n + (1 - 2 d_n)w_n ]


      Examples:

      z = 9
      n = 3; m = 1; d1 = 0; d2 = 0; d3 = 1; x = 3; w1 = 1

      y = 9/3
      = 1 + 2 [0 + (1 - 2 * 0) * 1 ]
      + 4 [ 0 + (1 - 2 * 0) w2 ]
      + 8 [ 1 + (1 - 2 * 1) w3 ]

      with w2 = 0 and w3 = 1, this yields y = 3.

      z = 15
      n = 3; m = 1; d1 = 1; d2 = 1; d3 = 1; x = 3; w1 = 1

      y = 15/3
      = 1 + 2 [1 + (1 - 2 * 1)* 1 ]
      + 4 [ 1 + (1 - 2 * 1) w2]
      + 8 [ 1 + (1 - 2 * 1) w3]

      With w2 = 0 and w3 = 1 this yields y = 5


      z = 21
      n = 4; m = 2; d1 = 0; d2 = 1; d3 = 0; d4 = 1

      x = 3; w1 = 1

      y = 21/3 = 7

      y = 1 + 2 [ 0 + (1 - 2 * 0) * 1 ]
      + 4 * [ 1 + (1 - 2 * 1) w2 ]
      + 8 * [ 0 + (1 - 2 * 0) w3 ]
      + 16 * [ 1 + (1 - 2 * 1) w4 ]

      With w2 = 0, w3 = 0, w4 = 1, this yields y = 7.


      z = 25

      n = 4; m = 2; d1 = 0; d2 = 0; d3 = 1; d4 = 1

      x = 5; w1 = 0; w2 = 1

      y = 25/5 = 5

      y = 1 + 2 [ 0 + (1 - 2 * 0)* 0 ]
      + 4 * [ 0 + ( 1 - 2 * 0) * 1 ]
      + 8 * [ 1 + (1 - 2 * 1) w3 ]
      + 16 * [ 1 + (1 - 2 * 1) w4]

      with w3 = 1; w4 = 1 , this yields y = 5.
    Your message has been successfully submitted and would be delivered to recipients shortly.