Results 1 to 2 of 2

Math Help - Help with modular arithmetic

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    156

    Help with modular arithmetic

    I'm doing some self-study in cryptography and have come across something that I don't understand. Hoping somebody can help me with the gap in my knowledge.

    I'm trying to follow an algorithm to compute exponentiation using Euler (really Fermat), and am stuck on some modular arithmetic. The problem before me is to compute

    2^{{{110001}^{11}}^{1100001}} mod 23

    The example that I am studying right now says that this is equal to: 2^{{{110001}^{11}}^{1100001} mod 22} mod 23 , which I can see is an application of Fermat's theorem (since 23 is prime). The next step is what I don't understand. They go on to apply Fermat again, saying that:

    110001^{{11}^{1100001}} \equiv 110001^{{11}^{1100001} mod 10}   mod 22

    I understand why they switched to mod 10 (there are 10 elements in the set phi(22)). What I don't understand are the following:

    1) How can they drop the base 2?
    2) Where did the mod 23 go? (these might be the same property)

    Clearly, there is some property of modular arithmetic that I don't understand in applying these theorems. Can anyone explain this to me?

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2011
    Posts
    156

    Re: Help with modular arithmetic

    Never mind, I figured it out. They weren't saying that all of these are equivalent. In the second step they are just isolating the exponent for the purpose of simplifying it by way of Fermat's theorem. As the solution goes on, once they get the exponent simplified all the way, they go on to build back up sequentially to the original problem, which is then easily solvable. Thanks anyway.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 6th 2011, 02:14 AM
  2. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2011, 01:37 PM
  3. modular arithmetic
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: March 18th 2010, 08:33 AM
  4. Modular arithmetic help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 4th 2008, 08:47 AM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 08:39 PM

Search Tags


/mathhelpforum @mathhelpforum