Modulus Силы

Question

У меня была проблема, что из расчета a^b mod m, является можно с помощью модульного возведения в степень, но проблема я имею в том, что б у меня есть очень большое значение, b > 2^63 - 1 так мы можем изменить модульный код возведения в степень

 
function modular_pow(base, exponent, modulus) 
    result := 1 
    while exponent > 0 
     if (exponent mod 2 == 1): 
      result := (result * base) mod modulus 
     exponent := exponent >> 1 
     base = (base * base) mod modulus 
    return result 

для размещения такого большого b

или это правильно, что a^b mod m равно (a^(b mod m)) mod m?

Answer 1

Это правильно, что a^b mod m = a^(b mod phi(m)) mod m, где фи (м) является Euler totient function

Ваш код правильный тоже (если типы достаточно долго, чтобы представить все значения)

Вы также можете объединить два метода