# Fermat Factorization

Does anyone know how I can use Fermat Factorization to find the two prime factors of the integer $n = pq = 321179$?

I am not sure how to go about solving this and any help would be much appreciated!

-

Let $m = \lceil \sqrt{n} \rceil = 567$. Now try if $m^2-n$ is a square or $(m+1)^2-n$ is a square or... Once you've found a value (near $m$) for which this difference is a square then $n$ can be expressed as a difference of two squares, which could also give an idea of how to find a factor.

-

By finding that $321179=570^2-61^2=(570-61)(570+61)=509\cdot631$, which is quite non-trivial by itself.

-
How did you find 570 and 61? –  John Mar 24 '12 at 23:22
@Ben, see answer by WimC –  Will Jagy Mar 25 '12 at 0:15

it's too late, but want to add this, In a easier language method is:

You start adding sequence of numbers in power of two like this:

321179 + 1^2 , 321179 + 2^2, 321179 + 3^2, 321179 + 4^2

until we find a perfect sequare number. After a little brute-forcing, we find out that

321179 + 61^2 = 324900 which has a square root of 570

So we take 61 as difference, then we calculate

(570 - 61) = 509 (570 + 61) = 631

So you have successfully found factors of your number which are 509 and 631

-