Finite cyclic discrete-log correctness, success and costs

By [F2], each sample is uniform on $H^{\perp }$. The bijection in [F3] makes $c$ uniform on ${\mathbb{Z}}_q$ and forces $d\equiv ac(\mathrm{m}\mathrm{o}\mathrm{d}q)$. Exactly $\phi (q)$ of the $q$ residues are units by [F4], so the probability of a unit is $\phi (q)\mathrm{/}q$.

If $c$ is a unit, [F5] supplies $c^{-1}$ modulo $q$. Then $d{c}^{-1}\equiv ac{c}^{-1}\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}q)$. The algorithm returns only after testing $g^{\tilde{a}}=x$, so every returned residue is the required exponent; rejecting a failed equality cannot produce an incorrect output.

Since $L\ge 1$, $D\le {\log }_2(1\mathrm{/}\delta )+1<2\ln (1\mathrm{/}\delta )+1$, so $t=(1+L)D\le 4L(1+\ln (1\mathrm{/}\delta ))$. Each sample calls the finite-abelian sampler once, which uses one direct $f$ query by [F1], so this bounds direct function queries. By [F7], one explicit $f$ evaluation uses $O(L)$ controlled group multiplications. Binary repeated squaring computes the verification power with at most $2L$ ordinary multiplications: square successive powers of $g$ and multiply the accumulator by each power whose exponent bit is one; [F8] proves the resulting accumulator is $g^{\tilde{a}}$. The constant precomputation takes $O(L)$ further group operations once. Thus the explicit-$f$ implementation uses $O(L^2(1+\ln (1\mathrm{/}\delta )))$ group-operation queries; with a direct $f$ oracle, step 1.2 shows that the first unit-coordinate sample verifies and terminates. Hence verification occurs at most once and needs $O(L)$ classical group multiplications, which also satisfies the stated looser $O(L(1+\ln (1\mathrm{/}\delta )))$ bound.

Put $p=\phi (q)\mathrm{/}q$. Extend the independent sample list to $t$ draws for this probability calculation, even when the procedure stops earlier. The probability that all $t$ independent samples have nonunit first coordinate is $(1-p{)}^t\le e^{-pt}$. By [F4], $p\ge (1+{\log }_{2}q{)}^{-1}$. Since $D\ge {\log }_2(1\mathrm{/}\delta )>\ln (1\mathrm{/}\delta )$, we have $t=(1+L)D\ge (1+{\log }_{2}q)\ln (1\mathrm{/}\delta )$. Therefore $pt\ge \ln (1\mathrm{/}\delta )$ and $(1-p{)}^t\le \delta$. Whenever at least one sample has a unit coordinate, step 1.2 returns $a$; hence success probability is at least $1-\delta$.

In the explicit circuit profile, each sample's full XOR function evaluation and verification use $O(L{C}_G+w)$ gates, while the supplied uniform preparation and product QFT use $O(L^2)$ ideal gates. The modular inverse on $O(L)$-bit residues uses $O(L^3)$ bit operations by [F5], and each classical group operation uses at most $T_G$ bits. Multiplying these per-sample costs by $t=O(L(1+\ln (1\mathrm{/}\delta )))$ gives the sampling, arithmetic and verification terms in the displayed bounds. In the direct-$f$-oracle profile, verification and inverse steps have $O(L{T}_G+L^3)$ bit work per sample, while one $f$ query costs one query and has no implicit gate bound. Precomputation contributes only $O(L{T}_G)$ additional bit operations and is absorbed because $L\ge 1$ and $1+\ln (1\mathrm{/}\delta )\ge 1$.

To compute $D$, compare $2^{d}p$ with $v$ for successive $d$ until the first successful comparison. Since $p\ge 1$ and $v<2^K$, $D\le K$; all tested integers have $O(K)$ bits. Binary shifts and comparisons therefore cost $O(K^2)$ in total. Computing $L$ from $q-1$ and multiplying $(1+L)D$ cost at most $O((L+K{)}^2)$ by schoolbook arithmetic, absorbed by $O(K^2+L^4)$ since $L\ge 1$. Adding this preprocessing gives the stated classical bit bound. The access coordinates remain separate by [F6].