modpow biginteger javascript

Question

I look for a good algorithme JavaScript because I tried this with 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);
}

}

But I have an error : RangeError: Maximum call stack size exceeded

Did you try with an iterative version, for instance something like that http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method ? — user189, Jun 12 '14 at 09:40
You could use a library that does it for you, like Crunch (http://crunch.secureroom.net). It includes modular exponentiation code. Or look at Chapter 14 in the Handbook of Applied Cryptography, it has lots of algorithms, and is available free online. — Nenad Vukicevic, Jun 12 '14 at 09:43
one thing that i notice is that BigInt(1) where 1 is not in '' — Vikram Bhat, Jun 12 '14 at 10:07
look here http://stackoverflow.com/q/18577076/2521214 for mine implementation of modpow in C++. I am not JAVA coder but most likely you have some problem inside modpow_2 and also I do not see the logic behind your pow computation (missing some form of loop but it can be there in form of that recursion but you do not provide modpow_2 code so hard to say), btw instead of divide by 2 you can use bit shift (on bigint the compiler can not do that for you via optimizations) — Spektre, Jun 13 '14 at 07:04

score 0 · Answer 1 · answered May 18 '23 at 14:03

Try something like this ...

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)

modpow biginteger javascript

1 Answers1