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!
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.
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$.
By finding that $321179=570^2-61^2=(570-61)(570+61)=509\cdot631$, which is quite non-trivial by itself.