0
$\begingroup$

In order to generate secure elliptic curves, this answer recommends to

  1. Calculate the cardinal $|E(\mathbb{F}_p)|$
  2. Check this cardinal is in the hasse interval

(with $p$ prime) and to restart the process with a different $p$ if step 5 (or others) fails. This suggests that cardinality is not always bounded in the way Hasse's theorem indicates.

I understand that different generator points can lead to "different cardinalities" in $\mathbb{F}_p$ (given prime $p$ and fixed parameters $a$ and $b$ in $y^2=x^3+ax+b$), but I see various examples where cardinality is well below the lower bound of Hasse's interval no matter what generator I choose.

Is it that I just need to brute-force generators in $\mathbb{F}_p$ until I find one that leads to an acceptable cardinality? or what am I missing?

$\endgroup$
3
$\begingroup$

The order of a point on $E(\mathbb F_p)$ merely divides the cardinality $\#E(\mathbb F_p)$ (or $|E(\mathbb F_p)|$) of the group. If $\#E(\mathbb F_p)$ has composite order, it may have small prime factors and therefore there may be low-order points that don't generate all of $E(\mathbb F_p)$. For example, on any Montgomery curve $y^2 = x^3 + A x^2 + x$, the point $(0, 0)$ always has order 2, even if the curve has large order like Curve25519, where $p = 2^{255} - 19$ and $A = 486662$, whose order is $8\ell$ for $\ell$ near $2^{252}$. But the standard base point $(9, \cdots)$ on Curve25519 has order $\ell$, and $(8, \cdots)$ has order $8\ell$.

$\endgroup$
  • $\begingroup$ Thanks! Now I recall having read somewhere else your 1st remark, but obviously it went over my head until now that you have pointed that out. Then that fact seemingly provides a much simpler approach for calculating cardinality than Schoof's or baby-giant step algorithms: Given a sufficiently high order of a point, some multiple of that order satisfies Hasse's interval (giving thus the cardinality). Now, is there a way to "a priori" obtain a generator/point of which order fits Hasse's interval? Brute-forcing this issue is taking me a while (should I post this as a new question?). $\endgroup$ – Iñaki Viggers Jun 13 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.