Monday, June 05, 2006


SF: Does this work?

Whether this slight change works or not, it is a curious bit of mathematics, as to how the algebra handles a less simple relationship between factors of T, and y, than there is with z.

Of course it's also desperation, but who knows? ___JSH

Solving the Factoring Problem

Consider a relation between two integer factorizations:

f_1 f_2 = k + g_1 g_2

and a solution with four unknowns w, x, y and z, as they are determined by four linear equations:

L_1(w,x,y,z) = f_1
L_2(w,x,y,z) = f_2
L_3(w,x,y,z) = g_1
L_4(w,x,y,z) = g_2

What I have found is that remarkably you can use only two linear equations and k itself to find g_1 and g_2, through a process I call surrogate factorization.

More specifically I use the system of equations

(w + x - 2z)(w + 3x + 2y + 2z) = k + (w + x + y + z)(3w + x - y - 3z)


k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

as then I can use

w + x - 2z = f_1

w + 3x + 2y + 2z = f_2

to find

x = (f_2 - f_1 - 2y - 4z)/2, w = (3f_1 - f_2 + 2y + 8z)/2

and with

f_1 f_2 = T+k

where T = (w + x + y + z)(3w + x - y - 3z)

I can substitute for w and x, into

k = 2x^2 + 2xy + y^2 - 2w^2 - z^2 - 2xz

and complete the square twice, isolating y on the right.

I had a previous approach where I isolated z on the right, but that failed.

You can see why it failed by fully solving for z using all four linear equations as then you get

z = (g_2 - g_1 + f_2 - 3f_1)/4

and, of course, g_2 - g_1 is just a difference of factor of T, so the solution to completing the square twice isolating z on the right side must use the factorization of T itself.

But y is different, giving a more complex solution, instead of a simple difference of squares.

Maybe it's still useless, but it may be that I just took a wrong turn, as that happens in real problem solving, when you are so close, but can make one last zig when you should zag, but back up, try again, and it make all the difference.

With that said, having screwed up the algebra multiple times, I'll leave the calculation to those of you with math software, which should be able to do it quickly.

Is it still trivial if you focus on y versus z?

Is there still hope for surrogate factoring?

Oh, if that does work, then you can use

g_1 = w + x + y + z

g_2 = 3w + x - y - 3z

to get rational factors of the target T.

But I will admit, I'm figuring there is still some way the algebra will stuff T in there so you end up needing to factor it, but how exactly does it do it?

<< Home

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