Остаток при разделении большого числа

Question

Что остальное, когда 30^74 делится на 57?

Я знаю, как правило, для решения такой проблемы, вы бы использовали Маленькую теорему Ферма, но в этом случае 57 не является простым числом, поэтому я не уверен, как подойти к этому. Есть идеи?

Answer 1

30^74 по модулю 57 = (3^74 * 10^74) по модулю 3 * 19 = 3 * [(3^73 * 10^74) по модулю 19]

и

(3^73 * 10^74) mod 19 = (3^(18 * 4) * 3 * 10^(18 * 4) * 10^2) mod 19

теперь по малой теореме Фермста (m^р-1) по модулю р = 1):

(3^73 * 10^74) по модулю 19 = (3 * 10^2) по модулю 19 = 300 мод 19 = 15

поэтому

30^74 мод 57 = 3 * 15 = 45

---

Основная реализация модульного метода возведения в степень, чтобы получить остаток:

long modular_pow(long base, long exponent, long modulus) { 
    long c = 1; 
    for (long e_prim = 0; e_prim < exponent; ++e_prim) { 
     c = (c * base) % modulus; 
    } 
    return c; 
} 

Однако реализация показана @Vikram Бхат является более эффективным.

Answer 2

Использование модульного возведения в степень: -

modexp(a,pow) = (a*modexp(a,pow-1))%p 

Faster модульная экспоненцирование: -

public static long modexp(long a,long pow,long p) { 

     if(pow==0) { 
      return(1); 
     } 

     long t = modexp(a,pow/2,p); 
     t = (t*t)%p; 

     if(pow%2==1) { 
      t = (t*a)%p; 
     } 

     return(t); 

    } 

вызова: -modexp(30,74,57)

Время Сложность:O(log(pow))