1

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!

bzc
  • 8,622
John
  • 13

3 Answers3

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.

WimC
  • 32,192
  • 2
  • 48
  • 88
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$.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
Vahid Farahmand
  • 111
  • 1
    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! – Erick Wong May 30 '16 at 17:25
0

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

Asaf Karagila
  • 393,674
Dennis Gulko
  • 15,640