Reversible circuits for modular multiplication Cx%M with x < M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific C and M values. In this paper, the authors develop such optimizations in a bottom-up fashion, starting with most convenient C values. When zero-initialized ancilla registers are available, they reduce the search for compact circuits to a shortest-path problem.
Search to explore resources
