§6, p. 1504 — the discrete-log circuit gives a good output with probability at least $1/480$

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$.

Run Shor's discrete-logarithm circuit: prepare the state

apply the Fourier transform $A_q$ (entries $q^{-1/2}e^{2\pi i ac/q}$) to each of the first two registers, and measure all three registers, obtaining $|c,d,y\rangle$. The output is good if $(c,d)$ satisfies (6.10) $|\{T\}_q|\le\frac12$ with $T=rc+d-\frac{r}{p-1}\{c(p-1)\}_q$, and (6.11) $|\{c(p-1)\}_q|\le q/12$. Then

This constant success probability is what makes the quantum discrete-logarithm algorithm run in expected polynomial time: from a few good outputs the discrete logarithm $r$ can be deduced.

Formalization Note The paper states the intermediate bound "at least $p/(240q)$"; its own count gives $(p-1)/(240q)$, which still yields $1/480$ because $q$ and $2p$ are both even, so $q<2p$ forces $q\le2(p-1)$. Only $1/480$ is stated. The state preparation by testing and restarting is not formalized; the state (6.1) is taken as given.