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.

Printable View

- Sep 29th 2008, 02:46 PMbigbprime 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 PMbigb
I think this might be a Euler's theorem problem? Any ideas??

- Sep 29th 2008, 06:40 PMJhevon
- Sep 29th 2008, 06:45 PMo_O
$\displaystyle \varphi (n) = \varphi (p_{1} \cdot p_{2}) = \varphi(p_{1}) \cdot \varphi (p_{2}) = (p_{1} - 1)(p_{2} - 1)$

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

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

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

Should be easy from here.

AH beaten ;) - Sep 29th 2008, 06:50 PMJhevon
- Sep 30th 2008, 07:40 AMbigb
nvm i got it...sry