1
$\begingroup$

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!

3 Answers 3

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.

1

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

  • 0
    This misses the point of Fermat's method, as it is just as laborious as trial division counting downwards from $\sqrt{n}$. The preferable idea is to iterate over the *larger* square, which grows much more rapidly than the smaller square. You only have to iterate 4 times this way rather than 61 times using your method!2016-05-30
0

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

  • 0
    @Ben, see answer by WimC2012-03-25