Algebras de endomorfismos en curvas elípticas (Parte 1 Anillos de Endomorfismos)

Hoy quiero hablar un poco de cómo analizar internamente la estructura de un grupo abeliano, lo cual lo haremos con el grupo abeliano que forma una curva elíptica.

Es decir, a veces para poder entender a un objeto, es indispensable poder entender los morfismos internos del objeto.
En este caso, lo que quiero es poder estudiar al grupo abeliano como un "espacio vectorial" y estudiar las transformaciones que hay en él... y pues con esto podemos incluso hablar de matrices, determinantes, trazas, polinomios característicos y valores propios.

Pero primero en esta parte, le daremos estructura de anillo a los homomorfismos de la curva en si misma, y en la siguiente parte de este post le daremos ya estructura de álgebra.

Recordando muy informalmente curvas elípticas

Recordemos rápidamente el contexto deseado, que son la curvas elípticas de una manera muy informal ya que he hablado antes de esto aquí en mi blog (busca keyword "elíptica").

Las curvas elípticas son objetos muy usados en criptografía ya que proveen con su estructura geométrica una manera diferente de "sumar y restar" que al ésta ser sustituida en los algoritmos de llave pública como Diffie-Hellman que es el más usado en todas las telecomunicaciones en vez de grupos finitos (enteros módulo un número primo usualmente) resulta muy rápido y más seguro. Un ejemplo intuitivo de cómo funciona esta suma es el siguiente:

Lo que estamos viendo aquí es una curva $latex E$ en azul, y dos puntos en ella que son $latex P,Q\in E$ , que su suma está definida como la proyección con el eje $latex x$ del tercer punto de intersección de la linea que los une, que en este dibujo está denotado como $latex P+Q$.

Siempre habrá este tercer punto de intersección si la curva es vista de manera proyectiva, lo cual veremos en la siguiente sección y es justificado por el teorema de Bézout.

Si quisieras calcular el punto $latex P+P$ se hace de manera parecida, sólo que la linea a considerar es la tangente a $latex P$ en la curva $latex E$.

El negativo de un punto es sólo su proyección con el eje $latex x$ es decir si $latex (x,y)\in E$ entonces $latex -(x,y)=(x,-y)$, y sumar $latex P+ (-P)=\infty$ , donde este $latex \infty$ será explicado en la siguiente sección y este $latex \infty$ nos funcionará como el cero (identidad) en la estructura de grupo abeliano que tiene la curva.

Bajo esta operación tenemos que la curva $latex E$ y sus puntos forman un grupo abeliano, es decir, con sus puntos bajo esta operación ya explicada es conmutativa, cada elemento tiene un inverso, es asociativa y cerrada, y lo más importante... es algebraica... es decir,  hay fórmulas explícitas que no necesitan funciones raras para definirlas (como raíces cuadradas, logaritmos ni nada).

Entrando un poco más en lo que significa "algebraico" es que su suma se puede definir con simples cocientes de polinomios, a eso me refiero con que algo sea "algebraico", y más allá de ser una curva, esto se le llama variedad abeliana, que es un objeto algebraico dotado de una estructura de grupo con una operación continua bajo cierta topología (Zariski), y que está dada por polinomios cuya operación explícita puede ser vista aquí en wikipedia.

Puedes notar que también puedes calcular "$latex n$ veces el punto $latex P$ , es decir $latex P+P+\ldots +P$  ($latex n$ veces) para todo $latex n\in \mathbb{Z}$ , por lo que significa que podemos "hacer actuar a los enteros en la curva", esto es lo que se le conoce como un $latex \mathbb{Z}$-módulo, y todo grupo abeliano, tiene esta capacidad, por más abstracto que sea el grupo, siempre se puede hablar de "$latex n$ veces aplicar la operación + del gropo".

La definición formal es que son curvas suaves proyectivas de género 1 con un punto distinguido.

Suaves significa que son diferenciables en todos lados y no hay puntos dobles o nodales por ejemplo dos que cumplen la definición vistas en $latex \mathbb{R}\times\mathbb{R}$ serían:

Espacio proyectivo.

Aquí justificamos este símbolo $latex \infty$.
Proyectivo significa que en vez de vivir en espacios vectoriales usales como $latex \mathbb{R}^n$ o $latex \mathbb{F}_{q}$ , vive en un nuevo espacio que ahora definiremos que es $latex \mathbb{P}^n_\mathbb{R}$ o en  $latex \mathbb{P}^n_{\mathbb{F}_q}$ respectivamente, donde estos espacios incluyen un punto nuevo, que es el infinito y múltiplos de vectores serán identificadas con un sólo punto.

Este espacio proyectivo lo tengo bien explicado aquí pero a grandes rasgos es un espacio en el cual identificamos todos los múltiplos de un punto como el mismo punto, imaginen un espacio vectorial, donde un vector $latex v$ al aumentar su magnitud por una constante $latex c\neq 0 \in \mathbb{R}$ tenemos que el nuevo vector sería $latex c \cdot v$. Aquí , tenemos que por ejemplo en $latex \mathbb{R}^n$ los puntos $latex v$ y $latex c \cdot v$ serán identificados con el mismo vector, es decir es como una contracción y a este nuevo espacio con esta nueva regla lo denotamos como  $latex \mathbb{P}^n_\mathbb{R}$.

El punto $latex [0:0:0]$ no existe, lo cual es una consecuencia de las reglas que acabo de definir, por lo que al interesado en álgebra le serviría la definición que es:  $latex \mathbb{P}^n_\mathbb{R}:=\mathbb{R}^{n+1}\setminus \lbrace \overline{0} \rbrace /\sim$ donde la relación $latex \sim$ es que si $latex \overline{u},\overline{v}\in \mathbb{R}^{n+1}$ entonces $latex \overline{u}\sim \overline{v}$ sí y sólo sí $latex \overline{u} = \lambda \overline{v}$ donde $latex \lambda\in \mathbb{R}^{*}$ , es decir esto nos colapsa toda una familia de puntos en $latex \mathbb{R}^{n+1}$ a un sólo punto que denotaremos como $latex [u] \in \mathbb{P}^n_\mathbb{R}$ y tenemos que en este caso $latex [u]=[v]$.


