Sunday, February 13, 2005

 

I was right, surrogate factoring proof

Last weekend I came across a simpler way to describe surrogate factoring with a couple of quadratics and solutions for x and z, which I promptly programmed—and it didn't seem to work.

I puzzled over that a bit, and posted the equations:

yx^2 + Ax - M^2 = 0

and

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)

and

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

and you should be able to always factor M, by iterating through factors of Tj^2 to get the full set of of integer solutions for Ax.

But, as I said, I tried the idea last weekend, and I didn't see it work, and also a poster named Rick Decker claimed to have a counter-example.

However, I was missing something easy, as consider A (yes, I've screwed this up before but here's the correct argument) as it's chosen arbitrarily.

Now then, for any rational x and z, there must exist some A, such that

Ax and Az

are integers, right? Like if x = 29343/3947387492 then

A = 3947387492, will force Ax to be an integer, equal to 29343.

Well, look at

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

and

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

and notice then that an A can always be chosen such that Ax and Az are integers.

So what, right?

Well, multiply both equations by A, and you get

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

and

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

so that now you have integers inside and out!!!

And looking at

sqrt((Az - 2M^2)^2 - 4TM^2)

it MUST be true that for some integer Az, M is factored.

In retrospect, with my tests last weekend, I, um, assumed that A=1, as I just figured it didn't matter, and that's probably why they didn't work, I guess, or also I might not have done plus and minus.

That is, the square roots give a positive and a negative solution, and I don't remember if I checked both.

In any event, the proof that the method has to work is easy. There must exist integers Ax and Az, as shown above.

[A reply to someone who askd James to inform the newsgroup when it turns out that his method won't work.]

Huh? Do you believe in algebra, or not?

Given

yx^2 + Ax - M^2 = 0

yz^2 + Az - j^2 = 0

and

T = M^2 - j^2

you must also have

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

and

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

and, you can multiply both equations by A, to get


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

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

where for any rational x and z there must be an integer A such that both Ax and Az are integers, so looping through all possible integer Ax and Ay as required by the square roots MUST factor M.

So, I can't be wrong, or, algebra is wrong.

Now that's a trivially easy proof. And I want to emphasize that it is a proof as I've seen weird stuff from sci.math'ers where proofs are just discounted, as if they don't matter.

But they do. A mathematical proof gives absolute certainty.

Surrogate factoring must work. There is no room for doubt.

[A reply to someone who said to have missed the proof that the method works in polynomial time.]

Sounds like you missed algebra in school.

It's a trivially easy proof. End of story.

If you wish to betray that you're either not bothering to read it, or can't comprehend VERY basic algebra, then ok.

Reply again, and so betray.

[A reply to someone who asekd James to state the therem that he think he proved.]

And there you have it.

I've seen this mindless behavior go on for hundreds of posts.

Yup, hundreds of posts, where the fact that an actual proof has been given and shown is lost in the shuffle.

What motivates these people?

I think their behavior is instinctive.

Easily this thread could in a few hours be over a hundred posts long, despite my having given a very basic argument, using very basic algebra, at the level that teenagers learn.

Oh, and note that the posters so far in this thread are obsessive repliers.

The "Last Danish Pastry" is notable for starting a flame webpage against me some years back. Yes, years back.

"Jose Carlos Santos" is a current regular flamer.

The other two are as well.

And they will reply, reply, reply.

Notice that reasoning doesn't work with them.





<< Home

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