ExtendedEuclideanGCD.js

/**
 * Problem statement and explanation: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
 *
 * This algorithm plays an important role for modular arithmetic, and by extension for cryptography algorithms
 *
 * Basic explanation:
 * The Extended Euclidean algorithm is a modification of the standard Euclidean GCD algorithm.
 * It allows to calculate coefficients x and y for the equation:
 *          ax + by = gcd(a,b)
 *
 * This is called Bézout's identity and the coefficients are called Bézout coefficients
 *
 * The algorithm uses the Euclidean method of getting remainder:
 * r_i+1 = r_i-1 - qi*ri
 * and applies it to series s and t (with same quotient q at each stage)
 * When r_n reaches 0, the value r_n-1 gives the gcd, and s_n-1 and t_n-1 give the coefficients
 *
 * This implementation uses an iterative approach to calculate the values
 */

/**
 *
 * @param {Number} arg1 first argument
 * @param {Number} arg2 second argument
 * @returns Array with GCD and first and second Bézout coefficients
 */
const extendedEuclideanGCD = (arg1, arg2) => {
  if (typeof arg1 !== 'number' || typeof arg2 !== 'number')
    throw new TypeError('Not a Number')
  if (arg1 < 1 || arg2 < 1) throw new TypeError('Must be positive numbers')

  // Make the order of coefficients correct, as the algorithm assumes r0 > r1
  if (arg1 < arg2) {
    const res = extendedEuclideanGCD(arg2, arg1)
    const temp = res[1]
    res[1] = res[2]
    res[2] = temp
    return res
  }

  // At this point arg1 > arg2

  // Remainder values
  let r0 = arg1
  let r1 = arg2

  // Coefficient1 values
  let s0 = 1
  let s1 = 0

  // Coefficient 2 values
  let t0 = 0
  let t1 = 1

  while (r1 !== 0) {
    const q = Math.floor(r0 / r1)

    const r2 = r0 - r1 * q
    const s2 = s0 - s1 * q
    const t2 = t0 - t1 * q

    r0 = r1
    r1 = r2
    s0 = s1
    s1 = s2
    t0 = t1
    t1 = t2
  }
  return [r0, s0, t0]
}

export { extendedEuclideanGCD }