Friday, March 13, 2009


Factoring problem solved, remaining issues resolved

For weeks I've been talking about having a proof that solves the factoring problem by using Pell's Equation and posters have argued with me. Well it turns out they were arguing over details of implementation, and ignoring the proof.

I've carefully figured out the answer to the implementation detail which they criticized:

r(v) = [(D+1)*v^2 - 2f_1*v + f_1^2]/2^k


t(v) = [f_1*(f_1 - f_2*v^2 - 2v)]/2^k

where D is the target composite to be factored, f_1 and f_2 are integer factors of D-1, where f_1*f_2 = D-1, and k is a natural number, so it cannot be non-zero, which is the critical element that was missing, which is necessary for implementation of the proof.

The proof notes that with r(v) and t(v) coprime to each other, and abs(r(v))<D, if you have integer r(v) for a rational v, then r(v) + t(v) or r(v) - t(v) MUST factor D non-trivially, and in fact, if D is prime, those conditions cannot be met, but the proof shows that if it is not, they can ALWAYS be met. Which is why the proof solves the factoring problem.

Now others may disagree saying that the proof should tell you how get r(v) and t(v), but it doesn't.

But I say that's like Einstein's theories don't tell you how to build a nuclear bomb.

Implementation is separate from theory.

The proof DOES give you the route to finding r(v) and t(v) by giving you the conditions they must meet, and as I've been enamored with the proof I've ignored appeals to give r(v) and t(v), and then gave them wrong repeatedly as I didn't bother to figure them out, but after enough arguing I finally decided to settle down and figure them out.

I know that a Patricia Shanahan keeps asking for pseudo-code, but in this case the answer is easy—once you have r(v) and t(v).

Finding them involves using whatever rules you know to get k above, which is just about making the expressions coprime with respect to 2, with the caveat that if there is a way to do that with k=0 that will NOT work, so k has to be a natural number, so it is nonzero.

What makes this story kind of sad is that now, yes, the factoring problem is solved, and yes, I had a mathematical proof all along.

If posters had focused on the proof then they'd have realized it HAD to be correct, and that arguments were over an implementation detail.

So if intelligence services listened to them, or their own analysts looked the argument over and agreed with their objection, then they failed the most basic test of mathematical understanding: believe the proof first.

If you believed in mathematical proof, then you knew there had to be an answer and could find it, as I did.

I did write the definition of mathematical proof. Just Google: define mathematical proof

The factoring problem is solved. Posters ignoring mathematical proof focused on one issue looking for me to be wrong, but they were focused on an implementation detail. Now with that detail removed ANYONE who wishes can factor, including factoring RSA public keys.

RSA encryption is, as I've said for a while now, obsolete.

[A reply to his own definitions of r and t.]

That's freaking STUPID. Of course if I just divide by 2^k, r(v) + t(v) will still have the same problem!!!

Ok. I realized that. Cursed myself a few times. Pondered my own stupidity and came up with the correct answer.

r(v) and t(v) share a non-trivial factor with D

So you can just take the gcd of r(v) with D, if you find abs(r(v)) < D, with the equation:

r(v) = [(D+1)*v^2 - 2f_1*v + f_1^2]

with a rational v that gives integer r(v).

The proof assumes coprime r(v) and t(v), but those are not necessary to reach.

So that's it. I really reached desperately at first which was embarrassing. The correct answer is easier, but why didn't I think of it first?

<< Home

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