Appendix D: Solutions for Chapter 22

This page collects solutions and editorial notes for the exercises in Chapter 22: Isogenies for programmers. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

The fuller versions of these routines are in the isogenies package under solutions/ch22-isogenies. From a clone of the companion repository, pytest tests/ch22 runs its suite. Appendix C has the setup.

Exercise 1

Solving $x(x^2 + 1) = 0 \bmod 431$: $x = 0$ is one root. $x^2 + 1 \equiv 0$ requires $-1$ to be a QR mod 431. Compute $(-1)^{(431-1)/2} = (-1)^{215} = -1$, so $-1$ is a non-residue mod 431, and $x^2 + 1$ has no roots in $\mathbb{F}_{431}$. The only 2-torsion point in $\mathbb{F}_{431}$ is $(0, 0)$, plus the point at infinity, total of 2 elements.

Every element of $\mathbb{F}_p$ is a square in $\mathbb{F}_{p^2}$, because $\mathbb{F}_p^\times$ has order $p - 1$ and $(p^2 - 1)/2 = (p-1)\cdot(p+1)/2$ is a multiple of it, so $z^{(p^2-1)/2} = 1$ for every $z \in \mathbb{F}_p^\times$. In particular $-1$ acquires a square root $i$ in $\mathbb{F}_{431^2}$, and $x^2 + 1$ splits there. Note what this argument does and does not say: it is a statement about the elements of $\mathbb{F}_p$, not about $\mathbb{F}_{p^2}$, where as in any finite field of odd characteristic exactly half the nonzero elements are squares.

The 2-torsion group of any elliptic curve in characteristic $\neq 2$ is $\mathbb{Z}/2 \times \mathbb{Z}/2$ (Klein four-group) over the algebraic closure, with 4 points: identity, $(0, 0)$, $(i, 0)$, $(-i, 0)$. All four already have coordinates in $\mathbb{F}_{431^2}$, so $E_0(\mathbb{F}_{431^2})[2]$ has 4 points.

roots = [x for x in range(431) if (x ** 3 + x) % 431 == 0]
print(roots)
# ==> [0]

Exercise 2

The supersingular 3-isogeny graph at $p = 431$ has 37 vertices (one per supersingular j-invariant in $\mathbb{F}_{p^2}$, by the formula $\lfloor p / 12 \rfloor + \varepsilon$). Each vertex has degree 4 (the four cyclic subgroups of order 3 in $E[3]$), so a random walk of 4 steps has $4^4 = 256$ possible sequences across 37 vertices.

A birthday bound is the wrong instrument here, and it gives the wrong answer. It would put the expected first revisit near $\sqrt{37} \approx 6$ steps and so call a 4-step revisit unlikely. In fact a revisit is more likely than not, and the reason has nothing to do with birthdays: it is backtracking. For a degree-3 isogeny $\phi: E \to E'$, the dual $\hat{\phi}: E' \to E$ has kernel one of the four order-3 subgroups of $E'$. A walk that picks uniformly among the four therefore steps straight back to where it came from with probability $1/4$, at each of steps 2, 3 and 4. The chance of avoiding that three times running is $(3/4)^3 = 27/64 \approx 42\%$.

Enumerating all $4^4 = 256$ walks confirms it, and shows the model is exact where it should be. The count of walks whose j-invariants are all distinct is 4 of 4 after one step, then $12/16 = 3/4$, then $36/64 = (3/4)^2$, then $104/256 \approx 40.6\%$. Steps 2 and 3 match $(3/4)^{k-1}$ exactly, because backtracking is the only way to collide that early. Step 4 falls just below the predicted $(3/4)^3 \cdot 256 = 108$ walks, and the missing 4 walks are the first genuine collisions: 4-cycles that return to a visited vertex without ever reversing an edge.

