Re: Factoring large composite numbers

SplinterCell wrote:
> Let us take an integer which we wish to factor: x.
> Now let y = the smallest factor greater than x, where y - x is a square
> number.
> Let y - x = z
> Then, x = (sqrt(y) - sqrt(z))(sqrt(y) + sqrt(z))
>
> For example:
>
> Let x = 15
> Let y = 16
> y - x = 1 = z
> sqrt(z) = +1 or -1
> x = (4 - 1)(4 + 1)
> = 3 * 5
>
>
> Does this hold much promise or is this a dead end?

   It seems very similar to Fermat's factorization method. See
http://en.wikipedia.org/wiki/Fermat%27s_factorization_method for a
comparison. Various people have come up with Fermat's method independently.
   I think it works for y any square (other than ((x+1)/2)**2) greater
than x where y-x is a square, not just for the smallest such y. You
wouldn't think finding squares with a given difference would be as
difficult as it must be for large numbers.

--Mike Amling
Received on Mon May 1 01:54:05 2006