Fast modular exponentiation in Java Script

fme.js

/**
 * Fast modular exponentiation for a ^ b mod n
 * @returns {number}
 */
var fastModularExponentiation = function(a, b, n) {
  a = a % n;
  var result = 1;
  var x = a;

  while(b > 0){
    var leastSignificantBit = b % 2;
    b = Math.floor(b / 2);

    if (leastSignificantBit == 1) {
      result = result * x;
      result = result % n;
    }

    x = x * x;
    x = x % n;
  }
  return result;
};

var assert = function(actual, expected){
  if (actual != expected){
    throw new Error('Assertion failed');
  }
};

assert(fastModularExponentiation(12, 53, 7), 3);
assert(fastModularExponentiation(7, 12, 10), 1);
assert(fastModularExponentiation(3, 51, 13), 1);

Thanks so much! Used it in my RSA Implementation

thanks!

The function does not give the expected answer in the following function to solve question 48 of Project Euler, which is to find the last 10 digits of sum(n^n) for n = 1 to 1000:

	let sum = 0;
	const digit_window = 10**10;
	for(let i = 1;i<=1000;i++){
		sum = (sum + mexp(i,i,digit_window)) % digit_window
	}
	console.log(sum);

9110846700 is expected but 6621474085 is yielded.

@devildelta that is because Javascript uses a floating point representation for numbers, in general you should not use Javascript for large arithmetic.

@y-richie-y @devildelta Now that chrome and node.js support BigInt natively, you can use javascript as well.
Simply append an n to every number literal to use BigInt:

const modExp = function (a, b, n) {
    a = a % n;
    var result = 1n;
    var x = a;
    while (b > 0) {
        var leastSignificantBit = b % 2n;
        b = b / 2n;
        if (leastSignificantBit == 1n) {
            result = result * x;
            result = result % n;
        }
        x = x * x;
        x = x % n;
    }
    return result;
};
let sum = 0n;
const digit_window = 10n**10n;
for(let i = 1n;i<=1000n;i++){
    sum = (sum + modExp(i,i,digit_window)) % digit_window
}
console.log(sum);
// 9110846700n