§6, eq. (6.17) — each good state is observed with probability at least $1/(20q^2)$

Throughout, $p$ is a prime, $g$ is a generator of the multiplicative group $(\mathbb Z/p\mathbb Z)^\times$ (an element of order $p-1$), $r$ is an integer with $0\le r<p-1$ and $x=g^r$ (so $r$ is the discrete logarithm of $x$), and $q=2^l$ is a power of $2$ with $p<q<2p$.

Let $0\le c,d<q$ be such that $(c,d)$ is good, i.e. satisfies conditions (6.10) and (6.11), and let $y$ be any nonzero residue modulo $p$. Then the probability of observing $|c,d,y\rangle$ when the final state (6.3) is measured satisfies

This per-state lower bound, combined with a count of good pairs, gives the constant success probability of the algorithm.

Formalization Note The paper derives the bound from the integral approximation (6.16), whose error term $O(W/(pq))$ has an unspecified constant, and then states $1/(20q^2)$ without a threshold on $p$. The statement here is the page's unconditional claim, for every prime $p$.