Results 1 to 4 of 4

Math Help - Decrypt a catched number

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

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

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,895
    Thanks
    759

    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
    47
    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
    1,895
    Thanks
    759

    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.
    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: September 6th 2012, 02:32 PM
  2. Decrypt the message
    Posted in the Math Puzzles Forum
    Replies: 0
    Last Post: March 13th 2012, 09:47 AM
  3. decrypt the message
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: March 13th 2012, 09:05 AM
  4. Replies: 3
    Last Post: March 27th 2011, 08:09 AM
  5. Replies: 0
    Last Post: June 2nd 2009, 12:31 PM

Search Tags


/mathhelpforum @mathhelpforum