How do I evade the result of infinity when I am doing 1000^1000 in a calculation in JavaScript

Question

I am trying to make an RSA like encryption program. Therefore I need to perform a calculation 1069^1099. The problem is that the result of that calculation is infinity according to Javascript. Is there any way around this problem?

var n = 23 * 83;
var e = 87;
var d = 1099;
var m = 1069;
var m = m**d % n; //Result NaN because m**d = infinity

Answer 1

If you're just developing a toy RSA cipher that doesn't use huge prime numbers, then you can implement modular exponentation as follows:

function modexp(base, exponent, modulus) {
    var result = 1;
    while (exponent) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return result;
}

The Wikipedia article has a detailed description, but what it basically does is split x^e into the product of x raised to the power of numbers corresponding to each set bit in the binary representation of e. For example, x¹³ == x⁸ × x⁴ × x¹ (because 13₁₀ == 1101₂). This can be calculated efficiently by squaring x at each step, and applying the modulus after each calculation so that the numbers don't get too large.

As others have said, you'll need a big number library to handle real-world RSA keys.