Gate and bit cost of modular multiplication and powering

In the explicit DAG of [F2], XOR emits four nodes, each adder bit emits two XORs and three carry nodes, hence $11$ nodes, and subtraction emits one additional NOT per bit, hence $12w$ nodes at width $w$. Selection emits $1+3w$ nodes. The product uses $n^2$ partial-product AND nodes and $n$ adders of width $2n$, totaling $23n^2$ nodes. Its $2n$ remainder stages use $2n(12(n+1)+1+3(n+1))$ nodes. The final comparison uses $12(n+1)$ nodes, validity/control uses two more, final selection uses $1+3n$, and the two shared constant nodes complete the count. Thus $S\le 100(n+1{)}^2$ suffices for all $n\ge 1$; every gate has at most two input ports, so $E\le 2S$. The correctness supplier in [F2] proves that the row sums never overflow and that each remainder stage needs only one conditional subtraction; these are exactly the loops just counted.

For the inverse computation, initialize $(R,S,U,V)=(N,x,0,1)$ and, while $S>0$, divide $R=qS+r$ with $0\le r<S$, set $h=(U-qV)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ to its least residue, and simultaneously update $(R,S,U,V)$ to $(S,r,V,h)$. Initially $R\equiv Ux$ and $S\equiv Vx(\mathrm{m}\mathrm{o}\mathrm{d}N)$; these two congruences are preserved because $r=R-qS\equiv (U-qV)x\equiv hx(\mathrm{m}\mathrm{o}\mathrm{d}N)$ by [F5]. The remainder pair is exactly the Euclidean descent in [F4], so it terminates at $(R,S)=(\gcd (N,x),0)=(1,0)$ by [F6]. The invariant then gives $Ux\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)$, and [F7] gives the returned inverse constant $b_0=U\in [0,N)$. For its cost, at every division $0<S<R\le N$; the new remainder is $r<R\mathrm{/}2$: if $S\le R\mathrm{/}2$, then $r<S\le R\mathrm{/}2$, while if $S>R\mathrm{/}2$, then $q=1$ and $r=R-S<R\mathrm{/}2$. Thus every two successive positive remainder values shrink by at least a factor of two, giving $O(n)$ iterations. The quotients and remainders have $O(n)$ bits, and $U,V$ always lie in $[0,N)$, so the signed intermediate $U-qV$ has $O(n)$ bits as well (its magnitude is at most $N^2+N$). Schoolbook division, multiplication, subtraction and reduction each take $O(n^2)$ multitape transitions, including signed reduction by dividing the absolute value and, when needed, replacing a nonzero remainder $d$ by $N-d$. Hence this explicit loop costs $O(n^3)$ transitions. Set $a_0=x$, and for the remaining $O(n)$ powers compute $a_{j+1}=a_j^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$ and $b_{j+1}=b_j^2<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N$. Induction gives $a_j\equiv x^{2^j}$ and $a_j{b}_j\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}N)$; each stage uses two $O(n^2)$ schoolbook modular products, so all powers and inverses still cost $O(n^3)$ transitions.

Step 1.1 counts the complete Boolean function DAG, including the validity comparison, control, and conditional output, and gives $S,E=O(n^2)$. Apply [F1] separately to the forward and inverse functions; the two compiled XOR maps and their clean work each cost $O(n^2)$. The swap uses $3n$ CNOT gates. Adding these counts proves the claimed $O(n^2)$ gate and clean-work bounds; [F2] ensures they implement the required map.

The resource definition [F3] keeps gate count, classical bit transitions, and oracle queries separate. The preceding counts establish only gate/work and stated classical arithmetic bounds; no circuit layering or depth estimate follows from them.