Take the 2-minute tour ×
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.

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|improve this question

3 Answers 3

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|improve this answer

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

share|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

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|improve this answer

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.