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?



What is the fastest algorithm for counting points in elliptic curves mod n?
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.


