= Solution
First require $x\neq0$. A <discrete logarithm> to a <generator of a group> of $\mathbb Z_p^*$ exists only for nonzero $x$; the printed membership $x\in\mathbb Z_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any <quantum circuit>.
Put $M=p-1$ and write $x=g^y$. Since $g$ is a <generator of a group> of order $M$, the map $k\mapsto g^k$ is a <bijection> from $\mathbb Z_M$ to the <multiplicative group of a finite field>. Hence every nonzero $c$ has a unique $k\in\mathbb Z_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, giving
$$
\boxed{f(a,b)=g^{a-by}=c\ \Longleftrightarrow\ a-by\equiv k\pmod M.}
$$
The <fiber> over $c$ is an affine <coset> of the <subgroup> $\{(yb,b):b\in\mathbb Z_M\}$, and contains exactly $M$ pairs. This identifies the <hidden subgroup problem> underlying <discrete-logarithm Fourier sampling>; knowing $k$ numerically is not needed to construct the <coset state>.
Back to article page
