Which composites pass this probabilistic primality test?

Question

If a composite integer resembles a prime too closely, it must pass algorithmic tests designed to find primes and in addition avoid nontrivial factorization.

Given an integer $p$, assume it is prime and run some testing algorithms for primality. If $p$ fails verification then declare $p$ composite and stop.

Which composites $p$ pass the following probabilistic primality test?:

1. Pick random integers $a,b$ and count the points modulo $p$ on the elliptic curve $E : y^2=x^3+ax+b$. Let the number of points be $o$. For point counting use Schoof's algorithm.

2. Verify $o$ is a multiple of the order by finding a point $P$ on $E$ and check if $oP=0$. For finding $P$, chose deterministic algorithm for square roots, say the implementation in sagemath 7.0.

3. Pick a random integer $X$ and compute $d=\psi_o(X) \mod p$ where $\psi_n$ is the $n$-th division polynomial. Verify $\gcd(d,p) \mod p \in \{0,1\}$. This step might find a nontrivial factor, since counting points modulo composites is probabilistically equivalent to factoring.

The running time of this algorithm is polynomial in $\log{p}$ if $p$ is prime. I believe explicit bounds for the running time are known for prime $p$.

Similar algorithm is via computing square roots modulo $p$. Square roots modulo composite are probabilistically equivalent to factoring, so just try to factor $p$ with square roots and if you fail to compute the square root of known square then $p$ is composite.

Answer 1

Turning my comment into an answer, as I recently learned that my hunch can be justified.

Schoof's algorithm computes, for each small $\ell$ and a point $(x,y) \in E[\ell]$, the element $a_{\ell} \in \mathbb{Z}/\ell$ such that $(x^{p^2},y^{p^2})+p(x,y) = a_{\ell}(x^p,y^p)$ (in the group law on $E$) and recovers the trace of Frobenius by applying the Chinese remainder theorem to the $a_{\ell}$.

We can try to do that when $p$ is not prime and it may fail in many ways. One way it can fail is that $(x^p,y^p)$ is not in $E[\ell]$ (or even in $E$). We can start by checking this, which is a polynomial time computation in the range of $\ell$ of interest. And, if $p$ is not a prime power, [1] proves that indeed there is an $\ell$ in the range of interest where this failure will happen, showing that $p$ is not prime.

[1] Couveignes, Jean-Marc; Ezome, Tony; Lercier, Reynald, https://arxiv.org/abs/0810.2853