# Thread: prime factors

1. ## prime factors

Suppose you know n = 1141367 is a product of two primes. A cryptographer is
able to tell you that = 1136856. Find the two prime factors of n.

2. I think this might be a Euler's theorem problem? Any ideas??

3. Originally Posted by bigb
I think this might be a Euler's theorem problem? Any ideas??
actually, it is an RSA problem

let the primes be $p$ and $q$

note that $\phi = (p - 1)(q - 1)$

and remember you have $pq = n \implies p = \frac nq$

4. $\varphi (n) = \varphi (p_{1} \cdot p_{2}) = \varphi(p_{1}) \cdot \varphi (p_{2}) = (p_{1} - 1)(p_{2} - 1)$

So: $(p_{1} - 1)(p_{2} - 1) = 1136856$

But since: $n = p_{1}p_{2} \ \Rightarrow \ p_{2} = \frac{n}{p_{1}}$

We have that: $(p_{1}-1)\left(\frac{n}{p_{1}} - 1\right) = 1136856$

Should be easy from here.

AH beaten

5. Originally Posted by o_O
AH beaten
that's right! Mr. o_O!

oh! i see, bigb was referring to the Euler-Phi function. ok. never heard it called theorem before

6. nvm i got it...sry