Let $p≠2,3$ be a prime, and $\mathbb{F}_p$ the finite field with $p$ elements. We will use the following notation: - $ℓ,ℓ_0,ℓ_1$ are primes bounded by $\DeclareMathOperator{\poly}{poly}\poly(\log p)$. - $m,n$ are $\poly(\log p)$-smooth integers bounded by $\poly(p)$, with $m∧n=1$. - $E, E_0, E_1, \dots$ are supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. - $j(E)$ is the $j$-invariant of $E$. - $\DeclareMathOperator{\End}{End}\End(E)$ is the endomorphism ring of $E$. - $B_{p,∞}$ is the quaternion algebra ramified at $p$ and infinity. - $\newcommand{\O}{\mathcal{O}}\O, \O_0, \O_1, \dots$ are maximal orders of $B_{p,∞}$. - $I, I_0, I_1, \dots$ are left ideals of some maximal order $\O$. - $θ:\O_0→\End(E_0)$ is an isomorphism of maximal orders. - If $E$ is a curve and $G⊂E(\bar{\mathbb{F}}_p)$ a finite subgroup, we denote by $E/G$ the image of the unique isogeny of kernel $G$. - If $A$ is a point of $E$, we denote by $〈A〉$ the cyclic subgroup generated by $A$. # Easy problems This is a list of problems that are known to be solvable in time polynomial in $\log p$. 1. Given $j(E)$ compute all elliptic curves $ℓ$-isogenous to $E$ (Vélu's formulas, or modular polynomials). 1. Given curves $E_0,E_1$, isogenous of degree $ℓ$, compute the kernel of an isogeny $φ:E_0→E_1$ of degree $ℓ$ (Elkies formulas and related algorithms). 1. Given $E$ and a finite subgroup $A⊂E(\bar{\mathbb{F}}_p)$ of size $ℓ$, compute $E/A$ and the rational maps of the isogeny $φ:E→E/A$. (Vélu's formulas) 1. Given a maximal order $\O$, compute $j(E)$ such that $\End(E)≃\O$. 1. Given $\O_0,\O_1$, find an ideal $I$ which is a left $\O_0$-ideal and a right $\O_1$-ideal. We can further ask that the norm of $I$ is - a prime, - a prime power, - power-smooth. 1. Given $\O$ representing a small $ℓ$, compute $E$ such that $\End(E)≃\O$. # Hard problems This is a list of problems for which no algorithm polynomial in $\log p$ is known. Each of the problems below has a more restrictive variant where $m,n$ are prime powers. 1. Given $j(E)$, compute an order $\O$ such that $\O≃\End(E)$. 1. Given $E_0,E_1$ and an integer $m$, decide if $E_0$ and $E_1$ are $m$-isogenous. 1. Given $\O$, given a smooth $m$, is $m$ represented by $\O$? 1. Given $E_0,E_1$, find an isogeny $φ:E_0→E_1$. 1. Given $E_0,E_1$ and a smooth integer $m$, find an isogeny $φ:E_0→E_1$ of degree $m$. 1. Given $E,E/〈A〉,E/〈B〉,E/〈A,B〉$, where $A,B∈E$ are unknown points of orders $m,n$. Determine $A$ or $B$. 1. Given $E,E/〈A〉,E/〈B〉,E/〈A,B〉$ as above, given the image of $A$ in $E/〈B〉$. Determine $A$. 1. Given $E,E/〈A〉$, where $A∈E$ is an unknown point of order $m$. Given points $B,C∈E$ of order $n$, and their images in $E/〈A〉$. Determine $A$. ## Known reductions Here we list known polynomial reductions between the hard problems given above. - All problems reduce to 1. Indeed, we can combine it with easy problem 5 to solve each.