Pairings for Beginners: Pohlig–Hellman attack time complexity

Question

I'm reading Pairings for beginners by Craig Costello.

I'm trying to understand this example of (what I think) is the Pohlig–Hellman algorithim (on page 31 of the book).

Consider $E/\mathbb{F}_{1021}\,:\,y^2=x^3+905x+100$ with group order $\#E(\mathbb{F}_q)=966=2\cdot3\cdot7\cdot23$ and generator $P = (1006,416)$. We are given $Q = (612,827)$ and we seek to find $k$ such that $[k]P = Q$. Rather than seeking $i$ in the full group $(2 \leq i \leq 965)$, we can map the instance into each prime order subgroup by multiplying by the appropriate cofactor, and then solve for $k_j = k\, \text{mod}\,j, j \in \{2,3,7,23\}$. For $j =2$, we have $P_j = P_2 = [966/2]P = [483](1006,416) = (174, 0)$ and $Q_j = Q_2 = [483](612,827) = (174, 0)$ so $Q_2 = [k_2]P_2$ gives $k_2 = 1$.

He then gives the values for $k_2$, $k_3$, etc.

For $k_{23}$, he says

For $Q_{23} = [k_{23}]P_{23}$ we exhaust $k_{23} \in \{1, ..., 22\}$ to see that $k_{23} = 20$.

I'm not sure if this is just a typo, or if I'm mis-understanding something more fundamental. If $k_{23} = 20$ then, he did not exhaust $\{1, ..., 22\}$, he exhausted $\{1, ....,20\}$. He repeats this same thing elsewhere, so I figured it wasn't a typo and I've been left feeling a little confused.

Anyone have an explanation?

Answer 1

I'm not sure if this is just a typo, or if I'm mis-understanding something more fundamental. If $k_{23} = 20$ then, he did not exhaust $\{1, ..., 22\}$, he exhausted $\{1, ....,20\}$. He repeats this same thing elsewhere, so I figured it wasn't a typo and I've been left feeling a little confused.

What he means is, trying all the elements in the set $\{1, ..., 22\}$ exhaustively is guaranteed to find $k_{23}$. It happens that he found it after 20, and didn't have to test 21 or 22 (assuming he started testing from 1). In another universe, he could have found $k_{23} = 5$ and stopped there. But regardless of the true value, the approach is still to exhaust the set $\{1, ..., 22\}$.