Sunday, March 15, 2009


JSH: So what happened?

Some of you may have noticed a very big discussion over the last few weeks where I've claimed to have solved the factoring problem and various posters have said I haven't and put up issues with my claims.

So here's a quick synopsis to get you up to speed on what happened:

1. I noticed that you can use Pell's Equation to do dual factorizations to attack factoring a composite target D by factoring D-1 instead:

In rationals, x^2 - Dy^2 = 1

requires that

(D-1)j^2 + (j+/-1)^2 = (x+y)^2

where j = ((x+Dy) -/+1)/D.

Ok, so I know you've seen that but the issue was how to actually get a key variable called v, where j=uv, and I had an explicit solution for x that looked like:

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 integers, while v is a free variable, which is a mess I didn't want to deal with, so I didn't try to simplify it, and just hoped others with math software would do so, but I talked about factoring D non-trivially with its numerator and denominator, as with functions I call r(v) and t(v), and


it is trivial that if they are integers and abs(r(v) - t(v)) < D, and abs(r(v) + t(v)) < D, then you non-trivially factor D.

And I'd proven the existence of integer solutions so I thought I was done.

But posters started claiming they couldn't work, and some put up:

r(v) + t(v) = 2Dv^2

which to me implied that v had to have a non-trivial factor in common with D before you could use it, but hey, that couldn't work as v is squared, so you'd always have a fraction! So I figured they were lying, and said so repeatedly as I didn't want to bother with that monster expression I had for x, and kept thinking that all those plus or minuses meant a lot of variations.

But I was wrong. I finally simplified things further and found a simple equation for x:

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

And lo and behold if adding the numerator to the denominator didn't give what I'd claimed had to be wrong!!!

Turned out the math was more subtle than I'd imagined and was slapping a freaking non-trivial factor of D on the numerator and denominator. That divides off easily enough—if you know what it is—but when you add them, you get 2Dv^2.

But NOT a big deal as instead of taking the gcd of r(v) + t(v) with D as I'd originally said, you take it with r(v). No worries, I thought.

But then I noticed that I could NOT get

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


t(v) = f_1*(f_1 - f_2*v^2 - 2v)

to both be integers with a rational v. It was a what the f-moment.

Turns out the algebra had one more trick up its sleeve as both have been divided by 2.

They have to both be integers to force a non-trivial solution with abs(r(v)) < D—oh yeah, I found that as a primary condition—so I ended up needing to multiply both by 2, and that's it.

However, a month of me working through these issues, especially weeks of me refusing to simplify x left the door open to posters who spread confusion about the result! One funny part though was when they specifically claimed it couldn't factor 15. But I had an example of a factorization of 15, so I knew they were wrong.

And that's the story, of how there can have been so much debate about a solution to the factoring problem for weeks.

Synopsis: I didn't feel like simplifying a key equation. The algebra had some subtleties that opened the door to confusion if you DID simplify the damn thing. And even after that point you needed to figure out one more wacky thing as in the functions had been divided by 2, and then everything works just fine.

Factoring problem is solved. No more room for confusion about the result. All issues are resolved.

<< Home

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