Tuesday, January 20, 2009


JSH: Factoring with Pell's Equation

The result I noticed previously can also be a factoring result, intriguingly enough, which deserves its own thread.

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 if a target composite N to be factored is given by D-1, you have that finding a non-trivial solution to

x^2 - (N+1)y^2 = 1

will give a difference of squares with the target composite i.e.

Nj^2 + (j+/-1)^2 = (x+y)^2, where j = ((x+(N+1)y) -/+1)/(N+1).

But it's even better, as given one non-trivial solution to a Pell's Equation you can trivially generate as many more as you like, so you can continually generate tries at non-trivially factoring N.

So solving Pell's Equation is directly connected to integer factorization.

<< Home

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