Period, Hidden-Shift, and Number-Theoretic Algorithms — Examples

Take $A=\mathbb{Z}\mathrm{/}4\mathbb{Z}$, shift $s=1$, and define injective maps $f(a)=a$ and $g(b)=b-1(\mathrm{m}\mathrm{o}\mathrm{d}4)$. Then $f(a)=g(a+1)$ for every $a$. With the generalized-dihedral product law and $H_1=⟨(1,1)⟩$, the left cosets are $C_0=\{(0,0),(1,1)\}$, $C_1=\{(1,0),(2,1)\}$, $C_2=\{(2,0),(3,1)\}$, and $C_3=\{(3,0),(0,1)\}$. The function $F(a,0)=f(a)$, $F(a,1)=g(a)$ takes the common value $a$ on $C_a$, so these are exactly its equal-value classes. In particular, right multiplication by $(1,1)$ pairs $(1,0)$ with $(2,1)$.

This convention uses left cosets: the right coset $H_1(1,0)$ is $\{(1,0),(0,1)\}$, whose two $F$-values are $1$ and $3$; it is not the hidden left coset $C_1$.

Work in the multiplicative group ${\mathbb{F}}_{31}^{\times }$ and let $g=9$. Its powers satisfy

$$9^2\equiv 19,9^3\equiv 16,9^4\equiv 20,9^5\equiv 25,9^{15}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}31)\mathrm{.}$$

Since the proper divisors of $15$ are $1,3,5$ and $9,16,25$ are all different from $1$ modulo $31$, $g$ has exact order $q=15$. Set $x=20=g^4$, so the discrete logarithm is $a=4$.

The cyclic DLP subgroup is $H=⟨(-4,1)⟩\le {\mathbb{Z}}_{15}^2$. The Fourier label $(c,d)=(2,8)$ lies in its annihilator because $d\equiv ac\equiv 4\cdot 2\equiv 8(\mathrm{m}\mathrm{o}\mathrm{d}15)$. Here $\gcd (2,15)=1$ and $2^{-1}\equiv 8(\mathrm{m}\mathrm{o}\mathrm{d}15)$, so the sample recovers

$$d{c}^{-1}\equiv 8\cdot 8\equiv 4(\mathrm{m}\mathrm{o}\mathrm{d}15)\mathrm{.}$$

Verification is direct: $9^4\equiv 20=x(\mathrm{m}\mathrm{o}\mathrm{d}31)$. Under the exact uniform annihilator sample law, this particular pair has probability $1\mathrm{/}15$.