Sunday, January 25, 2009
Pell's Equation and the factoring problem
One of the weirder things to emerge recently from my latest research on solving quadratic Diophantine equations is a route to factoring using Pell's Equation where I'll admit a lot of details did not occur to me, but were pointed out by others.
What I found was that given x^2 - Dy^2 = 1
you have solutions for an ellipse or Pythagorean triples with
(D-1)j^2 + (j+/-1)^2 = (x+y)^2
where j = ((x+Dy) -/+1)/D, and j can be a fraction.
So it's this trivial little equation—always been there—which unites Pell's Equation to Diophantine ellipses which can be Pythagorean triples when D-1 is a square.
Now factoring comes into the picture because you can conceivably set D equal to your target composite to be factored, and then
x^2 - 1 = Dy^2, so (x-1)(x+1) = Dy^2
might non-trivially factor D, which was noted by the poster Colin Barker, but I'd guess that approach hasn't been considered viable because it's thought hard to get non-zero solutions for x and y BUT it IS easy to get non-zero solutions to Pythagorean triples or Diophantine ellipses, and the equations I found go in BOTH directions. Here's a demonstration where I worked from a Pythagorean triple.
Consider, 24^2 + 7^2 = 25^2.
If 7 is j+/-1, I can try j = 6 or 8, and find D=17 or D=10.
With j=6, D=17, I have j = ((x+Dy) -/+1)/D, so
17(6) = x+17y -/+ 1, so x+17y = 17(6)+/-1, and x+y = 25, so
16y = 17(6)+/-1 - 25, which doesn't give an integer y, which is ok, but I want an integer for this demonstration.
And trying j=8, D=10:
x+10y = 10(8)+/-1, so 9y = 10(8)+/-1 - 25, gives y = 6 as a solution, so x = 19, and
19^2 - 10(6)^2 = 1.
So you can go in either direction, though you may get a fractional j, giving the more general form u^2 - Dy^2 = C^2.
But that is ok for factoring as then you just have: (u-C)(u+C) = Dy^2
The simplicity of solving Diophantine ellipses was noted by the poster Achava. That is equations of the form:
nu^2 + v^2 = w^2
as you can use w+v = nu, w-v = u.
Then the latest research indicates that it is not at all difficult to find non-zero solutions to
x^2 - Dy^2 = C^2
where D is picked and C is determined by the method.
It occurs to me that no one knew before that you could directly connect Pell's Equation to Pythagorean triples and Diophantine ellipses, as if they did, then this solution would have been known.
To me that is further indication of a disturbing reality I've often noted on the newsgroups where posters make bold claims about research being "not new", no matter what the territory. So it is clear that they make things up.
Given that you can go in either direction from Pythagorean triples to a general form of the Pell's Equation, or from a Pell's Equation to Pythagorean triples or Diophantine ellipses, it seems very unlikely that factoring would have been considered a hard problem if this information had been previously known.
It also seems extremely unlikely that the world's Internet security system would be based on it, or that RSA encryption would exist.
Therefore, it is clear that the information must be in many ways new. Factoring was never a hard problem.
People simply were wrongly convinced it was because some simple algebra was, I guess, unknown, though it's not clear why it was not known. It is easy algebra, after all.
Trivially easy algebra.
What I found was that given x^2 - Dy^2 = 1
you have solutions for an ellipse or Pythagorean triples with
(D-1)j^2 + (j+/-1)^2 = (x+y)^2
where j = ((x+Dy) -/+1)/D, and j can be a fraction.
So it's this trivial little equation—always been there—which unites Pell's Equation to Diophantine ellipses which can be Pythagorean triples when D-1 is a square.
Now factoring comes into the picture because you can conceivably set D equal to your target composite to be factored, and then
x^2 - 1 = Dy^2, so (x-1)(x+1) = Dy^2
might non-trivially factor D, which was noted by the poster Colin Barker, but I'd guess that approach hasn't been considered viable because it's thought hard to get non-zero solutions for x and y BUT it IS easy to get non-zero solutions to Pythagorean triples or Diophantine ellipses, and the equations I found go in BOTH directions. Here's a demonstration where I worked from a Pythagorean triple.
Consider, 24^2 + 7^2 = 25^2.
If 7 is j+/-1, I can try j = 6 or 8, and find D=17 or D=10.
With j=6, D=17, I have j = ((x+Dy) -/+1)/D, so
17(6) = x+17y -/+ 1, so x+17y = 17(6)+/-1, and x+y = 25, so
16y = 17(6)+/-1 - 25, which doesn't give an integer y, which is ok, but I want an integer for this demonstration.
And trying j=8, D=10:
x+10y = 10(8)+/-1, so 9y = 10(8)+/-1 - 25, gives y = 6 as a solution, so x = 19, and
19^2 - 10(6)^2 = 1.
So you can go in either direction, though you may get a fractional j, giving the more general form u^2 - Dy^2 = C^2.
But that is ok for factoring as then you just have: (u-C)(u+C) = Dy^2
The simplicity of solving Diophantine ellipses was noted by the poster Achava. That is equations of the form:
nu^2 + v^2 = w^2
as you can use w+v = nu, w-v = u.
Then the latest research indicates that it is not at all difficult to find non-zero solutions to
x^2 - Dy^2 = C^2
where D is picked and C is determined by the method.
It occurs to me that no one knew before that you could directly connect Pell's Equation to Pythagorean triples and Diophantine ellipses, as if they did, then this solution would have been known.
To me that is further indication of a disturbing reality I've often noted on the newsgroups where posters make bold claims about research being "not new", no matter what the territory. So it is clear that they make things up.
Given that you can go in either direction from Pythagorean triples to a general form of the Pell's Equation, or from a Pell's Equation to Pythagorean triples or Diophantine ellipses, it seems very unlikely that factoring would have been considered a hard problem if this information had been previously known.
It also seems extremely unlikely that the world's Internet security system would be based on it, or that RSA encryption would exist.
Therefore, it is clear that the information must be in many ways new. Factoring was never a hard problem.
People simply were wrongly convinced it was because some simple algebra was, I guess, unknown, though it's not clear why it was not known. It is easy algebra, after all.
Trivially easy algebra.
# posted by James Harris @ 11:42 
