Constructing supersingular elliptic curves with a given endomorphism ring (Q2878828)

The authors consider two computational problems related to supersingular elliptic curves defined over prime fields \(\mathbb{F}_p\) and their endomorphism rings. The first is: given a maximal order \(\mathcal{O}\) in the quaternion algebra \(B_p\) over \(\mathbb{Q}\) ramified at \(p\) and \(\infty,\) construct a supersingular elliptic curve \(E\) over \(\mathbb{F}_p\) such that \(\mathrm{End}(E) \cong \mathcal{O}.\) The second is: given a prime \(p,\) find for each distinct maximal order type \(\mathcal{O}_i\) of \(B_p\) the minimal polynomial of the supersingular \(j\)-invariant with endomorphism rign \(\mathcal{O}_i.\) Novel algorithms are given for both problems with running time \(O(p^{1 + \varepsilon})\) and \(O(p^{2.5 + \varepsilon})\) respectively, in both cases improving previous results.