Why do we get a connected 2-regular graph?

Question

In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ form a "branchless cycle".

For some context,

• $U$ is a set of elliptic curves, each one being a uniquely determined by a $j$-invariant.
• $l$ is a prime such that the Kronecker symbol $\left(\frac{D_\pi}{l}\right)=1$, and $D_\pi$ is the Frobenius discriminant (which is common among all the elliptic curves in $U$ because they are all isogenous by Tate's theorem).

Kohel (Theorem 2 in paper) showed that if an elliptic curve has $D_\pi$ and $l$ satisfying $\left(\frac{D_\pi}{l}\right)=1$, then there are exactly two $l$-degree isogenies from $E$.

Now this implies $U$ is $2$-regular, but why does the following statement hold:

It is practically determined that, when #U is prime, all the elements of U form a single isogeny cycle.

If $\#U=7$ can't we have two disjoint cycles of size $3$ and $4$? And why must $\#U$ be prime? A reference and/or an explanation would be appreciated.

Cross-post: https://math.stackexchange.com/questions/4882120/why-do-we-get-a-connected-2-regular-graph

Answer 1

The construction makes $U$ the Cayley graph associated to an abelian group $G$ and a pair $\pm g$ of elements of $G$.(*) In such a graph all the components are cycles of the same length, namely the order of $g$, call it $|g|$. Thus $|g|$ is a factor of $|G|$ (this is also part of Lagrange's theorem). In particular if $|G|$ is prime and $g$ is not the identity element then $|g| = |G|$ and the graph is a single $|G|$-cycle.

(*) More precisely, or at least more canonically, $U$ is not an abelian group but a "principal homogeneous space" for $G$; once we choose some curve $E_0 \in U$, we can identify $U$ with $G$.

The identification is as follows. Let $O_D$ be the imaginary quadratic order of discriminant $D = D_\pi$; then $G$ is the class group of $O_D$: every curve in $U$ is $E_0/I$ for some invertible ideal $I$ of $O_D$, with $E_0/I \cong E_0/I'$ iff $I,I'$ are in the same ideal class.

By the hypothesis on the prime $l$, it factors $(l) = \lambda \bar\lambda$ for some ideal $\lambda$ of $O_D$. The two $l$-isogenous curves are $E/\lambda$ and $E/\bar\lambda$. The classes of $\lambda$ and $\bar\lambda$ in $G$ are the elements $\pm g$ that connect adjacent vertices in the Cayley graph.

All this assumes that $g \neq -g$. It is possible for $g$ to be trivial or an element of order 2. In the former case, $U$ consists of $|G|$ loops, and thus is disconnected unless $G$, too, is trivial. In the latter case, $U$ is the union of $\frac12|G|$ two-cycles (double edges), though of course this cannot happen for $|G|$ prime unless $|G|=2$ in which case we still get a connected (multi)graph.