# How to implement modular exponentiation efficiently in Shor's algorithm?

I'm a noob in quantum computing and I'm trying to get Shor's algorithm working on Q# (the language is unrelated). However, I'm stuck on computing $$f(x)$$s in the quantum circuit. Let $$N\sim \log_2(n)$$ be the number of qubits needed for finding the period. As far as I know, we can initialize $$s=1$$, and multiply it with $$a,a^2,a^4 \cdots a^{2^{N-1}} \mod n$$ according to the $$N$$ control qubits. However, all methods I can think of needs around $$O(N^2)$$ modulus and thus $$O(N^2)$$ ancillary clean qubits (for example, compute $$a,a^2,a^4 \cdots a^{2^{N-1}}\mod n$$ beforehand, use additions, comparing numbers and subtracting accordingly). Is there a way to implement modulus as some reversible circuit? Or, am I all wrong?