algorithm - 大数除法余数

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) 模 19 = (3^(18*4) * 3 * 10^(18*4) * 10^2) 模 19

现在，通过 Fermst 小定理 ( m^(p-1) mod p = 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 Bhat 显示的实现更有效。

Answer 2

使用模幂：-

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

更快的模幂运算：-

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