Results 1 to 3 of 3

Math Help - Modular Logs

  1. #1
    Newbie cryptocrow's Avatar
    Joined
    Jun 2008
    Posts
    11

    Modular Logs

    good morning,

    encrypt: c = m^3 (mod 101)
    decrypt: m = c^d (mod 101)

    how would i solve for d (with the most efficient method by hand)?

    thanks...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by cryptocrow View Post
    good morning,

    encrypt: c = m^3 (mod 101)
    decrypt: m = c^d (mod 101)

    how would i solve for d (with the most efficient method by hand)?

    thanks...
    \begin{aligned} m & \equiv c^d \ [101] \\<br />
&\equiv (m^3)^d \ [101] \\<br />
&\equiv m^{3d} \ [101] \end{aligned}

    So d is such that m^{3d} \equiv m \ [101]

    Euler's theorem :
    m^{\varphi(n)} \equiv 1 \ [n]

    Here, n=101 and is prime. \varphi(101)=100

    3d has to be congruent to 1 \mod \varphi(101), i.e. 1 \mod 100
    --------
    Why ?

    m^{3d}=m^{1+100k}=m \cdot \left(m^{100}\right)^k=m \mod 101
    --------
    So we want to find the inverse of 3 modulo 100.

    100=3 \cdot 33+1 \implies 3 \cdot (-33)=1-100

    \Longleftrightarrow 3 \cdot (-33) \equiv 1 \mod 100

    3 \cdot 67 \equiv 1 \mod 100

    d=67




    But you have to be careful, because either I've confused myself, either this is a particular case. In general, the number which would be at the same place as 101 is rarely prime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie cryptocrow's Avatar
    Joined
    Jun 2008
    Posts
    11
    thank's a lot for the detailed info!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 9
    Last Post: February 22nd 2011, 05:39 PM
  2. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 03:40 PM
  3. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2009, 11:16 AM
  4. Dealing with Logs and Natural Logs
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 14th 2008, 06:18 AM
  5. several questions-logs/natural logs
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 12th 2007, 08:58 PM

Search Tags


/mathhelpforum @mathhelpforum