Y de hecho las ecuaciones proyectivas de los ejemplos anteriores serían la ecuación homogénea que hace que los grados de todos los monomios sean iguales $latex y^2z=x^3-xz^2$  así como $latex y^2z=x^3-xz^2 + z^3$ donde ahora vemos que tiene otra variable $latex z$ que nos permitirá agregar otra familia de puntos, por ejemplo, los puntos de la ecuación afín serían los puntos de la forma $latex [x:y:1]$ pero también tenemos que la ecuación también tiene el punto $latex [0:1:0]$  que será el punto racional distinguido, y todas las ecuaciones cúbicas de esta forma lo contienen.


También agregamos un punto muy especial como ya vimos que es usualmente $latex \infty:=[0:1:0]$ que es muy usado en el modelo matemático de lo que significa dibujar "horizontes" en un paisaje, y observando que unas vías del tren no son paralelas, ya que se tocan en el infinito, como lo pueden ver aquí.

Y bueno una curva elíptica de género 1 sin puntos raros, siempre es transformable a una ecuación de la forma $latex y^2 = x^3 + ax+b$ mediante sustitución de variables, a esta forma se le llama forma de Weierstrass.

Género de una curva

El género es un poco más difícil de explicar en este post y con esta informalidad, pero imaginen que tiene que ver con que si la ecuación de la curva la vemos en el espacio complejo... su gráfica será una dona con 1 hoyo... si fueran dos hoyos tendría género 2, por lo que una curva elíptica tiene género 1 y se ve así  "intuitivamente" como una función compleja:

A mi me gusta mucho el álgebra así que podemos calcular de hecho géneros de maneras más abstractas gracias aun teorema muy interesante, de Riemann-Roch, que nos dice el género de un objeto geométrico con la dimensión de ciertos espacios de funciones el cual tengo explicado de manera formal aquí.

Estoy trabajando en mi mente un artículo para explicar el teorema de Riemann-Roch sin necesitar álgebra tan dura, con pura teoría de espacios vectoriales, espero pronto tenerlo.

El género cuando no hay puntos raros en la ecuación, se puede calcular con los grados de los monomios en una ecuación.


En términos criptográficos, recuerden que hasta ahora las computadoras no saben cómo manejar a los números reales (ni complejos), de manera continua, es decir, cuando ustedes programan un "float" o "double" sabemos que tienen un "límite" en su representación, por lo que realmente la computadora sólo sabe manejar estructuras finitas.

Estructura finita asociada a las curvas para poder usada en criptografía y computación.

Algo interesante de las curvas elípticas es que su estructura de grupo funciona en cualquier campo... no sólo en los números reales, los complejos o los racionales que son infinitos... sino en campos finitos, como son los enteros módulo p.

De manera básica y para no entrar en detalles tenemos que si escogemos cualquier número primo $latex p$ , tenemos que si $latex a,b\in \mathbb{Z}$ podemos calcular que $latex a\cdot b\equiv c \bmod p$  donde $latex c$ será solamente el residuo de la división al calcular $latex a\cdot b/p $ , este residuo está entre el 0 y $latex p-1$, y todo entero se puede reducir módulo $latex p$ de la misma forma (dividiendo entre $latex p$ y calculando su residuo), este conjunto donde juntas a todos los elementos reducidos en sus respectivas clases se denota como $latex \mathbb{F}_p$ y consta de $latex p$ elementos, del 0 al $latex p-1$.


La suma se define de manera similar y todo elemento tiene un inverso multiplicativo y aditivo, es decir para todo $latex [a]\in \mathbb{F}_p$ tenemos que existe un $latex [a]^{-1}\in \mathbb{F}_p$ tal que $latex [a]\cdot [a]^{-1} = [1]$  , por ejemplo en $latex \mathbb{F}_7$ tenemos que el inverso  multiplicativo de $latex [3]$ es $latex [5]$ ya que $latex 5\cdot 3=15$ y $latex 15\equiv 1\bmod 7$ por lo que podemos decir abusando de la notación que "dividir entre $latex [3]$" módulo $latex 7$ equivale a multiplicar por $latex [5]$.
Con la suma el negativo de $latex [a]\in \mathbb{F}_p$ es de hecho $latex [p-1]\cdot [a]$ ya que $latex (p-1)\cdot a = pa-a \equiv -a \bmod p$ , por ejemplo en $latex \mathbb{F}_7$ tenemos que $latex -[3]= (p-1)\cdot 3 = 6\cdot 3 = 18 \equiv 4 \bmod 7$ , por lo que $latex -[3] \equiv [4]$ y es fácil verificarlo ya que al sumar con su inverso aditivo al 3 tenemos que $latex -[3] + [3] = [4] + [3] \equiv 0 \bmod 7$ (ya que no deja residuo).

Se pueden definir campos para cada potencia de $latex p$ es decir $latex \mathbb{F}_{p^n}$ pero eso queda de tarea para ustedes investigar cómo se hace.

Con esto tenemos que si evaluamos todas las posibles soluciones de una curva elíptica bajo esta aritmética, tenemos que ya no se ve como una "curva", pero realmente lo es en el sentido algebraico, y se ve por ejemplo $latex y^2=x^3 - 4x+6$ sobre $latex \mathbb{F}_{197}$ así:

Si implementan la regla de adición como en wikipedia, donde las divisiones que vean en las funciones que definen la suma de dos puntos las interpretan como "calcular el inverso multiplicativo" (lo cual se hace con el algoritmo de euclides extendido), una consecuencia del teorema fundamental del álgebra les dirán que las "lineas entre dos puntos" en aritmética modular también funcionan, esto es de manera informal pero sólo quiero meter la idea, en posts anteriores formalizo esto.



Grupos de homomorfismos en grupos abelianos (curvas elípticas en este caso)

