## 25462Factoring by analysis of parity

Expand Messages
• Jan 26, 2014
• 0 Attachment

Hello everyone.

I have constructed a factor algorithm that uses only the information in the base 2 representation of the number to be factored.  However, it is, in speed of factoring, roughly equivalent to trial division.

I illustrate the algorithm here by its factoring of 11*31 =341, in hope that your study of it will give insight into the reasons why polynomial time factoring is not possible.

G = x

H = y

G and H will keep track of factors.  At each step, G * H = 341.

x y = 341

Note that both x and y are odd.

replace x with (2x+1) and y with (2y+1).

G = 2x+1

H = 2y+1

(2x+1)(2y+1) = 341

4 x y + 2 x + 2 y + 1 = 341

4 x y + 2 x + 2 y = 340

2 x y + x + y = 170

Note that x+y is even.

x and y are same parity.

replace x with (y-x) and y with (y+x).

G = 2(y-x)+1 = 2y – 2x +1

H = 2(y+x)+1 = 2y + 2x +1

2 (y-x)(y+x) + (y-x)(y+x) = 170

2y^2 – 2x^2 + 2y = 170

y^2 – x^2 + y = 85

Note that x is odd.

Replace x by (2x+1)

G = 2 y – 2 (2x+1) + 1 = 2y – 4x -1

H = 2y + 2(2x+1) + 1 = 2y + 4x + 3

y^2 – (2x+1)^2 + y = 85

y^2 – 4x^2 – 4x – 1 + y = 85

y^2 – 4x^2 – 4x + y = 86

At this point we much branch because there is not enough information to determine the parity of x and y.

Branch 1.0 is

From

y^2 – 4x^2 – 4x + y = 86 ;G = 2y – 4x -1 ; H = 2y + 4x + 3

Make x and y same parity.

replace x with (y-x) and y with (y+x).

G = 2(y+x) – 4 (y-x) -1 = -2y + 6x -1

H = 2(y+x) + 4(y-x) + 3 = 6 y -2x + 3

(y+x)^2 – 4(y-x)^2 – 4(y-x) + (y+x) = 86

-3y^2 + 10 x y – 3 x^2 -3 y + 5 x = 86

Branch 2.0 is

From

y^2 – 4x^2 – 4x + y = 86 ;G = 2y – 4x -1 ; H = 2y + 4x + 3

Make x and y opposite parity.

replace x with (y-x) and y with (y+x+1).

G = 2(y+x+1)-4(y-x)-1 = -2y+6x+1

H = 2(y+x+1)+4(y-x)+3 = 6y -2x +5

(y+x+1)^2 – 4(y-x)^2 -4(y-x) + (y+x+1) = 86

-3y^2 + 10xy -3x^2 –y +7x = 84

From Branch 1.0;

-3y^2 + 10 x y – 3 x^2 -3 y + 5 x = 86

G = 2(y+x) – 4 (y-x) -1 = -2y + 6x -1

H = 2(y+x) + 4(y-x) + 3 = 6 y -2x + 3

make two branches.

Branch 1.1.0 is

Make x and y same parity.

Replace x with (y-x) and y with (y+x).

G = -2(y+x) + 6(y-x) -1 = 4 y – 8x -1

H = 6(y+x) – 2(y-x) +3 = 4 y + 8x + 3

-3 (y+x)^2 + 10 (y-x) (y+x) – 3 (y-x)^2 – 3(y+x) + 5 (y-x) = 86

4 y^2 -16 x^2 + 2y – 8x = 86

2 y^2 – 8x^2 + y – 4x = 43

From Branch 1.0;

-3y^2 + 10 x y – 3 x^2 -3 y + 5 x = 86

G = -2y + 6x -1

H = 6 y -2x + 3

Branch 1.2.0 is

Make x and y different parity.

Replace x with (y-x) and y with (y+x+1).

G = -2(y+x+1) + 6(y-x) -1 = 4y -8x -3

H = 6(y+x+1) – 2 (y-x) + 3 = 4 y + 8x + 9

-3(y+x+1)^2 + 10 (y-x) (y+x+1) – 3 (y-x)^2 – 3 (y+x+1) + 5 (y-x) = 86

4 y^2 -16 x^2 + 6 y – 24 x = 92

2 y^2 – 8 x^2 + 3 y – 12 x = 46

Branch 1.2.0 has become

2 y^2 – 8 x^2 + 3 y – 12 x = 46

G = 4y -8x -3

H = 4 y + 8x + 9

From Branch 2.0,

-3y^2 + 10xy -3x^2 –y +7x = 84

G = -2y+6x+1

H = 6y -2x +5

Branch 2.1.0 is

Make x and y same parity.

