Skip to content

Instantly share code, notes, and snippets.

@krzkaczor
Created May 16, 2015 23:51
Show Gist options
  • Save krzkaczor/0bdba0ee9555659ae5fe to your computer and use it in GitHub Desktop.
Save krzkaczor/0bdba0ee9555659ae5fe to your computer and use it in GitHub Desktop.
Fast modular exponentiation in Java Script
/**
* 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);
@fnlctrl
Copy link

fnlctrl commented Jun 16, 2019

@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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment