Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.