2
$\begingroup$

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?

  • 0
    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.2012-12-13

0 Answers 0