Replace x by (y-x) and y by (y+x).

G = -2(y+x) + 6 (y-x) + 1 = 4 y – 8x + 1

H = 6 (y+x) – 2 (y-x) + 5 = 4 y + 10 x + 5

-3(y+x)^2 + 10 (y-x)(y+x) – 3 (y-x)^2 – (y+x) + 7 (y-x) = 84

4 y^2 – 16 x^2 + 6 y – 8x = 84

2 y^2 – 8 x^2 + 3 y – 4 x = 42

From Branch 2.0,

-3y^2 + 10xy -3x^2 –y +7x = 84

G = -2y+6x+1

H = 6y -2x +5

Branch 2.2.0 is

Make x and y opposite parity.

Replace x by (y-x) and y by (y+x+1).

G = -2(y+x+1) + 6 (y-x) + 1 = 4 y – 8x -1

H = 6 (y+x+1) – 2(y-x) + 5 = 4 y + 8x + 11

-3(y+x+1)^2 + 10 (y-x)(y+x+1) – 3 (y-x)^2 – (y+x+1) + 7 (y-x) = 84

4 y^2 – 16 x^2 + 10 y -24 x = 88

2 y^2 – 8 x^2 + 5 y – 12 x = 44

From Branch 1.1.0

2 y^2 – 8x^2 + y – 4x = 43

G = 4 y – 8x -1

H = 4 y + 8x + 3

Note that y must be odd.

Replace y with (2y+1)

G = 4(2y+1) – 8 x – 1 = 8 y – 8x + 3

H = 4(2y+1) + 8x + 3 = 8 y + 8x + 7

2 (2y+1)^2 – 8 x^2 + (2y+1) – 4x = 43

4 y^2 – 8 x^2 + 6y – 4x = 40

2 y^2 – 4 x^2 + 3 y – 2x = 20

Branch  1.1.0 has become

2 y^2 – 4 x^2 + 3 y – 2x = 20

G = 8 y – 8x + 3

H = 8 y + 8x + 7

From Branch 1.2.0

2 y^2 – 8 x^2 + 3 y – 12 x = 46

G = 4y -8x -3

H = 4 y + 8x + 9

Note that y must be even.

Replace y with (2y)

G = 8 y – 8x – 3

H = 8 y + 8x + 9

2 (2y)^2 – 8x^2 + 3(2y) – 12 x = 46

8 y^2 – 8x^2 + 6 y – 12 x = 46

4 y^2 – 4 x^2 + 3 y – 6 x = 23

Branch 1.2.0 has become

4 y^2 – 4 x^2 + 3 y – 6 x = 23

G = 8 y – 8x – 3

H = 8 y + 8x + 9

From Branch 2.1.0,

2 y^2 – 8 x^2 + 3 y – 4 x = 42

G = 4 y – 8x + 1

H = 4 y + 10 x + 5

Note that y must be even.

Replace y by (2y).

G = 4(2y) – 8x + 1 = 8y – 8x + 1

H = 4(2y) + 10x + 5 = 8y + 10x + 5

2 (2y)^2 – 8x^2 + 3 (2y) – 4x = 42

8y^2 – 8x^2 + 6y – 4x = 42

4y^2 – 4x^2 + 3y – 2x = 21

Branch 2.1.0 has become

4y^2 – 4x^2 + 3y – 2x = 21

G = 8y – 8x + 1

H = 8y + 10x + 5

From Branch 2.2.0,

2 y^2 – 8 x^2 + 5 y – 12 x = 44

G = 4 y – 8x -1

H = 4 y + 8x + 11

Note that y must be even.

Replace y with (2y).

G = 4 (2y) – 8x – 1 = 8y – 8x – 1

H = 4 (2y) + 8x + 11= 8y + 8x + 11

2 (2y)^2 – 8x^2 + 5 (2y) – 12x = 44

8y^2 – 8x^2 + 10 y – 12x = 44

4 y^2 – 4x^2 + 5 y – 6x = 22

Branch 2.2.0 has become

4 y^2 – 4x^2 + 5 y – 6x = 22

G = 8y – 8x – 1

H = 8y + 8x + 11

From Branch  1.1.0

2 y^2 – 4 x^2 + 3 y – 2x = 20

G = 8 y – 8x + 3

H = 8 y + 8x + 7

Note that y must be even.

Replace y with (2y)

G = 8 (2y) – 8x + 3 = 16 y – 8x + 3

H = 8 (2y) + 8x + 7 = 16 y + 8x + 7

At this point we have found the solution because

at x=1, y=1,

G = 16 – 8 + 3 = 11

H = 16 + 8 + 7 = 31

have the property that

G * H = 341.