Reversible modular multiplication by a unit

Input. An integer $N\ge 2$, $n=\lceil {\log }_{2}N\rceil$, a one-bit control $c$, an $n$-bit data register $z$, and integers $a,a^{-1}$ with $0\le a,a^{-1}<N$ and $a{a}^{-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)$. The data encoding is valid when its unsigned value is less than $N$.

Residue addition and multiplication are in $\mathbb{Z}\mathrm{/}N$ with the class operations of The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$, Addition and multiplication on $\mathbb{Z}\mathrm{/}n$ by $[a{]}_n+[b{]}_n=[a+b{]}_n$ and $[a{]}_n[b{]}_n=[ab{]}_n$, and For every natural $n$, $(\mathbb{Z}\mathrm{/}n,+)$ is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold. The inverse condition says $[a{]}_N$ is a unit, equivalently $\gcd (a,N)=1$ by The unit group $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ and Euler's totient $\phi (n)=\mid (\mathbb{Z}\mathrm{/}n{)}^{\times }\mid$ for $n\ge 1$ and For $n\ge 1$, $[a{]}_n$ is a unit if and only if $\gcd (a,n)=1$. Kets use Dirac Notation Conversion; $c,z$ are ordered computational-basis registers with the unsigned encoding of Finite registers and their ordered computational bases and Big-endian encoding of ordered bit strings, tensor order as in Ordered tensor registers, their inner product, and wire permutations, and circuit denotation as in Denotational semantics of a finite layered circuit. “Clean work” means initialized and returned to zero under Clean and dirty ancillas.

Output. A reversible circuit on $c,z$ and clean work registers which implements the controlled map $z\mapsto az<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ for $c=1$ and valid $z$, and is the identity on invalid encodings and when $c=0$.

Instructions. Define the total Boolean function on $(c,z)$ by $f_a(c,z)=\{\begin{array}{ll}az<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N,& c=1\text{ and }z<N,\\ z,& \text{otherwise.}\end{array}$ Generate the following explicit NOT/AND/OR DAG for this function. Bit arrays in the instructions below are indexed from least significant bit $0$; the input and output port lists retain the repository's most-significant-first register order. Begin with the distinct input identifiers $c,z_{n-1},\dots ,z_0$ and two constant nodes $0,1$. Every gate emission appends a fresh identifier in consecutive order, referencing only existing identifiers. A named bit below is an alias of its node identifier, never an additional gate. Expand every macro call immediately in the stated loop order.

1. Define $\mathrm{XOR}(u,v)$ by emitting, in order, $o=\mathrm{OR}(u,v)$, $h=\mathrm{AND}(u,v)$, $d=\mathrm{NOT}(h)$, and $e=\mathrm{AND}(o,d)$, returning $e$. Define ${\mathrm{ADD}}_w(U,V,d_0)$ by looping $i=0,\dots ,w-1$: emit $e_i=\mathrm{XOR}(U_i,V_i)$, $s_i=\mathrm{XOR}(e_i,d_i)$, $h_i=\mathrm{AND}(U_i,V_i)$, $j_i=\mathrm{AND}(e_i,d_i)$, and $d_{i+1}=\mathrm{OR}(h_i,j_i)$. Return $(s_0,\dots ,s_{w-1})$ and $d_w$. Define ${\mathrm{SUB}}_w(U,V)$ by first emitting $\mathrm{NOT}(V_i)$ in increasing $i$ and then calling ${\mathrm{ADD}}_w(U,\mathrm{NOT}(V),1)$; return its difference bits and carry bit $h$ (the no-borrow bit).
2. Define ${\mathrm{SELECT}}_w(h,U,V)$ by emitting $d=\mathrm{NOT}(h)$ and, for $i=0,\dots ,w-1$, $u_i=\mathrm{AND}(h,U_i)$, $v_i=\mathrm{AND}(d,V_i)$, $s_i=\mathrm{OR}(u_i,v_i)$. It returns the selected bit array $S$. Public constant arrays below refer to the shared $0,1$ nodes and are zero-padded to the displayed width.
3. Initialize a $2n$-bit accumulator $P$ with zero aliases. For $i=0,\dots ,n-1$, form a $2n$-bit row $H$: for $j=0,\dots ,n-1$, emit $H_{i+j}=\mathrm{AND}(a_i,z_j)$, where $a_i$ is the constant bit of $a$; all other row bits alias $0$. Replace $P$ by the sum output of ${\mathrm{ADD}}_{2n}(P,H,0)$, ignoring the carry output.
4. Initialize $R$ to $n$ zero aliases. For $\mathrm{\ell }=2n-1,\dots ,0$, form the $(n+1)$-bit array $V$ by $V_0=P_{\mathrm{\ell }}$ and $V_i=R_{i-1}$ for $1\le i\le n$. Call ${\mathrm{SUB}}_{n+1}(V,N)$, obtaining difference $D$ and carry $h$. Set $R$ to the low $n$ bits of ${\mathrm{SELECT}}_{n+1}(h,D,V)$.
5. Pad $z$ by a zero high bit, call ${\mathrm{SUB}}_{n+1}(z,N)$, and let $h$ be its carry. Emit $v=\mathrm{NOT}(h)$ and $g=\mathrm{AND}(c,v)$. Set $F={\mathrm{SELECT}}_n(g,R,z)$. The ordered output ports are $F_{n-1},\dots ,F_0$. This completes the finite DAG and its topological order. Construct a second DAG by the identical recipe with constant $a^{-1}$ in place of $a$.

Compile each DAG to the clean-target XOR oracle of Coherent XOR function oracle using Reversible embedding of a Boolean circuit, whose exact gate-emission rules apply also to repeated-source ports. Allocate an $n$-bit clean target, compute $f_a(c,z)$ into it, swap the data and target registers with three CNOT gates per bit, then apply the compiled XOR computation for $f_{a^{-1}}$ to the old-data target, using the new data as input. Each compiled XOR oracle is an involution by A total Boolean XOR oracle is unitary and involutive. Return the concatenated gate list with every compute-copy-uncompute stage included. Separate items thm-qa-modular-multiplication-circuit-correctness and thm-qa-modular-arithmetic-cost establish its basis action and gate/work bounds. No depth bound is part of this algorithm.