Discrete-logarithm Fourier sampling ($c_2\equiv -y{c}_1(\mathrm{mod}M)$)

For a generator of a group $g$ of order $M$ and $x=g^y$, the function $f(a,b)=g^a{x}^{-b}$ hides the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$ of ${\mathbb{Z}}_M^2$. Each fiber is an affine coset $\{(yb+k,b):b\in {\mathbb{Z}}_M\}$. Measuring the function register gives its normalized coset state. Applying the positive-exponent quantum Fourier transform to both input registers gives amplitudeThe finite geometric series vanishes off $c_2=-y{c}_1$ and equals $M$ on that line. Thus each allowed output pair has probability $1/M$, independently of the coset offset. If $\gcd (c_1,M)=1$, a modular inverse recovers $y=-c_2{c}_1^{-1}$.

Let $d=\gcd (c_1,M)$. A supported sample guarantees $d\mid c_2$. Dividing its linear congruence by $d$ gives an invertible coefficient modulo $M/d$ and a unique residue $y_0$ there. The $d$ compatible discrete logarithms modulo $M$ are $y_0+jM/d$ for $0\le j<d$. Only $d=1$ determines the discrete logarithm from the sample alone; $(c_1,c_2)=(0,0)$ conveys no information for $M>1$.