Results 1 to 6 of 6

Math Help - Discrete Logarithms

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    89

    Discrete Logarithms

    Given that:

    3^6 = 44 (mod 137)
    3^10 = 2 (mod 137)

    find x such that 3^x = 11 (mod 137)
    such that 0 < x < 135

    My attempt:
    I first noticed that fact that 11 = (44/2)/2
    So I tried using that.
    I though maybe I can subtract the exponents and test my luck.
    (3^6)/(3^10) = (3^-4)
    (3^-4)/(3^10) = (3^-14)
    -14 + 137 = 123

    Doesn't work out. And Im sure there are a few things wrong with this.
    Ive been looking at this question for quite some time. So now I am here for advice.

    The answer I am looking for is 122.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2007
    Posts
    89
    More info:
    From looking at an ElGamal Cryptosystem example (http://www14.informatik.tu-muenchen....yptosystem.pdf)
    There is a statement that says 15^-5 (mod 17) = 15 ^11 (mod 17) = 9

    Is it just a coincidence that -5 + 17 = 12 (1 more than 11) and -14 + 137 = 123 (1 more than 122)?
    What is the proper way to solve modular arithmetic with a negative exponent?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chrisc View Post
    There is a statement that says 15^-5 (mod 17) = 15 ^11 (mod 17) = 9
    By Fermat's Little Theorem is m \equiv n ~\text{(mod p - 1)} then a^m \equiv a^n~\text{(mod p)}. In this case -5 \equiv 11 ~\text{(mod 16)} thus 15^{-5} \equiv 15^{11} ~\text{(mod 17)}.

    I'm working on your original problem, but don't expect results. I'm not catching on how to look at it.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chrisc View Post
    What is the proper way to solve modular arithmetic with a negative exponent?
    5^(-15) = 1/3^(15). Since this is a fraction and no fractions can be allowed in modular math, we need to prove that the inverse exists.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by chrisc View Post
    Given that:

    3^6 = 44 (mod 137)
    3^10 = 2 (mod 137)

    find x such that 3^x = 11 (mod 137)
    such that 0 < x < 135

    My attempt:
    I first noticed that fact that 11 = (44/2)/2
    So I tried using that.
    I though maybe I can subtract the exponents and test my luck.
    (3^6)/(3^10) = (3^-4)
    (3^-4)/(3^10) = (3^-14)
    -14 + 137 = 123

    Doesn't work out. And Im sure there are a few things wrong with this.
    Ive been looking at this question for quite some time. So now I am here for advice.

    The answer I am looking for is 122.
    Got it. Remember Fermat's Little Theorem? We're doing the reverse: (This is all mod 137, a prime.)
    2 \cdot 2 \cdot 11 = 44

    3^{10} \cdot 3^{10} \cdot 3^x = 44 = 3^6

    3^{20 + x} = 3^6

    This is all mod 137. But the reverse of Fermat's Little says that if a^m \equiv a^n ~\text{(mod p)} then m \equiv n ~\text{(mod p-1)}.

    Thus since 3^{20 + x} \equiv 3^6 ~\text{(mod 137)} implies that 20 + x \equiv 6 ~\text{(mod 136)}. Thus x = 122.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2007
    Posts
    89
    well that does solve the problem, no?

    since -14 = 122 (mod 136)

    *just saw your new post. ill check it out
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logarithms
    Posted in the Algebra Forum
    Replies: 4
    Last Post: October 30th 2010, 07:10 PM
  2. logarithms
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 24th 2010, 05:26 AM
  3. Logarithms :(
    Posted in the Algebra Forum
    Replies: 8
    Last Post: July 21st 2009, 09:33 PM
  4. logarithms
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 14th 2008, 05:05 PM
  5. Logarithms
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 11th 2008, 12:17 PM

Search Tags


/mathhelpforum @mathhelpforum