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?

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?

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.