Let me show how Shor's algorithm works. It's really a classical algorithm, and the reason it is only thought of as quantum, is that it is unfeasible to finish the period-finding step for a significant semiprime without a quantum computer.
We can factor 145 with Shor on a classical computer, though.
First, we generate a random number. I'll call it m. It must be lower than c.
Next, we test to see if gcd(m, c) != 1. If it is not equal to 1, we have factored c.
Now comes the difficult step which is only feasible on classical computers for smaller semiprimes. We are going to calculate an unending sequence until we find where it repeats.
Evaluate
m mod c, m^2 mod c, m^3 mod c, m^4 mod c, m^5 mod c, m^6 mod c, m^7 mod c.. Until it repeats. When it repeats, the amount of terms before a repeat value is the period. We'll call it r.
If r is odd, we must go back to step 1 and try a different random number.
If c is a factor of (m^(r/2) + 1), we must go back to step 1 and try a different number.
If all of these steps have passed, we have the factors of the number.
gcd(m^(r/2) + 1, c) = a
gcd(m^(r/2) - 1, c) = b
You could just divide c/a without evaluating b, though. Let's go through an example. It's really cool.
Let's pick 18 as our random m to factor 145.
gcd(18, 145) = 1, so, next step is to evaluate the sequence.
18 mod 145 = 18
18^2 mod 145 = 34
18^3 mod 145 = 32
18^4 mod 145 = 141
18^5 mod 145 = 73
18^6 mod 145 = 9
18^7 mod 145 = 17
18^8 mod 145 = 16
18^9 mod 145 = 143
18^10 mod 145 = 109
18^11 mod 145 = 77
18^12 mod 145 = 81
18^13 mod 145 = 8
18^14 mod 145 = 144
18^15 mod 145 = 127
18^16 mod 145 = 111
18^17 mod 145 = 113
18^18 mod 145 = 4
18^19 mod 145 = 72
18^20 mod 145 = 136
18^21 mod 145 = 128
18^22 mod 145 = 129
18^23 mod 145 = 2
18^24 mod 145 = 36
18^25 mod 145 = 68
18^26 mod 145 = 64
18^27 mod 145 = 137
18^28 mod 145 = 1
18^29 mod 145 = 18 ← repeat value
18^30 mod 145 = 34
So we can see that it has repeated. The amount of terms before the repeat is 28, so that is the period, r.
m^(r/2) + 1 = 374813367582081025
c is a factor of this number, which means we have to restart.
if we want to be sure this number doesn't work, we can try the equation.
gcd(m^(r/2) + 1, c) = 145
gcd(m^(r/2) - 1, c) = 1
Let's try 19 as m.
gcd(19, 145) = 1
Calculate sequence..
The period is 28.
c is not a factor of 19^(28/2) + 1
gcd(m^(r/2) + 1, c) = 29
gcd(m^(r/2) - 1, c) = 5