Results 1 to 4 of 4

Thread: Decrypt a catched number

  1. #1
    Junior Member
    Joined
    Oct 2012
    From
    Bonn
    Posts
    48
    Thanks
    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,722
    Thanks
    1515

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2012
    From
    Bonn
    Posts
    48
    Thanks
    1

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,722
    Thanks
    1515

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Decrypt code without the key
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Sep 6th 2012, 03:32 PM
  2. Decrypt the message
    Posted in the Math Puzzles Forum
    Replies: 0
    Last Post: Mar 13th 2012, 10:47 AM
  3. decrypt the message
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: Mar 13th 2012, 10:05 AM
  4. Replies: 3
    Last Post: Mar 27th 2011, 09:09 AM
  5. Replies: 0
    Last Post: Jun 2nd 2009, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum