Order finding (exact)

Let $N\geq2$ and $x\geq0$ be integers with $\gcd(x,N)=1$, $r$ be the least positive integer satisfying $x^r\equiv1\pmod N$, $n=\lceil\log_2N\rceil$, and $q=2^t$ be a multiple of $r$ for an integer $t\geq1$. Given access to a $(t+n)$-qubit oracle $U_x$ such that $U_x\ket{a,y}=\ket{a,y\oplus(x^a\bmod N)}$, there exists a quantum algorithm that outputs an index $j=s(q/r)$ for some $s\in\{0,\ldots,r-1\}$ with probability one, using at most $t+n$ logical qubits, 1 query to $U_x$, $t(t-1)+3\lfloor t/2\rfloor$ CNOT gates, and $t(3t+1)/2$ single-qubit gates.