TheAlgorithms · raklaptudirm · Aug 7, 2022 · Jul 27, 2022 · Jul 27, 2022 · Jul 27, 2022
@@ -18,6 +18,7 @@
 * **Cellular-Automata**
   * [ConwaysGameOfLife](Cellular-Automata/ConwaysGameOfLife.js)
 * **Ciphers**
+  * [AffineCipher](Ciphers/AffineCipher.js)
   * [Atbash](Ciphers/Atbash.js)
   * [CaesarsCipher](Ciphers/CaesarsCipher.js)
   * [KeyFinder](Ciphers/KeyFinder.js)
@@ -194,6 +195,7 @@
   * [RadianToDegree](Maths/RadianToDegree.js)
   * [ReverseNumber](Maths/ReverseNumber.js)
   * [ReversePolishNotation](Maths/ReversePolishNotation.js)
+  * [ShorsAlgorithm](Maths/ShorsAlgorithm.js)
   * [SieveOfEratosthenes](Maths/SieveOfEratosthenes.js)
   * [SimpsonIntegration](Maths/SimpsonIntegration.js)
   * [Softmax](Maths/Softmax.js)

@@ -1,32 +1,20 @@
-/*
-    Problem statement and Explanation : https://en.wikipedia.org/wiki/Euclidean_algorithm
-
-    In this method, we have followed the iterative approach to first
-    find a minimum of both numbers and go to the next step.
-*/
-
 /**
- * GetEuclidGCD return the gcd of two numbers using Euclidean algorithm.
- * @param {Number} arg1 first argument for gcd
- * @param {Number} arg2 second argument for gcd
- * @returns return a `gcd` value of both number.
+ * GetEuclidGCD Euclidean algorithm to determine the GCD of two numbers
+ * @param {Number} a integer (may be negative)
+ * @param {Number} b integer (may be negative)
+ * @returns {Number} Greatest Common Divisor gcd(a, b)
  */
-const GetEuclidGCD = (arg1, arg2) => {
-  // firstly, check that input is a number or not.
-  if (typeof arg1 !== 'number' || typeof arg2 !== 'number') {
-    return new TypeError('Argument is not a number.')
+export function GetEuclidGCD (a, b) {
+  if (typeof a !== 'number' || typeof b !== 'number') {
+    throw new TypeError('Arguments must be numbers')
   }
-  // check that the input number is not a negative value.
-  if (arg1 < 1 || arg2 < 1) {
-    return new TypeError('Argument is a negative number.')
+  if (a === 0 && b === 0) return undefined // infinitely many numbers divide 0
+  a = Math.abs(a)
+  b = Math.abs(b)
+  while (b !== 0) {
+    const rem = a % b
+    a = b
+    b = rem
   }
-  // Find a minimum of both numbers.
-  let less = arg1 > arg2 ? arg2 : arg1
-  // Iterate the number and find the gcd of the number using the above explanation.
-  for (less; less >= 2; less--) {
-    if ((arg1 % less === 0) && (arg2 % less === 0)) return (less)
-  }
-  return (less)
+  return a
 }
-
-export { GetEuclidGCD }
@@ -0,0 +1,98 @@
+/**
+ * @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/watch?v=lvTqbM5Dq4Q
+ *
+ * Shor's algorithm is a quantum algorithm for integer factorization. This
+ * function implements a version of the algorithm which is computable using
+ * a classical computer, but is not as efficient as the quantum algorithm.
+ *
+ * The algorithm basically consists of guessing a number g which may share
+ * factors with our target number N, and then use Euclid's GCD algorithm to
+ * find the common factor.
+ *
+ * The algorithm starts with a random guess for g, and then improves the
+ * guess by using the fact that for two coprimes A and B, A^p = mB + 1.
+ * For our purposes, this means that g^p = mN + 1. This mathematical
+ * identity can be rearranged into (g^(p/2) + 1)(g^(p/2) - 1) = mN.
+ * Provided that p/2 is an integer, and neither g^(p/2) + 1 nor g^(p/2) - 1
+ * are a multiple of N, either g^(p/2) + 1 or g^(p/2) - 1 must share a
+ * 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
+ * @description Finds a value p such that A^p = mB + 1.
+ * @param {BigInt} A
+ * @param {BigInt} B
+ * @returns The value p.
+ */
+function findP (A, B) {
+  let p = 1n
+  while (!isValidP(A, B, p)) p++
+  return p
+}
+
+/**
+ * @function isValidP
+ * @description Checks if A, B, and p fulfill A^p = mB + 1.
+ * @param {BigInt} A
+ * @param {BigInt} B
+ * @param {BigInt} p
+ * @returns Whether A, B, and p fulfill A^p = mB + 1.
+ */
+function isValidP (A, B, p) {
+  // A^p = mB + 1 => A^p - 1 = 0 (mod B)
+  return (A ** p - 1n) % B === 0n
+}
+
+/**
+ * @function gcd
+ * @description Euclid's GCD algorithm.
+ * @param {BigInt} A
+ * @param {BigInt} B
+ * @returns Greatest Common Divisor between A and B.
+ */
+function gcd (A, B) {
+  while (B !== 0n) {
+    [A, B] = [B, A % B]
+  }
+
+  return Number(A)
+}
+
+export { ShorsAlgorithm }
@@ -0,0 +1,29 @@
+import { ShorsAlgorithm } from '../ShorsAlgorithm'
+import { fermatPrimeCheck } from '../FermatPrimalityTest'
+
+describe("Shor's Algorithm", () => {
+  const N = 10 // number of tests
+  const max = 35000 // max value to factorize
+  const min = 1000 // min value to factorize
+
+  for (let i = 0; i < N; i++) {
+    while (true) {
+      const num = Math.floor(Math.random() * max) + min
+      // num must be composite, don't care for false negatives
+      if (fermatPrimeCheck(num, 1)) continue
+
+      it('should find a non-trivial factor of ' + num, () => {
+        const f = ShorsAlgorithm(num)
+
+        // should not be trivial
+        expect(f).not.toEqual(1)
+        expect(f).not.toEqual(num)
+
+        // should be a factor
+        expect(num % f).toEqual(0)
+      })
+
+      break
+    }
+  }
+})