Results 1 to 2 of 2

Math Help - Calculate hugh mod

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    Calculate hugh mod

    Hi,

    How would one do to calculate something like a^b mod m where 0<a,b,m<10000?

    Is there an efficient algorithm do to this? I have heard (and think I understand it) that the Euler totient (phi)-function can be used, but I'm not quite sure how.

    And if we go one step further, and want to know a^b^c mod m, 0 < a,b,c,m < 10000, can we use some kind of recursive formula?

    Thanks!
    Alex
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by faximan View Post
    Hi,

    How would one do to calculate something like a^b mod m where 0<a,b,m<10000?

    Is there an efficient algorithm do to this? I have heard (and think I understand it) that the Euler totient (phi)-function can be used, but I'm not quite sure how.

    And if we go one step further, and want to know a^b^c mod m, 0 < a,b,c,m < 10000, can we use some kind of recursive formula?

    Thanks!
    Alex
    In the event that gcd(a,m) = 1, you can reduce b mod phi(m), for example 3^{101}\pmod{10}\equiv3^1\pmod{10} because (3,10)=1 and \varphi(10)=4 and 101\equiv1\pmod{4}.

    Often for a powermod calculation it's fast enough to compute by squaring while considering the exponent in binary. I explain it here (post #7).

    http://www.mathhelpforum.com/math-he...tml#post508102

    You might also like to compare with this Wikipedia article, which I found a bit hard to follow the last time I read it.

    Modular exponentiation - Wikipedia, the free encyclopedia

    For power towers, see this example (involving both totient and CRT - Chinese Remainder Theorem)

    http://www.mathhelpforum.com/math-he...on-150486.html
    Last edited by undefined; October 19th 2010 at 07:01 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 25th 2011, 12:28 AM
  2. Calculate the N.P.V
    Posted in the Business Math Forum
    Replies: 1
    Last Post: May 12th 2010, 08:28 PM
  3. How do I calculate this?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 18th 2010, 04:00 PM
  4. Calculate !
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: February 3rd 2010, 11:35 AM
  5. How to calculate ((a+b)!/a!b!) mod p
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 4th 2009, 11:57 PM

Search Tags


/mathhelpforum @mathhelpforum