Let $\ell$ and $p$ be two primes. We are looking for a method for checking whether two supersingular elliptic curves over the finite field $F_p$, given through their $j$-invariants, are $\ell$-isogenous. In what follows I will somewhat imprecisely also speak of isogenous $j$-invariants. Using the classical modular polynomial $\Phi_\ell(X,Y)$ this is easy to decide since two $j$-invariants $j_1$ and $j_2$ are $\ell$-isogenous iff $\Phi_\ell(j_1, j_2) = 0$.
The disadvantage of these classical modular polynomials is that they have many non-zero and actually very large coefficients. The so-called canonical modular polynomials $\Phi_\ell^c(X,Y)$ instead have a much smaller degree in $Y$. Following Cohen-Frey, Section 17.2.3c in order to prove that the elliptic curves described by two given $j$-invariants $j_1$ and $j_2$ are $\ell$-isogenous, one has to find a common root $X$ of the two rational functions $\Phi_\ell^c(X,j_1)$ and $\Phi_\ell^c(\ell^s/X,j_2)$, where $s = 12/\text{gcd}(12, \ell-1)$. We typically multiply the second funtion by a suitable power of $X$ ($X^{\ell+1}$ will do) in order to get a polynomial in $X$ again.
The approach in the book of Cohen-Frey is stated over the complex numbers, but the authors apply it also to elliptic curves over finite fields (see Example 17.26 in the book). This is also the setting we are interested in. We did extensive computations with different values of $\ell$ and $p$.
However, we have found many examples of non-isogenous $j$-invariants such that nevertheless the two functions $\Phi_\ell^c(X,j_1)$ and $\Phi_\ell^c(\ell^s/X,j_2)\cdot X^{\ell+1}$ share common roots in $F_p$. For example, letting $\ell = 11$, $p = 101$, $j_1 = 3$ and $j_2 = 66$, we have the common factor $X^2 + 3X + 21$ of both polynomials, which leads to two common roots $X$ over $F_{p^2}$.
Are there any sufficient conditions on $\ell$ or $p$ which make the approach work over finite fields? We have not found any counter-examples to Cohen-Frey's approach for very small $\ell$ -- is there a reason for that lack of counter-examples?
