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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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

→ Ответить