Wednesday, February 09, 2005


Factoring problem solution

I've been working to figure out the particulars of my approach to surrogate factoring focusing on getting solutions for y, and then using those to get solutions for x, as it's a little complicated.

It turns out there's an easier way, where you focus on x at the start, and actually solve out y, and at a key point you do an inversion to get the full solution set, solving the problem.

Notice the mathematics is very easy. The factoring problem had never been proven to be difficult, but had been supposed to be difficult because no one knew of an easy answer!

Well, here it is.

Take the two quadratics

yx^2 + Ax - M^2 = 0


yz^2 + Az - j^2 = 0

where A, j, and M are integers greater than 0 chosen, where M is the target to be factored, and you find that you can use T, where

T = M^2 - j^2

and substituting out y to solve for x and z gives

x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)


z = x(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)

where you have the problem that x may be a fraction, and its denominator is what's important to determine.

So, invert it. Let x = 1/Aw, then

z = 1(-1/w +/- sqrt((1/w - 2j^2)^2 + 4Tj^2))/(2wM^2 - 2)

and focusing on the square root I have

sqrt((1 - 2wj^2)^2 + 4Tw^2 j^2))/w^2

and focusing on the square root again, multiplying it out, gives

sqrt(1 - 4 j^2 w + 4j^4 w^2 + 4Tj^2 w^2)

and collecting with respect to w, gives

sqrt(4(j^4 + Tj^2)w^2 - 4A^2 j^2 w + 1)

which is

sqrt(4j^2 (j^2 + T)w^2 - 4 j^2 w + 1)

and since M^2 = j^2 + T, that is

sqrt(4j^2 M^2 w^2 - 4j^2 w + 1)

and completing the square inside, gives

sqrt(4j^2 M^2 w^2 - 4j^2 w + j^2/M^2 + 1 - j^2 /M^2)

which is

sqrt((2j M w - j/M)^2 + (M^2 - j^2)/M^2)

which is

sqrt(j(2M^2 w - 1)^2 + T)/M^2

and focusing on the square root again, you have

sqrt(j(2M^2 w - 1)^2 + T)

showing that the factorization is dependent on T.

The inversion is what's necessary to finish out.

Since x = 1/Aw, if x is a fraction like

x = x_num/x_denum, where x_num and x_denum are integers, then

w = x_denum/A x_num

so you can easily recover x from the solution to w, and you can let A have different values but it's easier to just let A=1, as you don't gain anything using other values.

That means the solution is almost trivially easy, and not hard to implement.

The belief that factoring was a hard problem had nothing to do with mathematical reality, but simply human wants and needs.

<< Home

This page is powered by Blogger. Isn't yours?