= Solution
The <quantum Fourier transform> measurement supplies a rational approximation
$$
\frac{c}{2^m}\simeq\frac{s}{r},
$$
where $r$ is the desired <multiplicative order>. Here
$$
\frac{c}{2^m}=\frac{256}{512}=\frac12.
$$
Its reduced <continued fraction convergent> has denominator two, so <continued-fraction recovery in quantum order finding> proposes $r=2$. Direct <order verification from divisors> confirms it:
$$
8^2=64\equiv1\pmod{21},
\qquad
8\not\equiv1\pmod{21}.
$$
Hence
$$
\boxed{\operatorname{ord}_{21}(8)=2.}
$$
As a check, the classical final step of the <Shor algorithm> gives
$$
\boxed{\gcd(8-1,21)=7,
\qquad
\gcd(8+1,21)=3.}
$$
Back to article page
