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² * 7

this way, 

g^p = 64² = 3² * 5 * 7 * 13 + 1

so in the end

m = 3² * 5 = 45   and   N = 7 * 13 = 91