vigroh_9's blog

How to calculate: a ^ n mod BASE with n is a big integer, a and n are not coprimes?
By vigroh_9, 10 years ago, In English

How to calculate: a ^ n mod BASE with n is a big integer, a and n are not coprimes? I have a formula: a ^ n mod BASE = a ^ (n % phi(BASE) + phi(BASE)) mod BASE. Is this correct? Can somebody prove it if correct?

Thanks. (Sorry for my bad English).

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Suppose you need 2^0 mod 4. The answer is 1 and you'll find 2^phi(4)=0

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks you for your reply, so, How to calculate: a ^ n mod BASE with n is a big integer, a and n are not coprimes? (Sorry for my bad English).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      probably you mean a and base are not coprimes.

      I think your formula should work for n >= phi(base)

      So you may for each level calculate value with appropriate modulo and also check whether it's more than those module

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thank you :) I will try (Sorry for my bad English)

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it +12 Vote: I do not like it

          You're welcome

          BTW, Your English (It's not me who may judge if it is really bad) bothers me much less than (sorry for my bad English) at the end of each post:)

          → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The function for computing what you want is the following (try to understand it as an exercise)

int pow_mod (int a, int n, int mod)
{
    int ans = 1;

    for (; n; n >>= 1)
    {
        if (n & 1)
            ans = (ans * 1ll * a) % mod;

        a = (a * 1ll * a) % mod;
    }

    return ans;
}

In the case where n is a big integer, you only need to convert it to binary and the apply the function above. I hope this can help you.

NOTE: In the case that you don't understand the above function, just ask me

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Just wondering — is it safe to assume, that ans * 1ll will happen first and get ans converted into long long? Is it defined behavior that compiler must multiply left to right one by one?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Arithmetic operators with same precedence are always evaluated from left to right.

      But in the expression (3 / 1) + (4 / 2) operators / may be called in any order.

      → Reply