Блог пользователя vigroh_9

How to calculate: a ^ n mod BASE with n is a big integer, a and n are not coprimes?
Автор vigroh_9, 10 лет назад, По-английски

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).

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

          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:)

          → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      → Ответить