What is the fastest algorithm for counting points in elliptic curves mod n? I need an algorithm for getting the order of the group in random elliptic curves mod n, being n a composite module. As far as I know, usual algorithms like Schoof's algorithm only works with prime modulus. What are the alternatives?
 A: I don't expect that there will be a known polynomial time algorithm. If I recall correctly, we don't know a polynomial time algorithm to decide, given $n=pq \equiv 1 \pmod 4, p,q$ primes, whether $p,q \equiv 1 \pmod 4$ or not. If we had a polynomial time algorithm to compute the number of points in $y^2 =x^3+x \pmod n$ we could decide the previous problem (as the number of points would be $(p+1)(q+1)$ when $p,q \equiv 3 \pmod 4$). Even better, if we knew that $p,q \equiv 3 \pmod 4$, we would then factor $n$.  
If you have a point on the curve (of reasonably large order), baby-step-giant-step will be a $\sqrt n$ algorithm.
A: Let the group order be $o$.
If $o$ is odd, you can factor $n$ in polynomial time
(I am pretty sure this will work for even $o$ too).
Let $\psi_k$ be the k-th division polynomial of $E$
and $p$ a prime factor of $n$.
Choose random $x_0 \in [1,n]$ and compute
$\psi_o(x_0)\equiv a \pmod{n}$.
If $x_0$ is on the curve modulo $p$, $a$ is zero modulo $p$, otherwise
it is non-zero.
So if $x_0$ is on the curve modulo $p$, but not on it modulo
some other factor, you find multiple of $p$.
The probability of being on the curve modulo $p$ is about $\frac12$.
