# Shor's algorithm

**Euclid's algorithm is a way to find common divisors. Use this algorithm to find the greatest common divisor of 210 and 45.**

210 = 45 * 4 + 30

45 = 30 * 1 + 15

30 = 15 * 2

which means gcd(210, 45) = 15

**Now, let's say that we have a number N=91, whose factors are 7 and 13. If we choose as a random guess g=64, which power p gives us the following expression?**

**g ^{p }= m*N → (g^{p/2 }+ 1)*(g^{p/2} - 1) = m*N**

p = 2 → g^{p/2} + 1 = 64^{2/2} + 1 = 64 + 1 = 65 = 5 * 13

→ g^{p/2} - 1 = 64^{2/2} - 1 = 64 - 1 = 63 = 3^{2} * 7

this way,

g^{p} = 64^{2} = 3^{2} * 5 * 7 * 13 + 1

so in the end

m = 3^{2} * 5 = 45 and N = 7 * 13 = 91