# prime factors

Printable View

• Sep 29th 2008, 02:46 PM
bigb
prime factors
Suppose you know n = 1141367 is a product of two primes. A cryptographer is
able to tell you that http://qaboard.cramster.com/Answer-B...4062507522.gif = 1136856. Find the two prime factors of n.
• Sep 29th 2008, 06:29 PM
bigb
I think this might be a Euler's theorem problem? Any ideas??
• Sep 29th 2008, 06:40 PM
Jhevon
Quote:

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$
• Sep 29th 2008, 06:45 PM
o_O
$\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 ;)
• Sep 29th 2008, 06:50 PM
Jhevon
Quote:

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
• Sep 30th 2008, 07:40 AM
bigb
nvm i got it...sry