modpow 大整数 javascript

Question

我在寻找一个好的 JavaScript 算法，因为我用 node.js 尝试过这个：

function modpow_3(a,n, module){
var u = BigInt('1');
var e = equals(a, u);
if( e) return a;
if(equalsZero(a)) return a;
if(pair(n)){
    x= modpow_2(a, (divide(n, BigInt('2'))));
    return mod(multiply(x,x), module);
}else{      
    x= modpow_2(a, (divide(subs(n, BigInt(1) ), BigInt('2'))));
    return mod(multiply(multiply(x,x), a), module);
}

}

但是我有一个错误： RangeError：超出最大调用堆栈大小

Answer 1

尝试这样的事情......

const prime = 101n
function modPow(expo, base, p=prime) {
  // "expo" needs to be of type BigInt
    let x = BigInt(base) % p, res = expo & 1n? x: 1n
    do {
        x = x**2n % p
        if (expo & 2n) res = res * x % p
    } while (expo /= 2n)
    return res
}
const res = modPow(9n, 2n)