I am trying to prove that, given an Elliptic Curve defined on $\mathbb{F}_p$ with $p$ a prime number, the order $q$ verifies: $|p| \le |q| \leq |p|+1$ where $|x|$ denotes the length in bits of $x$.
To do it, I try to use the Hasse's theorem which says:
If $N$ is the number of points on the elliptic curve E over a finite field with $q$ elements, then Helmut Hasse's result states that $|N - (q+1)| \le 2 \sqrt{q}$
So in our case we have: $|q-p| \le 2\sqrt{p-1}$ which gives $log_2(|q-p|) \le log_2(2\sqrt{p-1}) \Leftrightarrow log_2(|q-p|) \le 1 + \frac{1}{2}log_2(p-1)$ but it seems that it would not give me the expected result. Thanks in advance for any idea.
Well, it wasn't very complicated but I didn't see the trick...
So from Hasse's theorem we have : $|q - (p+1)| \le 2 \sqrt{p}$ so $q \le p + 1 + 2 \sqrt{p}$.
It is easy to see that $p + 1 + 2 \sqrt{p} \le 2p$ from a certain rank. So $q \le 2p$ and by applying the logarithm function we found $log_2(q) \le log_2(p) + 1$.