The Exercise

The discrete logarithm problem gives an element $a$ of order $r$ and a power $b = a^s$ , and asks for the exponent $s$ , with $0 \le s < r$ . The quantum algorithm for it ends by measuring two registers, which yields, for some integer $\ell$ , two real numbers $\varphi_1$ and $\varphi_2$ estimating $s\ell/r$ and $\ell/r$ modulo one. The exercise is the classical step that follows, finding $s$ from $\varphi_1$ , $\varphi_2$ and $r$ by continued fractions.

Recovering the Exponent

For a rational number $q$ and a modulus $r$ , the numerator recovered from $q$ is the integer $k_r(q) = \operatorname{num}(qr),$ (1)^✦ where $\operatorname{num}(x)$ is the numerator of a rational number $x$ in lowest terms.

The discrete logarithm recovered from rational numbers $q_1$ and $q_2$ , with modulus $r$ , is the residue modulo $r$ , between $0$ and $r - 1$ , $\tilde s_r(q_1, q_2) = k_r(q_1)\, k_r(q_2)^{-1} \bmod r,$ (2)^✦ with $k_r(q_2)^{-1}$ the inverse of $k_r(q_2)$ modulo $r$ .

The Claim

A real number $\varphi$ with continued fraction expansion $[a_0; a_1, a_2, \dots]$ has, for each $n$ , an $n$ th convergent, the rational number $c_n(\varphi) = [a_0; a_1, \dots, a_n]$ .

Theorem 1. Let $r$ be a positive integer, $s$ an integer with $0 \le s < r$ , and $\ell$ an integer coprime to $r$ ; let $k_1 = s\ell \bmod r$ and $k_2 = \ell \bmod r$ , both between $0$ and $r - 1$ . Let $\varphi_1$ and $\varphi_2$ be real numbers with $|\varphi_1 - k_1/r| < 1/(2r^2)$ and $|\varphi_2 - k_2/r| < 1/(2r^2)$ . Then there are indices $n_1$ and $n_2$ with $c_{n_1}(\varphi_1) = \frac{k_1}{r}, \qquad c_{n_2}(\varphi_2) = \frac{k_2}{r}, \qquad \tilde s_r\!\left(\frac{k_1}{r}, \frac{k_2}{r}\right) = s.$ (3)^✦

What Is Checked

The claim is stated over the numerator recovery $k_r$ of (1) and the recovered discrete logarithm $\tilde s_r$ of (2), evaluated at the exact fractions $k_1/r$ and $k_2/r$ , and over the convergents of the continued fractions of the two estimates.