Encryption

Fermat's Little Theorem

function pow(n,e,m){
    if (e<=0) return 1n;
    let h = e/2n;
    let r = pow(n,h,m);
    r = (r*r) % m;
    if (e % 2n === 1n){
        return (n * r) % m;
    }
    return r;
}

function modInverse(a, m){
  a = (a % m + m) % m
  if (!a || m < 2n) {
    return NaN // invalid input
  }
  // find the gcd
  const s = []
  let b = m
  while(b) {
    [a, b] = [b, a % b]
    s.push({a, b})
  }
  if (a !== 1n) {
    return NaN // inverse does not exists
  }
  // find the inverse
  let x = 1n
  let y = 0n
  for(let i = s.length - 2; i >= 0; --i) {
    [x, y] = [y,  x - y * (s[i].a / s[i].b)]
  }
  return (y % m + m) % m
}