Finding cyclic subgroups of points on elliptic curves for isogeny based cryptography

Question

Isogeny based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is a theorem:

Elliptic curves are isogenous over $F_p$ if and only if they have equal number of points.

Recently, isogeny based public key methods are widely used in articles. This methods are implemented in computer systems in milliseconds and in android systems in seconds. This show that in future we can use such post-quantum cryptographic systems in practical world.

In programs such as Sage, we can find $l$-isogeny with subgroup of order $l$, but in several times our defined curve have not any subgroup with order $l$. My question is:

How can we find cyclic subgroup of order $l$ of the elliptic curve $E(\overline{\mathbf F_p})$, over the algebraic closure of the finite field?

I will be so thankful for any helpful comments and answers.

Answer 1

The $x$ coordinates of the $l$-torsion points are the roots of the $l$ division polynomial. Any cyclic subgroup of order $l$ is generated by a single point of order $l$. In practice only $\mathbb{F}_{p^2}$ rational points are used. See for instance https://eprint.iacr.org/2011/506.pdf.