Function ShorsAlgorithm

Maths/ShorsAlgorithm.js:25–55

* @function ShorsAlgorithm * @description Classical implementation of Shor's Algorithm. * @param {Integer} num - Find a non-trivial factor of this number. * @returns {Integer} - A non-trivial factor of num. * @see https://en.wikipedia.org/wiki/Shor%27s_algorithm * @see https://www.youtube.com/w

(num)

 * factor with N, which can then be found using Euclid's GCD algorithm.
 */
function ShorsAlgorithm(num) {
  const N = BigInt(num)

  while (true) {
    // generate random g such that 1 < g < N
    const g = BigInt(Math.floor(Math.random() * (num - 1)) + 2)

    // check if g shares a factor with N
    // if it does, find and return the factor
    let K = gcd(g, N)
    if (K !== 1) return K

    // find p such that g^p = mN + 1
    const p = findP(g, N)

    // p needs to be even for it's half to be an integer
    if (p % 2n === 1n) continue

    const base = g ** (p / 2n) // g^(p/2)
    const upper = base + 1n // g^(p/2) + 1
    const lower = base - 1n // g^(p/2) - 1

    // upper and lower can't be a multiple of N
    if (upper % N === 0n || lower % N === 0n) continue

    // either upper or lower must share a factor with N
    K = gcd(upper, N)
    if (K !== 1) return K // upper shares a factor
    return gcd(lower, N) // otherwise lower shares a factor
  }
}

/**
 * @function findP