Recordemos que un homomorfismo entre dos grupos (o dos curvas) $latex G_1$ y $latex G_2$ es un mapeo que respeta la estructura de grupo en cada uno. Es decir si $latex \langle G_1,+\rangle$ y $latex \langle G_2,\oplus\rangle$ son sus respectivas operaciones. tenemos que $latex \alpha \in Hom(G_1,G_2)$ es un homomorfismo entre $latex G_1$ y $latex G_2$ , es decir  $latex \alpha:G_1\rightarrow G_2$ si para $latex P,Q\in G_1$

$latex \alpha(P+Q)=\alpha(P)\oplus \alpha(Q)$

También tenemos que $latex \alpha$ también manda infinitos de un grupo a infinitos del otro.

 $latex \alpha(\infty_{G_1})=\infty_{G_2}$.


Algo muy interesante es que el conjunto de todos los homomorfismos, es decir $latex Hom(G_1,G_2)$ forma un grupo abeliano, es decir, puedes sumar los homomorfismos, noten que ya no estamos hablando de los puntos de la curva solamente o de elementos de grupos en general, es decir si $latex \alpha,\beta\in Hom(G_1,G_2)$ definimos bajo la operación nueva de homomorfismos $latex \boxplus$ una nueva función $latex \alpha\boxplus \beta\in Hom(G_1,G_2)$ :

$latex (\alpha\boxplus\beta):G_1\rightarrow G_2$
$latex P\mapsto \alpha(P)\oplus \beta(P)$

Es fácil demostrar que $latex \alpha\boxplus \beta$ también respeta estructura de grupo en $latex G_2$ (es decir que es un homomorfismo) , y pues tenemos que la identidad es el morfismo $latex [0]\in Hom(G_1,G_2)$ que manda todo al 0 del grupo $latex G_2$.
También para que $latex Hom(G_1,G_2)$ sea grupo bajo la operación $latex \boxplus$, necesitamos un inverso, es decir, si $latex \alpha\in Hom(G_1,G_2)$ existe un $latex -\alpha \in Hom(G_1,G_2)$ y de hecho pueden ver que este es simplemente $latex -\alpha:G_1\rightarrow G_2$ que mapea $latex P\mapsto \alpha(-P)$ por lo que $latex \alpha\boxplus -\alpha$ está definido como $latex (x,y)\mapsto \alpha(x,y)\oplus \alpha(x,-y)$ y esto y si $latex \alpha(P)=Q\in G_2$ tenemos que es igual a $latex Q\oplus -Q=\infty_{G_2}$ , por lo que mapea al cero de $latex G_2$ y $latex (\alpha\boxplus -\alpha)(P)=\infty_{G_2}$ para todo $latex P\in G_1$ por lo que $latex \alpha\boxplus -\alpha=[0]\in Hom(G_1,G_2)$.

De manera similar se puede demostrar que $latex \boxplus$ es asociativa,  por lo que $latex Hom(G_1,G_2)$ es un grupo.

También como mencionamos hace rato, todo grupo abeliano tiene estructura de $latex \mathbb{Z}$ módulo... es decir, en este ejemplo podemos hablar de aplicar en $latex Hom(G_1,G_2)$ la operación $latex \boxplus$ varias veces a sus elementos, (en este caso homomorfismos entre los dos grupos) es decir $latex n\alpha$ simplemente será:

$latex n\alpha:G_1\mapsto G_2$
$latex P\mapsto \alpha(P)\oplus\ldots \oplus \alpha(P)=\bigoplus_{k=1}^{n} \alpha(P)$

Por lo que decimos que $latex Hom(G_1,G_2)$ tiene estructura de $latex \mathbb{Z}$ módulo.

Anillos de Endomorfismos entre grupos abelianos.

Este es un caso especial de $latex Hom(G_1,G_2)$ , ahora imaginen que $latex G_1=G_2$ por o que lo denotaremos simplemente por $latex G$ , y vamos a definir que $latex End(G):=Hom(G,G)$ pero adicionalmente para que sea un anillo tenemos que la operación multiplicación de endomorfismos $latex \alpha,\beta\in End(G)$ es  $latex \alpha\circ \beta$ , es decir la composición entre ellos como funciones, es decir $latex (\alpha\circ\beta)(P)=\alpha(\beta(P))$.

Como tenemos que $latex \alpha,\beta Hom(G,G)$ está bien definido $latex \alpha\circ \beta:G\rightarrow G$.

La identidad bajo esta multiplicación es la función identidad , es decir, la que manda un punto a sí mismo, y la denotamos como $latex [1]\in End(G)$.

Ustedes pueden verificar que la operación $latex \circ$ es distributiva con $latex \boxplus$ , es decir que si $latex \alpha,\beta,\gamma\in End(G)$ y $latex P\in G$:

