56 lines
836 B
JavaScript
56 lines
836 B
JavaScript
export function gcd(a, b) {
|
|
let x = Math.abs(a);
|
|
let y = Math.abs(b);
|
|
while (y !== 0) {
|
|
const t = y;
|
|
y = x % y;
|
|
x = t;
|
|
}
|
|
return x;
|
|
}
|
|
|
|
export function modPow(base, exp, mod) {
|
|
let result = 1;
|
|
let b = base % mod;
|
|
let e = exp;
|
|
while (e > 0) {
|
|
if (e % 2 === 1) {
|
|
result = (result * b) % mod;
|
|
}
|
|
b = (b * b) % mod;
|
|
e = Math.floor(e / 2);
|
|
}
|
|
return result;
|
|
}
|
|
|
|
export function modInverse(e, phi) {
|
|
let oldR = e;
|
|
let r = phi;
|
|
let oldS = 1;
|
|
let s = 0;
|
|
|
|
while (r !== 0) {
|
|
const q = Math.floor(oldR / r);
|
|
[oldR, r] = [r, oldR - q * r];
|
|
[oldS, s] = [s, oldS - q * s];
|
|
}
|
|
|
|
if (oldR !== 1) {
|
|
return null;
|
|
}
|
|
|
|
return ((oldS % phi) + phi) % phi;
|
|
}
|
|
|
|
export function isPrime(n) {
|
|
if (n < 2) {
|
|
return false;
|
|
}
|
|
for (let i = 2; i * i <= n; i += 1) {
|
|
if (n % i === 0) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|