So the answer to the exercise is yes, usually: 152 of the 256 walks revisit a j-invariant within 4 steps, and only 104 produce 5 distinct ones. A reader whose implementation makes canonical rather than uniform kernel choices will see one particular walk from that distribution.

Exercise 3

$431 \bmod 12 = 11$ (since $432 = 36 \cdot 12$ so $431 = 12 \cdot 35 + 11$). Then $\lfloor 431 / 12 \rfloor + 2 = 35 + 2 = 37$ supersingular j-invariants over $\mathbb{F}_{431^2}$.

The 3-isogeny graph at $p = 431$ is connected (Pizer’s expander result), so enumerating reachable j-invariants from $j = 1728$ via repeated 3-isogenies eventually visits all 37 vertices. Running that search, the frontier sizes are 1, 2, 6, 12, 10, 6: the last vertex is reached at depth 5, not at the $\log_4 37 \approx 2.6$ a branching-factor-4 tree would suggest.

Two things break the tree estimate, and the first is the chapter’s own Figure 22.1. The starting vertex $j = 1728$ has extra automorphisms, and its four order-3 kernels reach only two distinct neighbours: $j = 102$ and $j = 319$, each twice. That is the same degeneracy the figure draws at degree 2, where three order-2 kernels reach only $j = 4$ and $j = 19$. So level 1 holds 2 vertices where the estimate assumes 4. From then on, backtracking and short cycles keep the frontier well below $4^d$. Being a Ramanujan graph bounds the diameter logarithmically, which is why 5 and not 20; it does not make the graph a tree.

print(431 % 12, 431 // 12 + 2)
# ==> 11 37

Exercise 4

The Castryck-Decru attack against SIDH exploits the auxiliary torsion-point images that SIDH publishes as part of its key exchange: feeding those images into Kani’s lemma on isogenies between products of elliptic curves recovers the secret isogeny in classical polynomial time, heuristically and with the endomorphism ring of the starting curve known in Castryck and Decru’s analysis, and without heuristics or that condition in Robert’s. CSIDH does not publish any torsion-point images. The public key is just the destination supersingular curve reached by a class-group action, given as the Montgomery coefficient $A$ of $E_A : y^2 = x^3 + A x^2 + x$ over $\mathbb{F}_p$ (Castryck et al., 2018, sec. 6). That coefficient names the curve’s $\mathbb{F}_p$-isomorphism class, which is what the action moves between; a j-invariant would not, because it does not separate a curve from its quadratic twist over $\mathbb{F}_p$ (the chapter’s j-invariant section). Either representation carries no auxiliary structure to feed into Kani’s lemma. The attack therefore has no foothold against CSIDH, though CSIDH faces its own quantum threat: recovering the secret is an abelian hidden-shift problem over the class group. Such a problem reduces to a dihedral hidden-subgroup problem, and the best known quantum algorithms for it run in sub-exponential time (Castryck et al., 2018, sec. 7.2).

Exercise 5

$2^5 \cdot 3^3 = 32 \cdot 27 = 864$, so $p' = 863$. Trial division: $863$ is not divisible by 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 (all primes up to $\sqrt{863} \approx 29.4$). So 863 is prime.

In SIDH-style chains at this prime, Alice walks the 2-isogeny graph and Bob walks the 3-isogeny graph. The chain length is the exponent of the corresponding prime in the smooth $p + 1$. Alice’s chain: $5$ steps (since $2^5$ is the 2-part). Bob’s chain: $3$ steps ($3^3$ is the 3-part). The asymmetry is intentional in SIDH. Both parties walk to depth that exhausts their respective torsion.

def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(n ** 0.5) + 1))


print(is_prime(863), 32 * 27)
# ==> True 864

References

Castryck, W., Lange, T., Martindale, C., Panny, L., & Renes, J. (2018). CSIDH: An efficient post-quantum commutative group action. Advances in Cryptology – ASIACRYPT 2018, Part III, 11274, 395–427. https://doi.org/10.1007/978-3-030-03332-3_15