On $E: y^2 \equiv x^3 + 3x + 7 \pmod{31}$ the group is cyclic with $|E| = 22$ and $P$ is a generator. You know $3P = Q(12; 2)$ and $15P = R(16; 11)$. Compute $S = 33P$, give the smallest $t$ with $S = tP$, find $-R$, and list the possible point orders with their counts.

Question

Accepted Answer

$33P = 2R + Q = (8; 27) + (12; 2) = (21; 0)$. Since $33 \equiv 11 \pmod{22}$, $S = 11P$. $-R = (16; 20)$. Orders 1, 2, 11, 22 occur 1, 1, 10, 10 times.
1. Split the scalar into known multiples: $33 = 2 \cdot 15 + 3$, so $33P = 2R + Q$.
2. Double $R = (16; 11)$: $\lambda = \dfrac{3 \cdot 16^2 + 3}{2 \cdot 11} = \dfrac{771}{22} \equiv 27 \cdot 22^{-1} \equiv 27 \cdot 24 \equiv 28$.
$x_3 = 28^2 - 16 - 16 \equiv 8$, $y_3 = 28(16 - 8) - 11 \equiv 27$, so $2R = (8; 27)$.
3. Add $Q = (12; 2)$: $\lambda = \dfrac{27 - 2}{8 - 12} = \dfrac{25}{-4} \equiv 6 \cdot 4^{-1} \equiv 6 \cdot 8 \equiv 17$.
$x_3 = 17^2 - 8 - 12 \equiv 21$, $y_3 = 17(8 - 21) - 27 \equiv 0$, so $33P = (21; 0)$.
4. Reduce the scalar mod the group order: $22P = \mathcal{O}$, so $33P = (33 \bmod 22)P = 11P$; the smallest $t$ is 11.
5. Negation: $-(x; y) = (x; -y)$, so $-R = (16; -11) = (16; 20)$.
6. Point orders: every order divides 22. In a cyclic group of order 22 there are $\varphi(d)$ points of each order $d$: $\varphi(22) = 10$ generators, $\varphi(11) = 10$ points of order 11, $\varphi(2) = 1$ point of order 2, and $\varphi(1) = 1$, namely $\mathcal{O}$. Check: $10 + 10 + 1 + 1 = 22$.
Sanity check: $(21; 0)$ has $y = 0$, so it equals its own negative and has order 2. That matches $11P$, whose order is $22 / \gcd(11, 22) = 2$.