## Toward a Polynomial Time Factoring Algorithm.

Expand Messages
• 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 5:25 PM
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,