I'm studing the paper "ON THE COST OF COMPUTING ISOGENIES BETWEEN SUPERSINGULAR ELLIPTIC CURVES" (link) and, at some point, autors say that (assuming $e$ even):
the number of order-$\ell^{e/2}$ subgroups of $E[\ell^e]$ is $N=(\ell+1)\ell^{e/2 - 1}.$
Here $E$ is an elliptic curve on $\mathbb{F}_q,$ $q = p^n$ with $p$ prime and $\ell$ is another prime diffrent from $p$. $E[\ell^{e}]$ is the set of $\ell^e-$torsion points of the elliptic curve $E$.
Can someone help me to understand why the number of order-$\ell^{e/2}$ subgroups of $E[\ell^e]$ is $N=(\ell+1)\ell^{e/2 - 1}$?
I know that $E[\ell^{e}] \simeq \mathbb{Z}/\ell^e \mathbb{Z}\times \mathbb{Z}/\ell^e \mathbb{Z}$ so i think that the problem is equivalent to counting order-$\ell^{e/2}$ subgroups of $\mathbb{Z}/\ell^e \mathbb{Z}\times \mathbb{Z}/\ell^e \mathbb{Z}.$ But
- I'm unable to do it;
- I'm not convinced I'm on the right way.
Any help will be appreciated
It is the number of cyclic subgroups.
If $c\le e$ then any subgroup of order $\ell^c$ in $E[\ell^e]$ will be contained in $E[\ell^c]$. The number of elements of order $\ell^c$ in $\Bbb{Z}/\ell^c\Bbb{Z}\times\Bbb{Z}/\ell^c\Bbb{Z}$ is $\ell^{2c}-\ell^{2(c-1)}$ (elements $(a,b)$ with $\ell\nmid a$ or $\ell \nmid b$). Then divide by $\ell^{c-1}(\ell-1)$ (the number of elements generating the same subgroup) to get $\ell^{c-1}(\ell+1)$ for the number of cyclic subgroups of order $\ell^c$.