  Shor's algorithm, which was proposed by Peter Shor [Proceedings of the 35th
Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134], is
considered as one of the most significant quantum algorithms. Shor's algorithm
can factor large integers with a certain probability of success in polynomial
time. However, Shor's algorithm requires an unbearable amount of qubits and
circuit depth in the NISQ (Noisy Intermediate-scale Quantum) era. To reduce the
resources required for Shor's algorithm, we propose a new distributed
quantum-classical hybrid order-finding algorithm for Shor's algorithm. The
traditional order-finding algorithm needs to obtain an estimation of some
$\dfrac{s}{r}$, where $r$ is the ``order'' and $s\in\{0,1,\cdots,r-1\}$. In our
distributed algorithm, we use $k$ computers to estimate partial bits of
$\dfrac{s}{r}$ separately. In order to reduce the errors of measuring results
of these computers, we use classical programs to correct the measuring results
of each computer to a certain extent. Compared with the traditional Shor's
algorithm, our algorithm reduces nearly $(1-\dfrac{1}{k})L-\log_2k$ qubits for
each computer when factoring an $L$-bit integer. Also, our algorithm reduces
gate complexity and circuit depth to some extent for each computer. The
communication complexity of our algorithm is $O(kL)$.
