¿Cómo calcular el orden de una curva hiperelíptica ($y^2=f(x)$,$deg(f)=2 \cdot g+1$,$g=4$), sobre$F_p$ para$p$% ($p$ prime)? ¿Hay algoritmos eficientes para hacerlo? ¿Es posible con Pari / Magma / Sage? ¿Hay algoritmos eficientes para resolver el problema del logaritmo discreto para tales curvas?
Respuesta
¿Demasiados anuncios?
Para estas curvas, siempre tenemos un punto en el infinito: (0:1:0).
La forma más sencilla de contar los otros puntos para conectar todos los $x$-valores, y ver si $f(x)$ es un cuadrado en $F_p$. Si es distinto de cero de la plaza, tenemos dos puntos: $(x, \pm \sqrt{f(x)})$. Si $f(x)=0$, tenemos un punto: $(x,0)$. Y si no es un cuadrado, no tenemos puntos de la $x$-valor.
Por lo tanto, si $N_p$ es el orden de la curva, tenemos $1 \leq N_p \leq 2p+1$ y $$N_p = 1 + \sum_{x=0}^{p-1}\left(\left(\frac{f(x)}{p}\right) + 1\right)$$ donde $\left(\frac{a}{p}\right)$ es el símbolo de Legendre.
Podemos arreglar esto $$N_p = p+1 + \sum_{x \in F_p} (f(x))^{\frac{p-1}{2}}$$ y, a continuación, tomar la suma, para cada término en $(f(x))^{\frac{p-1}{2}}$ por separado.
Desde $\sum_{x \in F_p} x^n$ 0 si no $p-1|n$$n \neq 0$, sólo necesitamos saber de unos coeficientes de $(f(x))^{\frac{p-1}{2}}$.
Deje $a_{p,i}$ ser el coeficiente de $x^{i(p-1)}$ $f(x)^{(p-1)/2}$ $i=1, \ldots, g$ (estos son los únicos términos que contribuyen a nuestra suma); y deje $a_p = a_{p,1} + \ldots + a_{p,g}$.
A continuación,$N_p \equiv p+1-a_p \pmod{p}$.
Desde $|N_p - (p+1)| \leq 2g\sqrt{p}$ (por parte de las conjeturas de Weil) si la curva tiene una buena reducción de más de $F_p$, se puede elegir $p$ suficientemente grande como para que $a_p$ determina completamente $N_p$.
Sé que hay otros métodos para el recuento de puntos, pero esta es muy simple, y es el método más rápido si $f(x)$ es dispersa polinomio (la mayoría de los coeficientes son 0). Tenga en cuenta que usted no tiene que calcular todos los de $(f(x))^{\frac{p-1}{2}}$ encontrar los coeficientes $a_{p,i}$, y sólo es necesario calcularlos modulo $p$.
