= Linear congruence from a discrete-logarithm Fourier sample
{title2=$c_1y\equiv-c_2\pmod M$}
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\leq 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$.
Back to article page
