forked from TheAlgorithms/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathShorsAlgorithm.js
More file actions
98 lines (86 loc) · 2.9 KB
/
ShorsAlgorithm.js
File metadata and controls
98 lines (86 loc) · 2.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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 }