Encryption

From ProgZoo
Revision as of 09:28, 19 September 2021 by Andr3w (talk | contribs) (Created page with "<pre id='shellbody' data-qtp='DOM'></pre> ==Fermat's Little Theorem== <div class='qu'> <pre class='usr'> function pow(n,e,m){ if (e<=0) return 1n; let h = e/2n; le...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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
}