Thursday, February 19, 2009
Factoring with Pell's Equation
One of the weirder, possibly ironic twists lately has been my discovery of a direct solution to Pell's Equation with x and y functions of an independent variable:
x^2 - Dy^2 = 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)
and
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.
What makes this solution so remarkable is that there is a factoring dependency in it, but it's for D-1, not D, but you can go after factoring D by considering x and y as ratios of integer functions r, s and t:
x = r(v)/t(v), y = s(v)/t(v), gives
(r(v) - t(v))*(r(v) + t(v)) = D*(s(v))^2
which means oddly enough that just playing around, like running through some values of v, you might accidentally factor D, but the mathematics also allows you to be very serious and just directly find minima.
So why minima?
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! So those conditions cannot even occur if D is prime, but MUST occur at some value for v if it's not, and then you have a non-trivial factorization of D from the gcd's.
So the factoring problem becomes a calculus problem. Calculus. Yup. It becomes a freaking calculus problem.
Kind of like a homework one too, as the highest power is 2.
I've been talking about this solution for a while so I guess for some reason people are not getting it, possibly listening to people claiming there must be some catch, as hey, it's the factoring problem!
Sorry. No catch. The mathematics is fairly straightforward and easily verified to be correct. There IS an inherent factoring dependency, but it is for factoring D-1, not D itself. The reality of minima is as simple as I explained above. So yeah, the factoring problem is solved using Pell's Equation in a remarkable twist on thousands of years of math history in this area.
But why the lack of news?
Easiest answer is that people don't believe me. It IS the factoring problem, so there is a lot of expectations built up around it, and maybe it's kind of a letdown for the much vaunted problem to be handled so easily. Like the tiger turned out to be a tabby.
It was never REALLY hard, with computers at least, it's just no one knew how to solve it, so it felt hard until you see the answer. Like a puzzle with a simple answer that becomes too easy when you see it worked out.
Still it's weird for it to be so easy, so maybe that's a lot of it. But it's so damn strange for things to be so quiet. I will admit to not having expected this situation, and I've been waiting to talk to people, like government people, about this solution and this situation, but it has been all quiet.
Who knew? You could put out a solution to the factoring problem, on a blog, talk about it on newsgroups, and have NOTHING happen for an entire week and counting.
That sure kills all the Hollywood stories about how things would work out. Truth is way stranger than fiction.
x^2 - Dy^2 = 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)
and
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.
What makes this solution so remarkable is that there is a factoring dependency in it, but it's for D-1, not D, but you can go after factoring D by considering x and y as ratios of integer functions r, s and t:
x = r(v)/t(v), y = s(v)/t(v), gives
(r(v) - t(v))*(r(v) + t(v)) = D*(s(v))^2
which means oddly enough that just playing around, like running through some values of v, you might accidentally factor D, but the mathematics also allows you to be very serious and just directly find minima.
So why minima?
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! So those conditions cannot even occur if D is prime, but MUST occur at some value for v if it's not, and then you have a non-trivial factorization of D from the gcd's.
So the factoring problem becomes a calculus problem. Calculus. Yup. It becomes a freaking calculus problem.
Kind of like a homework one too, as the highest power is 2.
I've been talking about this solution for a while so I guess for some reason people are not getting it, possibly listening to people claiming there must be some catch, as hey, it's the factoring problem!
Sorry. No catch. The mathematics is fairly straightforward and easily verified to be correct. There IS an inherent factoring dependency, but it is for factoring D-1, not D itself. The reality of minima is as simple as I explained above. So yeah, the factoring problem is solved using Pell's Equation in a remarkable twist on thousands of years of math history in this area.
But why the lack of news?
Easiest answer is that people don't believe me. It IS the factoring problem, so there is a lot of expectations built up around it, and maybe it's kind of a letdown for the much vaunted problem to be handled so easily. Like the tiger turned out to be a tabby.
It was never REALLY hard, with computers at least, it's just no one knew how to solve it, so it felt hard until you see the answer. Like a puzzle with a simple answer that becomes too easy when you see it worked out.
Still it's weird for it to be so easy, so maybe that's a lot of it. But it's so damn strange for things to be so quiet. I will admit to not having expected this situation, and I've been waiting to talk to people, like government people, about this solution and this situation, but it has been all quiet.
Who knew? You could put out a solution to the factoring problem, on a blog, talk about it on newsgroups, and have NOTHING happen for an entire week and counting.
That sure kills all the Hollywood stories about how things would work out. Truth is way stranger than fiction.
# posted by James Harris @ 00:11 
