Shor's Algorithm and Permutations

Question

I read some articles about Shor's algorithm but I can't understand how it works. From my point of view it makes the problem even more complex from O(2^n) to O(n!). How does the oracle that is suppose to solve the modular division simultaneously calculate $r_x \equiv a^x \pmod N$ for all $x$s between $0$ to $2^n$ without permutating?

If $x_j=\sum_i 2^i$, Isn't n! permutations on j needed?! $$r_x \equiv a^{x} \pmod N = \prod_{j \subseteq \{ i \}} a^{2^i} \pmod N$$

I'm not a native English speaker please edit my question to be accurate.

Answer 1

It appears you may have entirely misunderstood or are not aware of several fundamental concepts of quantum computation, namely: superposition and quantum parallelism.

I will not try to explain how Shor's algorithm works because I'm certain any introductory book will do a better job. However, I highly recommend first understanding well the precursor algorithms such as the Deutsch algorithm, Deutsch-Jozsa algorithm and Simon's algorithm and only then start looking into Shor's algorithm. These algorithms are relatively simpler than Shor's algorithm and introduce necessary concepts.

Also, you might want to review your math equations as they don't make much sense.