Skip to content

Instantly share code, notes, and snippets.

@serg06
Last active April 12, 2022 02:01
Show Gist options
  • Save serg06/5547b0c78cb22b2a83f8ccab9db6149b to your computer and use it in GitHub Desktop.
Save serg06/5547b0c78cb22b2a83f8ccab9db6149b to your computer and use it in GitHub Desktop.
[TypeScript] powerMod implementation
// x^p mod m
function powerMod(x: number, p: number, m: number): number {
if (m === 1) {
return 0;
}
x = x % m;
let result = 1;
while (p > 0) {
if (p % 2 === 1) {
result = (result * x) % m;
}
x = (x * x) % m;
p = p >> 1;
}
return result;
}
function powerModBigInt(x: bigint, p: bigint, m: bigint): bigint {
if (m === BigInt(1)) {
return BigInt(0);
}
x = x % m;
let result = BigInt(1);
while (p > 0) {
if (p % BigInt(2) === BigInt(1)) {
result = (result * x) % m;
}
x = (x * x) % m;
p = p >> BigInt(1);
}
return result;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment