# I have question about cost of 'modular multiplication unitary' in Shor's algorithm

Here modular multiplication unitary means $$U_a : |s\rangle \to|as\mod N\rangle$$.

My main question is, can the modular multiplication unitary $$U_a$$ can be constructed in time polynomial in the number of qubits $$n$$ for any $$a$$ and $$N$$? Or is this an open question? I cannot find a method or proof of implementing modular multiplication unitary fast.

In fact, the more relevant question is how to efficiently implement $$U_a^k$$ for any integer $$k$$: it's not good enough to implement $$U_a$$ $$k$$ times. But, again, this can be done classically and therefore you can implement the same thing on a quantum computer. Other questions on this site have asked that before if you want detail.