Cálculo del cofactor h de la curva elíptica

Question

Curva elíptica en forma corta de Weierstrass sobre un campo finito $F_p$ viene dada por la ecuación

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

Para utilizar esta curva con fines criptográficos, en los parámetros de dominio de la curva un punto $G$ en la curva. $n$ es el orden del subgrupo generado por $G$ y suele incluirse en los parámetros de dominio de la curva. El cofactor de una curva de este tipo se define como:

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

donde $\#E(F_p)$ es el número de todos los puntos que satisfacen la ecuación de la curva y $n$ es el orden de la curva.

Para la mayoría de los parámetros de dominio (bien elegidos), $h$ puede aproximarse razonablemente bien mediante:

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

Pero ¿cuál es el enfoque para realmente calcular $h$ cuando sólo $a, b, n, p$ que evite los algoritmos explícitos de recuento de puntos como Schoof/Elkies?

Answer 1

Aplicación de Teorema de Hasse encontramos que $h\in[h_{\text{min}},h_{\text{max}}]$ con $$\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}$$ Por consiguiente, si $n>4\sqrt{p}$ (normalmente lo es), la incertidumbre de $h$ como se ha cuantificado anteriormente es menor que $1$ por lo que no hay más de un entero en $[h_{\text{min}},h_{\text{max}}]$ .

La solución para $h$ es el número entero más próximo a $$\frac{h_{\text{min}}+h_{\text{max}}}{2} = \frac{p+1}{n}$$ (Razonablemente bien.)