Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
    
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 at 17:25

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

share|cite|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.