Friday, February 20, 2009


JSH: Critiquing factoring solution proof

I will say I've been surprised by a willingness of posters to use the same tactics against my solution to the factoring problem as they've used against my other research. You might say that before I didn't think they'd have the nerve!

But with posters already talking victory as if they had shot down a remarkably simple proof I thought it worth it to step out a critique of the actual proof, and then you can ponder how posters were so confident they could block knowledge of such a thing.

Ok. Field is rationals. First thing is I use Pell's Equation:

x^2 - Dy^2 = 1

but I SOLVE Pell's Equation, giving x and y explicitly as functions of a variable I call v, and factors of D-1:

y = [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)


x = +/-(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v) - [+/-2Dv/(f_1 - f_2*v^2 - 2v) +/- 1 -/+(f_1 + f_2*v^2)/(f_1 - f_2*v^2 - 2v)]/(D-1)

where f_1*f_2 = D-1, and the f's are non-zero integer factors, while v is a free variable.

Note there is no argument about the correctness of those equations. If you plug in some rational v, then you will get x and y such that x^2 - Dy^2 = 1. That's a mathematical absolute, so don't worry about if they are right or not (or go check and you'll see they are).

And remarkably while there is a factoring dependency—familiar to anyone who may have tried to solve for x and y directly who probably faced factoring D—it is for D-1, which is a good thing!!! If it were D, then that would be it. This approach could not be a solution to the factoring problem.

So that is a HUGE thing which allows everything that follows which is why I belabor it: yes there is a factoring dependency but it is on D-1, not D.

But integer factorization is about integers!!! Not rationals, so I move in the direction of integers with a simple step,

by considering x and y as ratios of integer functions r, s, and t:

x = r(v)/t(v), y = s(v)/t(v)


(r(v) - t(v))*(r(v) + t(v)) = D*(s(v))^2

and that is not a big step though it might seem controversial to some. Quite simply I only care about integer values for r, s and t, as I'm trying to factor D, and integers would be nice!!!

Now the proof is almost done!!! It is remarkably short considering it is a proof of a solution to the factoring problem.

The penultimate step is to realize simple conditions on r(v) and t(v) such that you MUST factor D non-trivially if it is a composite.

That is important. We're now worrying about what mathematical conditions can be satisfied which will give us the desired non-trivial factorization, which is a very big step. But it turns out it is easy as well!

Well, if abs(r(v) - t(v)) < D and abs(r(v) + t(v)) < D, then of course neither can have D itself as a factor!

And for some of you there should be this excited rush of amazement and awe that it can be that simple!!!

ALL we have to do is determine r(v) and t(v) such that the they are below a minimum value.

And, um, from where I'm from, that's calculus!

Somehow, someway the much vaunted factoring problem has just turned into a calculus problem.

But I said the penultimate step. So what is the final one?

Existence of course!!!

We need to know that rational v exists such that the conditions above can be met, and I can start you on the answer.

Let D = g_1*g_2 where the g's are integer factors and D is an odd composite, and now let

r - t = g_1 and r + t = g_2

where I leave off v because this time we're going BACKWARDS and are going to find v, so now v is the dependent variable, as I'm setting the functions.

So r = (g_1 + g_2)/2 and t = (g_1 - g_2)/2, and then s = 1.

That means I have x and y, and it turns out I can now go off and find v by a rather straightforward method, proving it exists, which completes the proof.

I've leave that out for the moment and see what happens in reply to this post.

<< Home

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