# Thread: Decrypt a catched number

1. ## Decrypt a catched number

Hi there

I've got the following exercise to solve:

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

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

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

Where is my fault?

Regards

2. ## 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?

3. ## 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?

4. ## 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, $\displaystyle a^{2038074743} \cong a (\mbox{mod }2038074743)$ for any integer $\displaystyle a$. So, you have $\displaystyle 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 $\displaystyle p^2$, not $\displaystyle p$. To get $\displaystyle p$, try $\displaystyle k-2 = 3\cdot 679358247$. Now $\displaystyle d^{679358247} \cong p\cdot p^{-2} (\mbox{mod }2038074743) = p^{-1} (\mbox{mod }2038074743)$. So, $\displaystyle p^3\cdot p^{-1}\cdot p^{-1} = p$. This is obtained by $\displaystyle d\cdot d^{679358247} \cdot d^{679358247} = d^{2\cdot 679358247 + 1} = d^{1358716495}$. Sure enough, this gives the correct result.