Fermat Factorization

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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

Your number is $321179$

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$.