# Why does Hasse's theorem sometimes seem to be invalid?

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?

## 1 Answer

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$$.

• 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?). – Iñaki Viggers Jun 13 '19 at 22:37