## Detailed illustration of polynomial time factoring algorithm

Expand Messages
• 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

*******************************************************
\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$\$
• ... 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
• 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:
>
> <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]
• ... 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.