# Decrypt a catched number

• Sep 28th 2013, 05:41 AM
huberscher
Decrypt a catched number
Hi there

I've got the following exercise to solve:

-
One sends the $d=p^3 \in \mathbb{Z}_{2038074743}$. You catch up $d=1933360524$. Calculate p now.
-

With $k:=2038074743$ I have by Euclid $1=679358248*3-k$ so as far as I know $c^{679358248}=p$ in $\mathbb{Z}_k$

I calculated this a couple of times now. I get p=709704058 but $p^3 \text{ MOD } k$ is not d.

Where is my fault?

Regards
• Sep 28th 2013, 05:51 PM
SlipEternal
Re: Decrypt a catched number
Here is your answer: p^3 congruent to 1933360524 mod 2038074743 - Wolfram|Alpha

Work backwards to figure out where you went wrong?
• Sep 29th 2013, 02:21 AM
huberscher
Re: Decrypt a catched number
I don't find a mistake in my calculation except the end result. Working backwards here is not possible as far as I know.

Does noone see where my mistake is?

1933360524^679358248 MOD n is not 113746 . Noone an idea?
• Sep 29th 2013, 05:50 AM
SlipEternal
Re: Decrypt a catched number
Ok, looking more closely at what you are doing, your mistake is in how you apply Euclid. Since 2038074743 is prime, $a^{2038074743} \cong a (\mbox{mod }2038074743)$ for any integer $a$. So, you have $d^{679358248} = p^{3\cdot 679358248} = p^{k+1} = p^k\cdot p \cong p\cdot p (\mbox{mod }2038074743)$. In other words, you are getting $p^2$, not $p$. To get $p$, try $k-2 = 3\cdot 679358247$. Now $d^{679358247} \cong p\cdot p^{-2} (\mbox{mod }2038074743) = p^{-1} (\mbox{mod }2038074743)$. So, $p^3\cdot p^{-1}\cdot p^{-1} = p$. This is obtained by $d\cdot d^{679358247} \cdot d^{679358247} = d^{2\cdot 679358247 + 1} = d^{1358716495}$. Sure enough, this gives the correct result.