Curva elíptica: punto de orden primo $n$

Question

Estoy intentando comprender el Cifrado ElGamal sobre Curvas Elípticas (comienzo de este documento )

Tengo una curva elíptica $E\left( \mathbb{F}_{11} \right)$ definido por $y^2 = x^3 + 2x + 3$

Necesito elegir un punto $P$ en $E\left(\mathbb{F}_{11}\right)$ de orden primo $n$

No he podido encontrar nada que me ayude a entender qué se entiende por "orden primario". $n$ '. ¿Puede alguien indicarme algo útil o explicarme cómo encontrar dicho punto? $P$ ¿Por favor?

Soy informático, así que asumo conocimientos limitados de cualquier matemática/teorema complejo - todos mis conocimientos sobre curvas elípticas son autodidactas a través de Google...

Answer 1

Ya te han dado una buena respuesta en los comentarios, pero vamos a añadir un pequeño detalle.

Encontramos todos los puntos de la curva (Obsérvese que $O$ es el punto en el infinito)

$$(x, y) = O, (0, 5), (0, 6), (2, 2), (2, 9), (3, 5), (3, 6), (4, 3), (4, 8), (6, 0), (8, 5), (8, 6), (10, 0)$$

Puede verificar cada uno de ellos comprobando que

$$y^2 = x^3 + 2x + 3 \pmod{11}$$

Si tomamos un punto $P$ y escriba $P, P+P, \ldots$ obtenemos

• $1P = (2, 2)$
• $2P = (0, 5)$
• $3P = (3, 5)$
• $4P = (4, 3)$
• $5P = (8, 6)$
• $6P = (10, 0)$
• $7P = (8, 5)$
• $8P = (4, 8)$
• $9P = (3, 6)$
• $10P = (0, 6)$
• $11P = (2, 9)$
• $12P = O$

Compare esta lista de puntos con la lista anterior. ¿De qué te das cuenta? Cada uno de los puntos debe sea un punto de la curva.

A continuación, ¿cuántos puntos hemos recorrido, cuál es el orden?

Esta curva elíptica tiene orden $\#E = |E| = 12$ ya que contiene $12$ puntos en su grupo cíclico.

Existe un teorema llamado Teorema de Hasse: Dado un módulo de curva elíptica $p$ el número de puntos de la curva se denota por $\#E$ y está limitada por $$p+1-2\sqrt{p} ≤ \#E ≤ p+1+2 \sqrt{p}$$

Interpretación: El número de puntos es cerca de principal $p$ .

Answer 2

No tengo suficiente reputación para comentar, así que respondo aquí.

El comentario dice:

Gracias, esto tiene sentido, pero si elijo $P=(4,3)$ entonces obtengo $\#E=3$ como $3P=\mathcal{O}$ ¿Qué te hizo elegir P=(2,2)?

Sin embargo, como no todos los puntos son generadores, sólo el punto generador puede generar todos los puntos de la curva.

Así que.., $P=(2,2)$ es un generador, pero $P=(4,3)$ no lo es.

puede leer esto : https://www.entrust.com/wp-content/uploads/2014/03/WP_Entrust_Zero-to-ECC_March2014.pdf