Calculating Elliptic Curve cofactor h

1k Views Asked by At

An Elliptic Curve in short Weierstrass form over a finite field $F_p$ is given by the equation:

$$y^2 = x^3 + ax + b \mod p$$

To use this curve for cryptographic purposes, in the domain parameters of the curve a point $G$ on the curve is defined. $n$ is the order of the subgroup generated by $G$ and is usually included in the domain parameters of the curve. The cofactor of such a curve is defined as:

$$h = \frac{\#E(F_p)}{n}$$

where $\#E(F_p)$ is the number of all points that satisfy the curve equation and $n$ is the order of the curve.

For most (well-chosen) domain parameters, $h$ can be approximated reasonably well by:

$$h \approx \frac{p}{n}$$

But what's the approach to actually calculate $h$ when only $a, b, n, p$ are given that gets around explicit point counting algorithms like Schoof/Elkies?

1

There are 1 best solutions below

1
On BEST ANSWER

Applying Hasse's theorem, we find that $h\in[h_{\text{min}},h_{\text{max}}]$ with $$\begin{align} h_{\text{min}} &= \frac{p+1 - 2\sqrt{p}}{n} & h_{\text{max}} &= \frac{p+1 + 2\sqrt{p}}{n} & \therefore\quad h_{\text{max}}-h_{\text{min}} &= \frac{4\sqrt{p}}{n} \end{align}$$ Consequently, if $n>4\sqrt{p}$ (it usually is), the uncertainty of $h$ as quantified above is smaller than $1$, so there is no more than one integer in $[h_{\text{min}},h_{\text{max}}]$.

The solution for $h$ is then the integer nearest to $$\frac{h_{\text{min}}+h_{\text{max}}}{2} = \frac{p+1}{n}$$ (Reasonably well indeed.)