I am curious of the details of how one would go about generating elliptic curve parameters. (I know standardized parameters exist, but I'm trying to understand both how they were generated and the general case.)
Let's also assume we want to work in a prime-order subgroup of size $O(2^n)$. For simplicity, let's work over a prime-order field $F_p$.
As I understand it, the basic idea is (1) generate a random elliptic curve $E$ over $F_p$; (2) use a point-counting algorithm to count the number of points $N = |E(F_p)|$; finally, (3) check that $N$ is divisible by an $n$-bit prime
I am confused about the 3rd step: how is it implemented efficiently without using a general-purpose factoring algorithm? Also, how many iterations are required (in expectation) before finding a curve $E$ whose order $N$ is divisible by an $n$-bit prime? Finally, given $n$, how should we best choose $p$? (This is related to the question of what co-factor one should be looking for.)