# Different elliptic curves over given $\mathbb{F}_q$ can have different orders?

As the title says: For a given $q \in \mathbb{N}$, in $\mathbb{F}_q$, is it true that different curves on it can have different group orders?

I assume yes. Let $q:=5$. Wikipedia gives $9$ points for $x^3+x+1$. For $x^3-x$, calculating it in the same naive way, I get only $8$:

• $(0,0)$ for $x=0$
• $(1,0)$ for $x=1$
• $(2,1)$ and $(2,4)$ for $x=2$
• $(3,2)$ and $(3,3)$ for $x=3$
• $(4,0)$ for $x=4$
• "infinity"

Bonus question: Is this the reason why factorization using elliptic curves is better? Say, if I don't get a factor with one elliptic curve, I can try another one, and since it might have a different order, I might "somehow" get a factor?

-
Yes and yes. ${}$ – Qiaochu Yuan Dec 13 '12 at 7:21
Unless you are looking for only a small subset of prime factors. Then p-1 algorithm might be much faster. For the same group order, p-1 is much faster. Therefore the recent practice is a chain: $p-1\rightarrow p+1\rightarrow$ ECM. But if you are only looking for 1 implementation, then yes ECM with multiple curve is better. – Yong Hao Ng Dec 13 '12 at 19:35