$latex (((\alpha\boxplus\beta)\circ \gamma)(P)=((\alpha\circ \gamma)\boxplus (\beta\circ \gamma))(P)$

y usando que $latex \gamma$ también es in homomorfismo.

$latex (\gamma\circ(\alpha\boxplus \beta))(P)=((\gamma\circ \alpha)\boxplus (\gamma\circ\beta))(P)$

Es fácil ver que por default, en $latex End(G)$ hay una infinidad de endomorfismos, de hecho para toda $latex n\in \mathbb{Z}$ tenemos el mapeo $latex [n]\in End(G)$ el cual definimos como:

$latex [n]:G\mapsto G$
$latex P\mapsto P+\ldots +P$  (n veces)

Donde $latex +$ es la operación del grupo $latex G$

Entonces es fácil ver que de hecho, en un nivel más alto hay otro homomorfismo de anillos entre los enteros y $latex End(G)$ , es decir:

$latex \Psi:\mathbb{Z}\rightarrow End(G)$
$latex n\mapsto [n]$

Y es homomorfismo ya que es fácil verificar que $latex \Psi(n+m)=\Psi(n)\oplus \Psi(m) = [n] \boxplus [m]=[n+m]$ y respeta la estructura de anillo ya que $latex \Psi(n\cdot m)=[n]\circ[m]=[nm]$.

Con esto tenemos mucho para argumentar que $latex \mathbb{Z}$ es un subanillo de $latex End(G)$ ya que $latex End(G)$ no tiene torsión, es decir, el aplicar $latex n$ veces cualquier endomorfismo diferente de $latex [0]$ , nunca nos dará $latex [0]$ y el mapeo entre $latex \mathbb{Z}$ y $latex End(G)$ es inyectivo.

Otra cosa es que $latex [n]\circ \alpha = \alpha \circ [n]$ es decir conmuta, y ustedes lo pueden demostrar fácilmente (pero no siempre es así entre cualquiera $latex \alpha,\beta\in End(G)$, que es cuando en el siguiente post definiremos que $latex End(G)$ está equipado con multiplicación compleja.

En el caso en que se esté trabajando sobre un campo finito en el grupo de una curva elíptica $latex E$ como $latex \mathbb{F}_q$ existe otro endomorfismo muy famoso que es usado mucho en investigación en criptografía , que es el endomorfismo de Frobenius, $latex \phi\in End(E)$ que equivale a $latex (x,y)\mapsto (x^q,y^q)$ , es decir, elevar a la $latex q$ cada coordenada de un punto en la curva usando la reducción en el campo finito $latex \mathbb{F}_q$. Este homomorfismo también conmuta.

Otro remark es que en una curva elíptica $latex \alpha,\beta\in End(E)$ son suprayectivos y por consecuencia $latex \alpha\circ\beta$ también lo es, por lo que jamás será el homomorfismo $latex [0]$ , esto nos dice que bajo la multiplicación del anillo $latex End(E)$ dada por la composición, nunca obtenemos el $latex [0]\in End(E)$ por lo que no existen múltiplos de 0, y $latex End(E)$ es un dominio entero, por lo que pueden usar las reglas de cancelación usuales entre sus elementos tanto por la izquierda como por la derecha.


Espero les haya gustado, la parte 2 la haré pronto, donde extenderemos la estructura de $latex \mathbb{Z}$-módulo de $latex End(E)$ a un $latex \mathbb{Q}$-módulo a través de un tensor.

Eduardo Ruíz Duarte (beck)
twitter: @toorandom

Teorema de Hasse para curvas elípticas, núcleo de la demostración pero desde el twist cuadrático de la curva 1/2

Vamos a explorar un teorema que es una consecuencia directa de las Conjeturas de Weil demostradas por Pierre Deligne, si nos da tiempo veremos un sketch de como demostrar las conjeturas de André Weil en general.

El teorema de Hasse es muy importante en criptografía con curvas elípticas, ya que nos permite aproximar o incluso saber el número de elementos que tiene el grupo que forma una curva elíptica, este número de elementos en función del tamaño del campo finito, esto tiene aplicaciones a la ingeniería en la implementación, y también nos puede decir, si la curva es segura o no , es decir que su grupo no sea isomorfo a algo trivial.

El problema de la demostración de Helmut Hasse en 1936 es que es muy larga y complicada, aquí trataremos de dar los elementos necesarios, pero también extenderemos el teorema a otro espacio el cual nos permitirá analizar la estructura desde los endomorfismos de la curva.

Primero, trabajemos en un campos $latex \mathbb{F}_q$ con $latex q$ impar y con la forma de una curva elíptica $latex E$ en su forma reducida de Weierstrass, es decir $latex y^2 = x^3 + Ax + B$ , pero esta forma reducida de Weierstrass tiene el problema de que $latex j(E)=1728\equiv 0$ mod $latex 3$ lo que nos limita a trabajar con cierta familia (0) de curvas en característica 3, necesitamos que el $latex j$ invariante tome todos los valores de $latex \mathbb{F}_q$ entonces consideraremos las curvas $latex y^2 = x^3 + a_{2}x^2 + a_{4}x + a_6$ , pueden demostrar que el $latex j$ invariante de esta curva ya cubre todas las curvas elípticas de característica impar.

El teorema de Hasse dice.

Teorema (Helmut-Hasse, 1936): Sea $latex E$ una curva elíptica sobre un campo
$latex \mathbb{F}_q$, si $latex N_q$ representan el número de puntos de $latex E$ sobre $latex \mathbb{F}_q$ entonces:

$latex \mid N_q-(q+1)\mid \leq 2\sqrt{q}$

Este teorema se ve muy infensivo, pero no lo es... de hecho de manera preliminar podríamos comenzar a atacarlo

Si la ecuación de $latex E$ es $latex y^2 = x^3 + Ax +B =f(x)$ y $latex q$ es impar, entonces vamos a

suponer que el número de puntos que cumplen $latex f(x)$ están distribuidos uniformemente al ser evaluado $latex f$  $latex \forall x\in \mathbb{F}_q$ , por lo que tenemos que hay una raíz que es un punto de $latex E$ y como $latex q$ es impar, existen $latex \frac{q-1}{2}$ elementos que no son cuadrados en $latex \mathbb{F}^{*}_q$  lo que nos deja con los otros $latex \frac{q-1}{2}$ puntos que sí son cuadrados, pero hay 2 por cada uno ya que en $latex E$  tenemos $latex (\pm y)^2$ por lo que el valor esperado de $latex N_q$ es   $latex 1+2\frac{q-1}{2}=q$

Esto nos da la desviación de $latex N_q$ y nos muestra la parte izquierda de la desigualdad de hasse que es $latex \mid N_q-(q+1)\mid$ donde el $latex +1$ es porque se consideran los puntos de $latex \mathbb{F}_q$ sobre la linea proyectiva la cual tiene otro punto adicional en el infinito.

Teoría necesaria.

En el post anterior hablamos del anillo de endomorfismos de una curva, el j-invariante e isogenias.
Te recomiendo lo leas antes, aquí recordaremos algunas cosas pero si crees que falta algo, el artículo anterior tiene más detalles.




Sean $latex E_1, E_2$ dos curvas elípticas definidas sobre $latex \mathbb{K}$ y $latex \psi:E_1\rightarrow E_2$ un homomorfismo separable de curvas elípticas, es decir... que si consideramos el functor contravariante $latex \psi^{*}:\mathbb{K}(E_2)\rightarrow \mathbb{K}(E_1)$ que manda $latex f\mapsto f\circ \psi$ entonces $latex \mathbb{K}(E_1)/\psi^{*}\mathbb{K}(E_2)$ es una extensión de campos separable (i.e. los polinomios minimos de elementos de el campo grande con coeficientes en el campo chico no tienes raíces repetidas) , y definimos el grado del mapeo $latex \psi$ como:  $latex \partial\psi=[\mathbb{K}(E_1):\psi^{*}\mathbb{K}(E_2)]$



Motivación de la demostración de Hasse

Sea $latex \psi:E_1 \rightarrow E_2$ un morfismo separable entre curvas elípticas, tenemos que $latex \partial \psi=\sum_{P\in \psi^{-1}(Q)}e_{\psi}(P)$  $latex \forall Q\in E_2$ con $latex e_\psi(P)=\nu_P(\psi^{*}t_{\psi(P)})$ el índice de ramificación [Silverman II , 2.6a], ahora, si usamos [Silverman III 4.10 a,c] tenemos que $latex \psi$ es separable $latex \Rightarrow \psi$ no tiene ramificación lo que implica que $latex e_{\psi}(P)=1$, y como $latex \psi(P+Q)=\psi(P)+\psi(Q)$ es un homomorfismo de grupos tenemos que $latex \psi^{-1}(\infty_{E_2}) = Ker\psi \Rightarrow$  $latex \partial \psi=\sum_{P\in Ker\psi}e_\psi(P) = \sum_{P\in Ker\psi}1 =$ #$latex Ker\psi$


Sabiendo esto, podemos deducir algo interesante sobre la cardinalidad de la curva elíptica $latex E$, si usamos [Silverman III, 5.5] tenemos que si $latex \phi:E\rightarrow E$ es el endomorfismo de Frobenius que actúa en las coordenadas de los puntos elevándolos a la $latex q$ entonces el mapeo
$latex Id-\phi$ es separable y tenemos que $latex \phi(P)=P \Leftrightarrow P\in E(\mathbb{F}_q)$ y usando el párrafo anterior, $latex Ker(Id-\phi)$ consta de todos los puntos $latex \mathbb{F}_q$ racionales de la curva ya que se anulan con la identidad, lo que nos dice que $latex Ker(Id-\phi)=E(\mathbb{F}_q)$ por lo que igual con el párrafo anterior, $latex \partial(Id-\phi)=$#$latex E(\mathbb{F}_q)$



Me he tardado en escribir en mi blog, pero por ahora dejo sólo esta parte, después vamos a terminar la demostración, pero falta relacionar los morfismos de la curva elíptica con elementos de una torcedura cuadrática de la curva, y con eso, construiremos $latex Id-\phi$ pero visto desde puntos en otra curva definida sobre $latex \mathbb{F}_q(s,t)$ tal que $latex s^2 = f(t)$ es decir la misma curva $latex E$ será  $latex E^{TW}: f(t)y^2 = f(x)$ y los puntos equivalentes a la identidad y el mapeo de frobenius ahí serán $latex (t,1)$ y $latex (t^q,s^{\frac{q-1}{2}})$ , pero esto será después de establecer este isomorfismo $latex Mor_{\mathbb{F}_q}(E,E) \cong E^{TW}(\mathbb{F}_q(s,t)) \cong E(\mathbb{F}_q(s,t))$ el cual nos permitirá calcular la cardinalidad del Kernel que necesitamos mediante otra función entre puntos sobre la curva con puntos en el campo de funciones racionales utilizando el grado de los puntos Id y Frobenius (los puntos ya no son numeros... son cocientes de polinomios en la torcedura cuadrática).


Espero les haya servido.

j-invariante y anillo de endomorfismos de curvas elípticas (isogenias)

Ahora, estoy dedicándome a explorar el anillo de endomorfismos de una curva elíptica $latex C$
sobre un campo perfecto (todo polinomio irreducible sobre este campo tenga raíces diferentes) para poder hablar de aplicaciones criptográficas.

Estos campos perfectos por excelencia en criptografía son $latex \mathbb{F}_q$.

Vamos a definir algunas cosas para clasificarlas, ya que anteriormente nos habíamos dedicado a estudiar cada curva por separado, pero ahora queremos considerar TODAS las curvas elípticas sobre un campo $latex \mathbb{K}$ , y ver cuáles son isomorfas, y ver cada clase de curvas isomorfas como la misma curva,  como un sólo punto, este espacio es una espacio modular, y generalmente es estudiado como un esquema.

Algo interesante es que en las curvas elípticas es que este espacio tiene dimensión 1, y de hecho es una linea topológicamente hablando.

Como sabemos, una curva elíptica tiene una estructura algebraica y una estructura geométrica, las curvas elípticas son el caso más simple de una variedad abeliana, éstas tienen dimensión 1 (Es decir, al considerar su anillo de coordenadas, su dimensión de Krull es 1, lo cual se traduce a que la cadena más grande de ideales por contención que se puede construir $latex \lbrace J_i \rbrace$ es de altura 1 por lo que $latex J_0 \subset J_1 \subset J_2$ tenemos que $latex J_1 = J_2$ lo que hace al anillo Noetheriano.

Vamos a explorar un poco lo que es una curva elíptica desde el punto de vista más formal, y construiremos relaciones de éstas, clasificaciones, y exploraremos cómo se comporta el anillo de morfismos de la curva en si misma, así como la relación que hay entre la traza y determinante de ciertos endomorfismos con el subgrupo de torsión de la curva en cuestión.


Curva suave de género 1, entonces es elíptica

Todas las curvas de género 1 son elípticas, como lo pueden ver en este post via el teorema de Riemann-Roch , y la construcción de la ecuación en la forma de Weierstrass ahora redefiniremos de una curva elíptica, recordemos que en la estructura algebraica de la curva siempre hay un punto distinguido que nos sirve como identidad visto como variedad abeliana, llamémoslo $latex \mathcal{O}$ , entonces si tenemos que una curva $latex E$ es suave de género g=1 y proyectiva , entonces por el teorema de Riemann-Roch tenemos que si $latex n>2g-2=0$ tenemos que $latex \mathcal{L}(n0)=n-g+2=n$  si $latex n=2$ y $latex n=3$ podemos encontrar dos funciones $latex x,y\in \mathbb{K}(E)$ que tienen exactamente 2 polos en $latex \mathcal{O}$ y $latex y$ tiene 3 polos en $latex \mathcal{O}$ , ahora si $latex n=6$, obtenemos una base para el espacio vectorial $latex \mathcal{L}(6\mathcal{O})$ la cual es $latex \lbrace 1,x,x^2,x^3,y,y^2,xy \rbrace$

La cual nos da la forma usual de la curva elíptica en la forma de Weierstrass como todos la conocemos.

$latex y^2 + f_1xy+f_3y = x^3+f_2x^2 + f_4x + f_6$

tal que $latex f_i \in \mathbb{K}$

Aquí fuimos de álgebra directamente a geometría.

Ahora, ya para geometrizar esto por completo, considera:

$latex \Phi: E \rightarrow \mathbb{P}^{2}_{\mathbb{K}}$
$latex (x,y) \mapsto [x:y:1]$

Ahora, también por lo anterior y Riemann-Roch tenemos que $latex [\mathbb{K}(E):\mathbb{K}(x)]=2$ y que $latex [\mathbb{K}(E):\mathbb{K}(y)]=3$ lo cual implica que $latex [\mathbb{K}(E):\mathbb{K}(x,y)]=1$, por lo que $latex \Phi$ tiene grado 1, como por hipótesis tenemos que $latex E$ es suave, sabemos que su discriminante $latex \Delta\neq 0$ ,  es decir $latex \Phi(\mathcal{O})=[0:1:0]=\infty$  es el punto al infinito.


Isogenias

La palabra "isogenia" no me gusta, pero no sé cómo traducirla, en inglés se dice "isogeny" , pero bueno, hay poca literatura en español sobre curvas isógenas (o no he buscado bien... o no he buscado más bien en español).

Lo que queremos hacer ahora es definir homomorfismos entre curvas elípticas, es decir queremos comenzar a compararlas de tal manera que ésta comparación respete sus propiedades geometricas y algebraicas.

Sean $latex E$ y $latex F$ dos curvas elípticas sobre $latex \mathbb{K}$ , una isogenia es un mapeo racional $latex \alpha: E\rightarrow F$ que induce homomorfismo de grupos de $latex E(\mathbb{K})$ y $latex F(\mathbb{K})$ (es decir entre los grupos abelianos inducidos por la curva elíptica)


Para entender esta definición, como ya lo había definido en el post antes citado en este post, vamos a redefinir lo que es un campo de funciones de una curva proyectiva en general para saber qué es un mapeo racional.

Sea $latex C(\mathbb{K})$ una curva proyectiva definida por $latex f(x,y,z)=0$ donde $latex f\in \mathbb{K}[x,y,z]$ es irreducible en $latex f\in \bar{\mathbb{K}}[x,y,z]$.

El campo de funciones $latex \mathbb{K}(C)$ son las funciones $latex g/h$ tal que

$latex g,h$ polinomios homogéneos del anillo $latex \mathbb{K}[x,y,z]$ de mismo grado
$latex h\notin (f)$  (el ideal generado por f)
$latex g_1/h_1$ y $latex g_2/h_2$ son equivalentes cuando $latex g_1h_2-g_2h_1 \in (f)$

Si te da miedo lo proyectivo, aquí te dejo la definición afín, pero debes trabajar proyectivamente, aquí te dejo un post anterior sobre el espacio proyectivo.

$latex \mathbb{K}(C)=Frac(\mathbb{K}[C])=Frac(\mathbb{K}[x,y]/(f))$

Decimos que un mapeo racional entre dos curvas proyectivas

$latex \Phi: E \rightarrow F$
$latex P\mapsto [\phi_x(P):\phi_y(P):\phi_z(P)]$

Tal que $latex \phi_i \in \mathbb{K}(E)$

Decimos que el mapeo es regular en $latex P\in E(\bar{\mathbb{K}})$  (puntos de E con coordenadas en la cerradura del campo) si existe $latex g\in\bar{\mathbb{K}}(E)$ tal que $latex [g\phi_x(P):g\phi_y(P):g\phi_z(P)]$ está bien definida y no todos son coordenada 0 ($latex [0:0:0] \notin \mathbb{P}^2$).


Si un mapeo es regular en todos los puntos, decimos que es un morfismo , puede verse en el libro Advanced topics in the arithmetic of elliptic curves (Silverman) que si $latex E$ es suave proyectiva, entonces todo mapeo racional de $latex E$ a una curva proyectiva $latex F$ es un morfismo.

Tambien decimos que un isomorfismo entre curvas elípticas es una isogenia invertible.

Como ejemplos que pueden trabajar en casa, consideren los mapeos sobre una curva $latex E$ sobre el campo $latex \mathbb{F_q}$  con $latex q=p^n$

$latex P\mapsto 2P$

Pueden demostrar que eso realmente es una isogenia

También
$latex \pi:E \rightarrow E$
$latex [x:y,z] \mapsto [x^q:y^q:z^q]$

Donde este mapeo es el endomorfismo de Frobenius y tenemos que
$latex \hat{\pi}:\mathbb{F}_q \rightarrow \mathbb{F}_q$
$latex x\mapsto x^p$

Este mapeo es muy importante , ya que es un automorfismo, y tenemos que

$latex \pi(\mathbb{F}_q)$ deja fijos a los elementos $latex \mathbb{F}_p$


Ahora queremos representar explícitamente las isogenias entre curvas elípticas.

Lema: Si $latex E$ y $latex F$ son curvas elípticas sobre $latex \mathbb{K}$  en su forma estándar de Weierstrass (como en los ejemplos) y si $latex \alpha$ es una isogenia no trivial, entonces tiene la siguiente forma:

$latex \alpha(x,y)=\Big( \frac{u(x)}{v(x)} , \frac{s(x)}{t(x)}y \Big )$

donde

$latex u,v,s,t \in \bar{\mathbb{K}}[x]$

y las fracciones están reducidas (numerador y cocientes son primos relativos)


Esto es fácil demotrarlo, te dejo los hints porque es mucha talacha para que tú lo hagas.

Considera lo que ya sabemos, supón que $latex \alpha$ está definido por el mapeo racional $latex [\alpha_x:\alpha_y:\alpha_z]$, y considera para todo punto afín

$latex [x:y:1] \in E(\bar{\mathbb{K}})$

$latex \alpha(x,y)=\Big ( r_1(x,y), r_2(x,y) \Big )$  donde $latex r_1(x,y)=\alpha_x(x,y,1)/\alpha_z(x,y,1)$ y $latex r_2(x,y)=\alpha_y(x,y,1)/\alpha_z(x,y,1)$

utilizando la relación de $latex E$ que ya conoces entre $latex x,y$ que es $latex y^2=x^3+ax+b$ elimina los factores $latex y^n$ y reescribe $latex r_1(x,y)=\frac{p_1(x)+p_2(x)y}{p_3(x)+p_4(x)y}$, multiplica el numerador y denominador por $latex p_3(x)-p_4(x)y$ y vuelve a reducir los $latex y^n$

Eso te dara otra versión de $latex \alpha$ que también tiene $latex y$, pero considera la simetría de la curva y el inverso de los puntos... sabes que $latex \alpha(x,-y)=-\alpha(x,y)$ por lo que deben haber cosas que se hagan 0, el argumento en $latex \alpha_y$ es similar.

El grado de una isogenia se define bajo esta representación tan cómoda como $latex \partial(\alpha):=max\lbrace u,v\rbrace$, y decimos que la isogenia $latex \alpha$ es separable si la derivada de $latex \frac{u}{v}$ NO es la función 0

El grado jugara un papel importante para despues definir otras cosas y jugar con la funcion zeta elíptica y el teorema de Hasse.

Corolario-Definición

Si $latex \alpha(x,y)$ es una isogenia como en el lema pasado, $latex v,t$ tienen las mismas raíces, y justamente estas raíces corresponden al kernel de $latex \alpha$



Teorema-Definición: Sea $latex \alpha: E\rightarrow F$ una isogenia con $latex \partial(\alpha)=n$ separable, entonces existe una única isogenia $latex \hat\alpha:F\rightarrow E$ tal que $latex \hat\alpha \circ \alpha = [n]$ , y le llamamos isogenia dual de $latex \mathbb{\alpha}$


Cosas que se pueden demostrar es que si $latex \alpha:E\rightarrow F$ y $latex \beta:E\rightarrow F$ entonces $latex \hat{\alpha+\beta}=\hat\alpha+\hat\beta$ y que $latex \alpha + \hat\alpha = 1 + \partial(\alpha)-\partial(1-\alpha)$, lo cual nos lleva a que definamos la traza  de un endomorfismo

$latex tr(\alpha)=tr(\hat\alpha)=\alpha+\hat\alpha$

Nota que tenemos que $latex \alpha\cdot \hat\alpha=[\partial(\alpha)]$ (en la misma curva elíptica) por lo que $latex \partial(\hat\alpha) = \partial(\alpha)$

Lo anterior nos lleva a un teorema importante que nos relaciona con un polinomio cuadrático cada endomorfismo.

Teorema: 

Sea $latex \alpha \in End_\mathbb{K}(E)$ , entonces $latex \alpha$ y $latex \hat\alpha$ son raíces del polinomio característico

$latex \xi(\lambda)=\lambda^2 - (tr\alpha)\lambda + \partial(\alpha) = 0$

Esto es muy fácil de probar

$latex \alpha^2 -(tr\alpha)\alpha+\partial(\alpha)=\alpha^2 - (\alpha+\hat\alpha)\alpha + \hat\alpha\alpha = 0$  lo mismo para $latex \hat\alpha$.

Ahora... como última parte de esta sección, consideremos el campo de caracteristica p y vamos a restringir los endomorfismos al subgrupo de torsión de la curva elíptica, es decir, sólo los evaluaremos en elementos de $latex E[n]$
y si $latex \alpha \in latex End(E)_\mathbb{K}$ a la restricción de $latex \alpha\mid_{E[n]}$ la redefiniremos como:

$latex \alpha_n$

Esta $latex \alpha_n$ es un endomorfismo del subgrupo abeliano $latex E[n]$ ya que $latex \alpha$ es un morfismo y manda puntos de torsión a puntos de torsión y como vimos anteriormente:

$latex E[n] \cong \mathbb{Z}/n\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, considera una base para $latex E[n]$ , llámale $latex (P_1,P_2)$

entonces podemos representar en forma de matriz a $latex \alpha_n=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ donde $latex a,b,c,d \in \mathbb{Z}/n\mathbb{Z}$ y $latex \alpha(P_1)=aP_1\oplus cP_2$ y $latex \alpha(P_2)=bP_1+dP_2$ , la representación de la matriz depende de la base, pero la traza  $latex tr \alpha_n$ y $latex det \alpha_n$ no.


Lo que nos deja con este teorema que es MUY importante, ya que es la conexión más importante que hay entre los endomorfismos y las restricciónes a $latex E[n]$


Teorema: 
Sea $latex \alpha \in End_\mathbb{K}(E)$ con $latex E$ elíptica sobre $latex \mathbb{K}$  y sea $latex n$ un número positivo primo relativo a la característica de $latex \mathbb{K}$

entonces:

$latex tr \alpha \equiv tr \alpha_n \bmod n$   y    $latex \partial(\alpha) \equiv det(\alpha_n) mod n$


Con esto ya estamos bien equipados.

j-Invariante

Ahora, ya que sabemos que todas las curvas de género 1 son elípticas, hay una manera de clasificarlas muy eficientemente, consideremos $latex \mathcal{E}$ como el espacio de todas las curvas elípticas sobre $latex \mathbb{K}$ , entonces existe una función

$latex j: \mathcal{E} \rightarrow \mathbb{K}$

Llamada j-invariante que cumple que:

$latex j(E)=j(F)\Leftrightarrow E \cong F$ sobre $latex \bar{\mathbb{K}}$

Se ha demostrado que la función $latex j$ es suprayectiva, por lo que $latex \mathbb{K}$ es el espacio modular de dimensión 1y tenemos que las fibras $latex j^{-1}(x)$ son clases de $latex \bar{\mathbb{K}}$-isomorfismos de curvas elípticas definidas sobre $latex \mathbb{K}$

Las curvas elípticas que generalmente usamos en criptografía son de la forma

$latex E:=y^2 - x^3 - px -q $

Por lo que podemos expresar el j-invariante de manera más reducida como:

$latex j(E)=1728 \frac{4p^3}{4p^3+27q^2}$

Torsiones cuadráticas de curvas elípticas

Aquí no voy a entrar tanto en detalle porque tengo poca experiencia pero es importante.

Imagina que tenemos las curvas $latex E$ y $latex F$ definids sobre $latex \mathbb{K}$ tal que existe un isomorfismo $latex E\rightarrow F$ sobre $latex \bar{\mathbb{K}}$ pero no sobre $latex \mathbb{K}$ , decimos en este caso que $latex E$ y $latex F$ son torsiones.

Ejemplo:

Considera las curvas $latex E:y^2=x^3+11664$ y $latex F:y^2=x^3+1$

Ambas suaves y lindas definidas sobre $latex \mathbb{Q}$ , estas curvas NO pueden ser isomorfas sobre $latex \mathbb{Q}$ ya que $latex F$ tiene un punto de orden 2 $latex (-1,0)$ y $latex E$ no tienen ningun punto de orden 2 (el punto de orden 2 en este caso como son simetricas son el eje x , tendria que se un punto de weierstrass, lo cual implica que x=0 por lo que $latex y\notin \mathbb{Q}$)

Pero ahora considera las curvas en la extensión cuadrática $latex \mathbb{Q}(\sqrt{2})$,
aquí podemos definir el isomorfismo:

$latex \Psi: E \rightarrow F$
$latex (x,y) \mapsto (2^3 3^6 \sqrt{2}\cdot x , 2^2 3^3\cdot y)$

Por lo que decimos que $latex E$ y $latex F$ son twists cuadráticos.

Por lo anterior... deberían de tener el mismo j-invariante, el cual es claramente 0, por lo que todas las curvas existentes con j-invariante 0 , serán isomorfas a estas que ejemplificamos en alguna extensión del campo en el que estén trabajando.


Subgrupo de torsión y endomorfismo de una curva elíptica

Sabemos que el mapeo que manda a multiplicar por $latex [n]$ los puntos de una curva $latex E$ es un morfismo, al kernel de este mapeo le llamamos subgrupo de torsión y lo denotamos como $latex E[n]$ , y tenemos el siguiente teorema cuando $latex K$ tiene caracteristica p

$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}\oplus \mathbb{Z}/n\mathbb{Z}$ si $latex p=0$ o $latex p\ndiv n$

o

$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}$ o $latex \lbrace 0\rbrace 0$  si $latex p>0$ y $latex n=p^m$

Qué corolario de este teorema pueden deducir de $latex E[p]$ ?

Pero lo que diremos es que en un campo de caracteristica positiva , si $latex E[p]\cong \mathbb{Z}/p\mathbb{Z}$ le llamamos a la curva $latex E$ ordinaria, y si es $latex E[p]\cong \lbrace 0\rbrace $ supersingular.

Ahora, aquí el anillo de Endomorfismos  de la curva $latex E$ los denotamos como $latex End_\mathbb{K}(E)$

y tenemos que las isogenias $latex \alpha:E\rightarrow E$ son endomorfismos, y forman un anillo

bajo las siguientes operaciones

$latex \alpha,\beta \in End_\mathbb{K}(E)$

$latex (\alpha + \beta)(P)=\alpha(P)\oplus\beta(P)$

$latex (\alpha\cdot \beta)(P)=(\alpha \circ \beta)(P)$

donde $latex \oplus$ es la adición elíptica .

Tenemos que ahora con esto podemos construir una infinidad de elementos ya que $latex [n] \ in End_\mathbb{K}(E)$

esto debería ser para ustedes pero lo pongo.

$latex (\alpha\cdot [n])(P)=\alpha(nP)=\alpha(\bigoplus_{i=1}^n {P}) = \bigoplus_{i=1}^n { \alpha(P) }=n\alpha(P)=([n]\cdot \alpha(P)$

Esto nos dice que $latex \mathbb{Z}$ es un subanillo de $latex End_\mathbb{K}(E)$ , lo puedes observar viendo como se comporta la composición y la suma de $latex [n]$ y $latex [m]$ , verás que forman un anillo esos endomorfismos y son isomorfos a $latex \mathbb{Z}$

Este anillo de endomorfismos no sólo tiene a $latex \mathbb{Z}$ , como vimos, también está el endomorfismo $latex \pi$ de Frobenius (con $latex \mathbb{K}$ de caracteristica p>0 como el caso de criptografía) y pues por lo tanto todas las composiciones y sumas de éste con los isomorfos a $latex \mathbb{Z}$ cuando la curva $latex E$ es supersingular, este anillo de endomorfismos se comporta como un álgebra de cuaternios y no es conmutativo.



Espero les haya interesado, cualquier duda o corrección háganmela saber

Eduardo Ruíz Duarte (beck)
Twitter: @toorandom