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

Normas y trazas de enteros algebraicos y polinomios característicos

Hoy quería recordar un poco de teoría de números analítica ya que a veces cuando tenemos un campo, queremos trabajar con los equivalente a sus "enteros" en analogía con $latex \mathbb{Q}$ y sus enteros $latex \mathbb{Z}$.

Entonces comencemos con la definición principal.

Definición: Un campo numérico $latex K$ es una extensión de campos algebraica finita de $latex \mathbb{Q}$

Esto quiere decir que $latex n=[K:\mathbb{Q}]<\infty$ es la dimensión del $latex \mathbb{Q}-$espacio vectorial $latex K$ , a $latex n$ nos referiremos como el grado de esta extensión.

El ejemplo por excelencia es:

$latex \mathbb{Q}(\sqrt{2}) = \lbrace x+y\sqrt{2} : x,y\in \mathbb{Q}\rbrace$

O también pueden considerar $latex \mathbb{Q}(\zeta_n)$ que es al adjuntarle una raíz $latex n-$ésima de  $latex 1$ (compleja), $latex \mathbb{R}$ no es un ejemplo de campo.

Ahora, si $latex \alpha\in K$ con $latex K$ de grado $latex n$ como $latex K$ es un $latex \mathbb{Q}-$espacio vectorial entonces existe una dependencia $latex \mathbb{Q}-$lineal entre $latex \lbrace 1,\alpha,...,\alpha^n\rbrace$ (ya que tiene dimensión $latex n$ y hay $latex n+1$ ahí), esto significa que existe un polinomio $latex f(x)\in \mathbb{Q}[x]$ tal que $latex f(\alpha)=0$ , si esto pasa decimos que $latex \alpha$ es un número algebraico y decimos que $latex \alpha$ es un entero algebraico si $latex \alpha$ es raíz de un polinomio mónico en $latex \mathbb[x]$.

Otro ejemplo obligatorio, es que $latex \sqrt{2}\in \mathbb{Q}(\sqrt{2})$ es un entero algebraico ya que es raíz es $latex x^2-2\in\mathbb{Z}[x]$ así como $latex i\in\mathbb{Q}(i)$ ya que es raíz de $latex x^2+1\in \mathbb{Z}[x]$, como es de esperarse $latex a/b\in\mathbb{Q}$ no son enteros (a menos que $latex b\mid a$ ya que no existe un polinomio mónico con coeficientes enteros que los tenga como raíz.

Hasta aquí hemos extendido un poco la definición de lo que es para nosotros un número entero en términos de la existencia de un polinomio mónico con coeficientes enteros.

Definición:  El polinomio mínimo de $latex \alpha\in K$ es un $latex f\in\mathbb{Q}[x]$ mónico, tal que $latex f(\alpha)=0$ y $latex f$ es de grado mínimo.

Es un buen ejercicio demostrar que $latex \alpha\in K$ es un entero algebraico si y sólo sí su polinomio mínimo tiene coeficientes enteros.

Si demostramos lo anterior tenemos que con todo esto.

Proposición: Los enteros algebraicos de $latex \mathbb{Q}$ son $latex \mathbb{Z}$

Esto también es fácil ya que si $latex a/b\in\mathbb{Q}$ entonces su mínimo polinomio es $latex x-a/b$ que por el ejercicio anterior sucede que $latex b\in\lbrace -1,1\rbrace$

Definición: Los enteros algebraicos de $latex K$ forman un anillo que lo denotamos como $latex \mathcal{O}_K$ y le llamamos anillo de enteros de $latex K$

El hecho de que $latex \mathcal{O}_K$ forma un anillo no es trivial, o sea, que la suma y producto de enteros algebraicos es un entero algebraico, pero tampoco es tan difícil , traten de visualizarlo con propiedades de sus polinomios moninos, y ver como pueden construir el polinomio monico que corresponde al producto y suma de dos números algebraicos, o también pueden demostrar que si $latex \alpha$ es un entero algebraico entonces $latex \mathbb{Z}[\alpha]$ es finitamente generado como grupo, es decir si $latex z\in \mathbb{Z}[\alpha]$ entonces $latex z=\sum_{i\leq m}z_i n_i$ es decir $latex \mathbb{Z}[\alpha]=\bigoplus_{i\leq m}\alpha^i \mathbb{Z}$.


Como un no-ejemplo tenemos a $latex \mathbb{Z}[\frac{1}{2}]$ está generado por todas las potencias de $latex \frac{1}{2}$ por lo que no es finitamente generado y su polinomio mínimo es $latex x-1/2$

Otros corolarios de esto son que $latex K=\mathbb{Q}\mathcal{O}_K

Normas y trazas de enteros algebraicos

Si $latex L/K$ es una extensión finita de campos numéricos y $latex \alpha\in L$ entonces el mapeo de multiplicación por $latex \alpha$ está dado por:

$latex \mu_\alpha:L\rightarrow L$
$latex x\mapsto \alpha x$

Esto es un mapeo $latex K$-lineal de $latex L$ a $latex L$ es decir un endomorfismo por lo que $latex \mu_\alpha\in End_K(L)$ $latex \forall \alpha\in L$

Como $latex \mu_\alpha \in End_K(L)$ entonces es una matriz y decimos que la norma y traza de $latex \alpha\in L$ están dadas por:

$latex N_{L/K}(\alpha)=det(\mu_\alpha)\in K$
$latex Tr_{L/K}(\alpha)=Tr(\mu_\alpha)\in K$ 

Tenemos que
$latex N_{L/K}(\alpha\beta)=N_{L/K}(\alpha)N_{L/K}(\beta)$
$latex Tr_{L/K}(\alpha+\beta)=Tr_{L/K}(\alpha)+Tr_{L/K}(\beta)$

por las propiedades de traza y determinantes usuales, por lo que si en particular $latex n=[L:K]$ y $latex a\in K$

$latex N_{L/K}(a\alpha)=a^n N_{L/K}$
$latex Tr_{L/K}(a\alpha)=aTr_{L/K}(\alpha)$

De hecho si $latex a\in K$ entonces $latex \mu_a$ si $latex \mathbb{I}$ es la matriz identidad entonces $latex \mu_a=a\mathbb{I}$.

También tenemos al polinomio característico de $latex \alpha\in L$ definido como:

$latex \chi(x)=det(\mathbb{I}x-\mu_\alpha)\in K[x]$ , donde es fácil ver que su término constante es $latex \pm N_{L/K}(\alpha)$ y el término de $latex x^{n-1}$ es $latex -Tr_{L/K}(\alpha)$ ya que $latex \chi(x)$ es un polinomio mónico de grado $latex n=[L:K]$


Es hora de un Ejemplo

Como lo hemos hecho $latex L=\mathbb{Q}(\sqrt{2})$ y $latex K=\mathbb{Q}$ entonces $latex 2=[L:K]$ por lo que podemos poner una base para el $latex \mathbb{Q}$ espacio vectorial $latex \mathbb{Q}(\sqrt{2})$ , la cual por simplicidad será $latex \lbrace 1,\sqrt{2} \rbrace$, entonces sea $latex \alpha \in \mathbb{Q}(\sqrt{2})$ , ahora calculemos $latex \mu_\alpha$ , tenemos que $latex \alpha = a+b\sqrt{2}$, para calcular la matriz, como vimos anteriormente $latex \mu_\alpha$ es un operador lineal , así que basta con aplicarlo a los elementos de la base para obtener su matriz.

$latex \mu_\alpha(1)=a+b\sqrt{2}$
$latex \mu_\alpha(\sqrt{2})=\sqrt{2}a+2b=2b+a\sqrt{2}$

Por lo que tenemos que:

$latex \mu_\alpha = \begin{pmatrix}a & 2b\\ b&a\end{pmatrix}=M_\alpha$

Ya que si $latex z=s+t\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ entonces

$latex M_\alpha \begin{pmatrix}s\\ t\end{pmatrix}=(as+2bt,bs+at)=as+2bt+(bs+at)\sqrt{2}$
$latex =(a+b\sqrt{2})(s+t\sqrt{2})=\alpha z =\mu_\alpha(z)$

Por lo que $latex N_{\mathbb{Q}(\sqrt{2})/\mathbb{Q}}(\alpha)=a^2-2b^2$ y $latex Tr_{\mathbb{Q}(\sqrt{2})/\mathbb{Q}}(\alpha)=2a$

Y el polinomio característico está dado por:

$latex \chi(x)=det \begin{pmatrix}x-a & -b\\ -2b&x-a\end{pmatrix}=x^2-2ax+a^2-2b^2$

$latex K$-monomorfismos a $latex \overline K=\mathbb{C}$

Para relacionar la traza y norma tenemos que existen  $latex n=[L:\mathbb{Q}]$ monomorfismos $latex \sigma_i:L\rightarrow \mathbb{C}$ , ya que si $latex L=K(\alpha)$ con $latex \alpha\in L$ entonces existe $latex f\in K[x]$ polinomio mínimo de $latex \alpha$ y es un resultado sabido que $latex f$ no tiene raices repetidas en $latex \overline{K}=\mathbb{C}$ por lo que tiene $latex n$ raíces diferentes, llamémosles $latex \alpha_i$ y definimos $latex \sigma_i(\alpha)=\alpha_i$, esto se puede demostrar para $latex K(\alpha,\beta)$ y en general por inducción.

Definición: Si $latex L/K$ es una extensión algebraica finita de grado $latex n$ entonces y $latex \alpha\in L$ con $latex \sigma_1, ..., \sigma_n$ los $latex K-$monomorfismos de $latex L$ a $latex \mathbb{C}$ entonces $latex \sigma_1(\alpha), ... , \sigma_n(\alpha)$ son los conjugados de $latex \alpha$

Teorema Sea $latex L/K$ una extension algebraica finita de grado $latex n$ y $latex \sigma_1, ..., \sigma_n$ los $latex K-$monomorfismos de $latex L$ a $latex \mathbb{C}$ que fijan $latex K$ entonces tenemos que para todo $latex \alpha\in L$

$latex N_{L/K}(\alpha)=\prod_{i=1}^{n}\sigma_i{\alpha}$
$latex Tr_{L/K}(\alpha)=\sum_{i=1}^{n}\sigma_i{\alpha}$


Esto se puede demostrar primero notando que si $latex \alpha\in L$ y $latex f\in K[x]$ es su polinomio mínimo, entonces:

$latex f(x)=\chi_{K(\alpha)/K}(x)$ y que por Cayley Hamilton $latex \chi_{K(\alpha)/K}(\mu_\alpha)=0$

Ejemplo

Sea $latex \mathbb{Q}(\sqrt{2})/\mathbb{Q}$ y $latex \alpha=a+b\sqrt{2}\in\mathbb{Q}(\sqrt{2})$ entonces:

$latex \sigma_1(a+b\sqrt{2})=a+b\sqrt{2}$
$latex \sigma_2(a+b\sqrt{2})=a-b\sqrt{2}$

Por lo que:

$latex N_{\mathbb{Q}(\sqrt{2})/\mathbb{Q}}(\alpha)=\sigma_1(a+b\sqrt{2})\sigma_2(a+b\sqrt{2})=a^2-2b^2$

y

$latex Tr_{\mathbb{Q}(\sqrt{2})/\mathbb{Q}}(\alpha)=\sigma_1(\alpha)+\sigma_2(\alpha)$


Que claramente da lo mismo que como lo calculamos anteriormente.

Queda para ustedes que calculen el polinomio característico de este caso, y que también consideren $latex \mathbb{Q}(i,\sqrt{2})$

Corolario  $latex N_{K/\mathbb{Q}}(\alpha)=\pm 1$ con $latex \alpha\in \mathcal{O}_K$ $latex \Leftrightarrow$ $latex \alpha$ es invertible

Eduardo Ruiz Duarte (beck)
twitter: @toorandom

Geometría p-ádica, completación de racionales y estructura de campo

¿Cómo podemos llegar a los números reales desde los números racionales?

Esta estructura es muy importante para estudiar muchos teoremas de geometría algebraica, y sirve como un ejemplo interesante ajeno a los campos usuales, todo estudiante de posgrado orientado a álgebra creo que debe conocerlos, aquí pongo una mini-introducción sólo para que te adentres más.


Tenemos que los números racionales son los cocientes de enteros, es decir:

$latex \mathbb{Q}=\Big \lbrace \frac{a}{b} : a,b\in\mathbb{Z}, b\neq 0 \Big \rbrace$

Ya sabemos como sumar y multiplicar fracciones, y sabemos que cada fracción tiene un inverso (excepto el 0) es decir, $latex (\mathbb{Q},+.\times)$ forma un campo.


Para entender los números p-ádicos necesitamos entender valores absolutos

Valores absolutos

Definición: Sea $latex \mathbb{K}$ un campo y $latex \mathbb{Q}_{+}=\big \lbrace x\in \mathbb{Q} : x\geq 0\big \rbrace$, entonces un valor absoluto en $latex \mathbb{K}$ es una función:

$latex \mid \cdot \mid:\mathbb{K}\rightarrow \mathbb{Q}_{+}$

Que satisface lo siguiente:


* $latex \mid x \mid = 0 \Leftrightarrow x=0$
* $latex \mid xy \mid = \mid x \mid \mid y \mid$
* $latex \mid x+y\mid \leq \mid x \mid + \mid y \mid$   (Desigualdad del triángulo)

Ejemplo usual:

Un valor absoluto para $latex \mathbb{Q}$ es:

$latex \mid \cdot \mid:\mathbb{Q}\rightarrow \mathbb{Q}_{+}$

$latex \mid x \mid =\begin{cases} \enspace x: & x\geq 0 \\ -x: & x < 0 \end{cases}$


Es fácil verificar que satisface las condiciones anteriores.


Ahora démosle más estructura al espacio, viendo cómo podemos comparar elementos.


Espacios Métricos

Decimos que una métrica es una función de distancia, es decir , si $latex \mathbb{X}$ es un conjunto entonces una métrica sobre $latex \mathbb{X}$ es una función:


$latex \delta:\mathbb{X}\times \mathbb{X} \rightarrow \mathbb{Q}_{+}$

Que satisface lo siguiente:

*$latex \delta(x,y)\geq 0$
*$latex \delta(x,y)=\delta(y,x)$
*$latex \delta(x,y)+\delta(y,z)\geq \delta(z,y)$ (desigualdad del triángulo)


Si se fijan hasta aquí, tenemos que si son observadores, $latex \mathbb{Q}$ forma un espacio métrico con la distancia usual , es decir:

$latex (\mathbb{Q},\mid \cdot \mid)$ es un espacio métrico , donde la métrica $latex \delta$ está definida usualmente como:

$latex \delta:\mathbb{Q}\times \mathbb{Q}\rightarrow \mathbb{Q}_{+}$
$latex \delta(x,y)=\mid x-y\mid$

Es decir la distancia que separa a los puntos $latex x,y\in \mathbb{Q}$

Para poder completar todos los huecos de $latex \mathbb{Q}$ necesitamos saber lo que son las sucesiones de Cauchy


Sucesiones de Cauchy


Una sucesión de Cauchy en un espacio métrico $latex \mathbb{X}$ es una sucesión de elementos $latex x_1,x_2,... \in \mathbb{X}$ de tal manera que cada uno de los elementos se van volviendo más cercanos conforme esta sucesión crece.

Es decir

$latex x_1,x_2,x_3,...$  es una sucesión de Cauchy si para todo número real positivo $latex \epsilon$ existe un entero $latex N$ de tal que para todos los números $latex n,m\in \mathbb{N}$ con $latex n,m > N$

$latex \delta(x_m,x_n)=\mid x_m -x_n\mid < \epsilon$



Esto quiere decir que siempre que se te ocurra cualquier real $latex \epsilon > 0$ por más chiquito que quieras, siempre podrás encontrar un índice $latex N$  donde todos los índices $latex n,m$ mayores que $latex N$ están a distancia menor que $latex \epsilon$


Puedes visualizarlo así... si se fijan los elementos $latex x_i$ se van juntando cada vez más y aunque escoja $latex \epsilon = \frac{1}{10^{100^{100}}}$ siempre sucederá que existe una $latex N$ que todos los elementos con índice mayor a $latex N$ están a distancia menor que $latex \epsilon$, entonces si una sucesión cumple esto, decimos que es de Cauchy, un ejemplo es $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$


$latex \mathbb{X}$




Ahora para juntar todo esto , veamos que es un espacio métrico completo.



Definición: Decimos que un espacio métrico $latex (\mathbb{X},d)$ es completo si toda sucesión de Cauchy en $latex (\mathbb{X},d)$ converge EN $latex \mathbb{X}$


Antiejemplos:

Es decir , por ejemplo si $latex \mathbb{X}=(0,1]$  vemos que la sucesión anterior $latex \Big \lbrace \frac{1}{n} \Big \rbrace_{n=1}^{\infty}$ converge a $latex 0\notin \mathbb{X}$ por lo que en este caso $latex \mathbb{X}$ no es completo.


Ahora... también tenemos que los números racionales con la métrica usual tampoco son completos es decir $latex (\mathbb{Q},\mid \cdot \mid)$

Es construir una sucesión de Cauchy en $latex \mathbb{Q}$ que no converja, por ejemplo.


$latex \Big \lbrace 3,3.1,3.14,3.141,3.1415,3.14159,3.14159295,...\Big \rbrace$


Esta claramente es una sucesión de números racionales que converge a $latex \pi \notin \mathbb{Q}$

Por lo que $latex \mathbb{Q}$ no es completo con la métrica usual


Ahora, Si un espacio no es completo, podemos completarlo agregando todos los límites de sucesiones de Cauchy de éste, y pueden probar que el completar un campo (en este caso $latex \mathbb{Q}$) el resultado les da otro campo (en este caso $latex \mathbb{R}$)


Resumen

Si quieres obtener $latex \mathbb{R}$ lo que necesitas es a $latex \mathbb{Q}$ , un valor absoluto en éste $latex \mid \cdot \mid$ , una métrica $latex \delta$ y todas las sucesiones de Cauchy en $latex \mathbb{Q}$ con respecto $latex \delta$


Otros Valores Absolutos  (p-ádicos)

Hasta ahora todo esto es lo usual y aburrido, la función de valor absoluto ya la conocemos perfectamente, lo que queremos hacer es usar otras funciones de valor absoluto y ver cómo se comportan estos espacios bajo una nueva métrica.


Fijemos un número primo $latex p$ , definiremos un valor absoluto asociado a $latex p$ en $latex \mathbb{Q}$

Sea $latex \alpha \in \mathbb{Q}^{\times}$ entonces tenemos que existen $latex g,h$ primos relativos tal que:

$latex \alpha = p^{n}\frac{g}{h}$

Es decir, todo número racional podemos verlo como múltiplo de $latex p^n$  donde $latex p$ no divide a ninguno de los $latex g,h$ , es decir todos son primos relativos.

Esto es fácil observarlo y demostrarlo, ahora vemos ejemplos , pero definimos el valor absoluto p-ádico para $latex \alpha \in \mathbb{Q}^{\times}$ como:

$latex \mid \alpha \mid_{p}=\mid p^{n}\frac{g}{h}\mid_p = p^{-n}$

Este es un valor absoluto no trivial y cumple todas las reglas de valor absoluto que definimos anteriormente con las leyes de los exponentes, hay que definir $latex \mid 0 \mid_p=0$ y hay que notar que el conjunto de valores absolutos es discreto ya que cae en el conjunto $latex \lbrace p^n : n\in \mathbb{Z}\rbrace \cup \lbrace 0 \rbrace$

Ejemplo:

Consideremos $latex \alpha = \frac{140}{297}=2^{2}\cdot 5 \cdot 7 \cdot 3^{-3} \cdot 11^{-1}$

Entonces:

$latex \mid \alpha \mid_2 = \frac{1}{4}$
$latex \mid \alpha \mid_3 = 27$

$latex \mid \alpha \mid_5 = \frac{1}{5}$

$latex \mid \alpha \mid_7 = \frac{1}{7}$

$latex \mid \alpha \mid_{11} = 11$

$latex \mid \alpha \mid_{13} = 1$

Métrica p-ádica en $latex \mathbb{Q}$

Naturalmente tenemos que la métrica p-ádica en los racionales definida como


$latex \delta_p:\mathbb{Q}\times\mathbb{Q} \rightarrow \mathbb{Q}_{+}$

está definida como

$latex \delta_p(x,y)=\mid x-y\mid_p$


Ejemplo contraintuitivo

Aquí las cosas no son tan intuitivas porque podemos ver que por ejemplo si $latex p=7$ $latex 28814$ y $latex 2$ están más cercanos que $latex 3$ y $latex 2$ ya que


$latex \delta_7(28814,2)=\mid 28812\mid_7 = \mid 2^2\times 3 \times 7^4\mid_7 = 7^{-4}=\frac{1}{2401}$

$latex \delta_7(3,2)=\mid 1 \mid_7 = \mid 7^0 \mid_7 = 7^0 = 1$

como $latex 1 > \frac{1}{2401}$ tenemos que $latex 3$ está más alejado del $latex 2$ que $latex 28814$



Completación de $latex \mathbb{Q}$ con la métrica p-ádica


$latex \mathbb{Q}$ no es completo con respecto a esta métrica, veamos un ejemplo

si $latex p=5$

$latex \displaystyle \sum_{n=0}^{\infty}{ 5^n}$

No es un elemento de $latex \mathbb{Q}$ pero ...

la sucesión:

$latex \lbrace 1,1+5,1+5+5^2, 1+5+5^2+5^3,...\rbrace = \lbrace 1,6,31,156\rbrace$

Es una sucesión de Cauchy con la métrica 5-ádica , esta sucesión con la métrica usual NO converge, pero con la métrica 5-ádica sí, de hecho las distancias van siendo $latex 1,\frac{1}{2},\frac{1}{4},\frac{1}{8}...$ .


Entonces para cada primo $latex p$ hay una completación de $latex \mathbb{Q}$ con respecto a su métrica p-ádica asociada

Entonces como sabemos que la completación del campo $latex \mathbb{Q}$ también será un campo.

y este objeto le llamamos campo de los números p-ádicos y lo denotamos como:

$latex \mathbb{Q}_p$

para algún primo $latex p$.

Representación de los números p-ádicos

Tenemos que todo número $latex x\in \mathbb{Q}_p$ puede ser representado como la serie de potencias:


$latex x_{-m}p^{-m}+x_{-m+1}p^{-m+1}+...+x_0+x_1p+x_2p^2+x_3p^3+...$


Esta representación es única cuando $latex x_i \in \mathbb{Z}/p\mathbb{Z}$ es decir , si $latex x_i$ está módulo $latex p$

La colección de las $latex \lbrace x_i \rbrace$ son los dígitos p-ádicos y la notación para escribirlos es de izquierda a derecha

$latex ...x_{3}x_{2}x_{1}x_{0} . x_{-1}x_{-2}...x_{-m+1}x_{-m}$


Geometría de $latex \mathbb{Q}_p$



Para finalizar vamos a ver cómo se ven las bolas de radio $latex r$ con centro en $latex a$ en $latex \mathbb{Q}_p$

es decir , queremos analizar estos objetos:

$latex B(a,r) = \lbrace x\in \mathbb{Q}_p : \mid a-x\mid_p < r\rbrace$


Como $latex r\in \lbrace p^n : n\in \mathbb{Z}$ si $latex p=3$ en $latex \mathbb{Q}_3$

Donde el círculo más grande tiene $latex r=1$ y los 3 circulitos que siguen tienen $latex r=1/3$ y así $latex r=1/3^n$

Pero si ponemos un microscopio, lo que veremos es:

que es como un arbol ternario.

Espero les haya servido, estos aparte de ser divertidos son bellos, ahora podríamos hablar en el futuro a detalle de topología con esto.

Eduardo Ruíz Duarte (beck)

twitter: @toorandom

Criptografía asimétrica combinatoria-algebraica no usual con bases de Gröbner

Siempre me ha gustado investigar estructuras algebraicas con el fin de poder ver si puedo sumergir criptografía asimétrica dura ahí, generalmente ésta basada en el problema de logaritmo discreto en curvas algebraicas; considero que es mi área favorita de trabajo y posiblemente a lo que me vaya a dedicar el resto de mi vida, pero aquí vamos a ver algo diferente que podría o no ser seguro en su implementación pero no deja de ser interesante.


Primero vamos a analizar un caso particular de un esquema de cifrado con polinomios y luego veremos cómo generalizarlo y definiendo con bases de Gröbner.

Vamos a utilizar cualquier $latex \mathbb{F}-algebra$ de tipo finito, i.e. finitamente generada, con grado de trascendencia $latex n$ veamos cómo funciona esto.

Construcción del algoritmo de cifrado:

Sea $latex \mathbb{F}$ un campo finito y $latex T=\lbrace t_{i}\rbrace_{i=1}^{n}$ un conjunto de variables.


Queremos que $latex A$ reciba un mensaje $latex m\in \mathbb{F}$ de $latex B$ cifrado.

• $latex A$ va a escoger un vector aleatorio $latex y\in \mathbb{F}^{n}$ como llave privada

• $latex A$ escoge polinomios como llave pública $latex P=\lbrace q_j \rbrace \subseteq \mathbb{F}[T]$ tal que $latex q_j(y)=0$ $latex \forall j$

         Es fácil generar polinomios con los ceros que necesitamos, por ejemplo si
         ya tenemos la llave privada $latex y$ tomas $latex q_j = \hat {q}_j - \hat{q}_j(y)$ con $latex \hat{q}_j \in \mathbb{F}[T]$.
         Lo que no es tan fácil es escogerlos seguros y álgebraicamente independientes, pero hay métodos.

•  $latex B$ quiere mandar el mensaje $latex m\in \mathbb{F}$ a $latex A$ por lo que se toma un elemento del ideal generado por la llave pública $latex P$ que es $latex (P) \subset \mathbb{F}[T]$:

   $latex p = \displaystyle \sum { h_j q_j } $

En otras palabras escoge $latex \lbrace h_j \rbrace \subset \mathbb{F}[T]$ y genera el polinomio $latex p$

• $latex B$ le manda a $latex A$ el polinomio multivariable        

$latex c=p+m$


Este esquema de cifrado funciona ya que $latex A$ va a poder obtener $latex m\in \mathbb{F}$ ya que conoce los ceros de los generadores del ideal $latex (P)\in \mathbb{F}[T]$ por lo tanto conoce los ceros de $latex p$ independientemente de los $latex \lbrace h_j \rbrace$ , por lo que usando su llave privada $latex y$ tenemos que $latex A$ puede calcular fácilmente

$latex c(y)=p(y)+m=m$


Nota que este esquema de cifrado es probabilístico y no determinístico, i.e. en cada
ocasión que se cifra $latex m$ es diferente ya que depende de los elementos del ideal de la llave pública que se tomen.

Su seguridad también depende de los ceros del conjunto algebraico generado por $latex B$, en este caso cada cero sería $latex y=(y_1,y_2,...,y_n)$ y cualquier cero en la intersección de las hipersuperficies funcionaría, su seguridad depende de la solución de sistemas de ecuaciones algebraicos no lineales de grado arbitrario , es decir, en dimensión grande y con un número grande de polinomios generadores independientes del ideal de la llave pública, es POSIBLE tener criptografía segura, digo posible porque no se ha demostrado que su solución NO sea en tiempo polinomial, pero creo que podría ser más seguro si usamos la teoría de bases de Gröbner.

Generalización:

Veamos unas definiciones que vienen de la teoría de bases de Gröbner para poder intentar una generalización, las cuales incluyen la reducción módulo otro polinomio multivariable, donde los monomios deberán estar ordenados bajo cierto orden lexicográfico.

Definición (módulo polinomio multivariable): Decimos que $latex f$ reduce a $latex h$ módulo $latex g$ parcialmente si $latex a_{i}X^{i}$ es un monomio de $latex f$ que es divisible por el término líder de $latex g$ ,$latex lt(g)$ (líder bajo el órden con el que organicemos nuestros polinomios como el lexicográfico por grado) y que sucede que:

$latex h=f-\frac{a_{i}X^{i}}{lt(g)}g$

Donde escribimos que $latex f \equiv h \bmod g$

Definición (módulo un conjunto de polinomios): Sea $latex G=\lbrace g_1,...,g_l \rbrace \subset \mathbb{F}[T]$ y sea $latex f\in \mathbb{F}[T]$, entonces decimos que $latex f$ se reduce a $latex h$ módulo $latex G$ ($latex f \equiv h \bmod G$) si tenemos la sucesión $latex h_0=f, ..., h_k=h$ tal que $latex h_j \equiv h_{j+1} \bmod g$ para algún $latex g\in G$

Definición (base de Gröbner): Sea $latex F=\lbrace g_1, ..., g_l \rbrace \subset \mathbb{F}[T]$ un conjunto finito de polinomios en $latex m=|T|$ variables e $latex I\subset \mathbb{F}[T]$ el ideal generado por $latex F$, decimos que $latex F$ es una base de Gröbner para el ideal $latex I$ si para todo $latex 0\neq f\in I$ se tiene que $latex lt(g_k)\mid lt(f)$ para algún $latex g_k\in F$


Teorema: F es una base de Gröbner para un ideal $latex I\subset \mathbb{F}[T]$ $latex \Leftrightarrow$ $latex \forall f \in I$ $latex f\equiv 0 \bmod F$

Con este último teorema nos resulta TRIVIAL el poder construir ideales aleatorios (finitos, anillos noetherianos) y su base de Gröbner asociada.

Regresando al esquema de cifrado original y rehaciéndolo con esto:

$latex A$ escoge una base de Gröbner $latex G=\lbrace g_1,...,g_l\rbrace$ de un ideal $latex I \subset \mathbb{F}[T]$, la llave privada de $latex A$ es $latex G$.

Sea $latex S\subset \mathbb{F}[T]$ el conjunto de TODOS los polinomios que no pueden ser reducidos módulo $latex G$ (ve las definiciones anteriores), este $latex S$ realmente sería el conjunto de representantes del anillo $latex \mathbb{F}[T]/I$ como ya se lo habrán imaginado, ahora supón que $latex S$ es público, aunque $latex G$ no lo sea, tenemos que todo mensaje $latex m \in \mathbb{F}$ es un elemento de $latex S$.

Un ejemplo:


 Sea $latex T=\lbrace t_1,...,t_n\rbrace$ y $latex y \in \mathbb{F}^n$ un punto secreto, $latex A$ toma como base de gröbner $latex G=\lbrace t_1-y_1, ..., t_n - y_n\rbrace$  en este caso tenemos que $latex S=\mathbb{F}[T]/(G)\cong \mathbb{F}$ es el campo de las constantes.

Ahora $latex A$ escoge un conjunto como llave pública $latex P=\lbrace q_j \rbrace \subset I=(G)$, esto es fácil ya que  podría tomar un $latex \hat{q}_j\in \mathbb{F}[T]$ arbitrario y calcular $latex q_j = \hat{q}_j - \overline{q}_j$ donde $latex \overline{q}_j \in S$ y $latex \hat{q}_j \equiv \overline{q}_j \bmod G$

Consideremos el ideal $latex J=(P)$ y $latex m\in S$, entonces $latex B$ le cifrará a $latex A$ el mensaje $latex m$ escogiendo al azar un elemento de $latex J$, ya que la llave pública de $latex A$ es $latex P$ y $latex J=(P)$:

$latex p=\displaystyle \sum h_{j}q{j} \in J$

$latex B$ le manda a $latex A$ $latex c=p+m$

$latex A$ al recibir $latex c$ sólo tendría que reducirlo módulo la base de Gröbner $latex G$ 

En este ejemplo cuando $latex G=\lbrace t_i - y_i \rbrace$ sería el caso particular que vimos en el principio.


Esta criptografía es rara y no es usada ni considerada AÚN SEGURA debido a que falta demostrar que tan dificil es el problema en términos de complejidad.


Espero les haya gustado

Eduardo Ruíz Duarte (beck)
@toorandom

Álgebra de votaciones para procesos electorales

Últimamente se ha hecho una modita el rechazar elecciones electrónicas por razones las cuales siento que carecen de fundamentos.

Hice una presentación la cual no fue del todo aprovechada ya que donde lo iba a exponer no sirvió el proyector, pero tambien expongo un punto de vista distinto al usual para realizar votaciones electrónicas (con criptografía y no con solo contadores electrónicos y cables), como valor agregado obviamente salvarás millones de árboles.

En el documento no toco temas socio-políticos los cuales son los que causan polémica, sino tres algoritmos necesarios para

poder realizar un proceso electoral electrónico.

Este documento puede ser un poco complicado, así que a manera de resumen explico los tres algoritmos:


1.Zero-Knowledge: Este algoritmo permitirá a una persona A poderle demostrar a B que A conoce un secreto "s" y B quedará totalmente convencido de que "s" existe pero sin que A haya revelado s, solamente a B se le revelara la veracidad de la existencia de "s". (Se utiliza el problema de logaritmo discreto), un poco mas técnico, el algoritmo podrá mostrarle a B que A posee una llave que abre un mensaje sin que el mensaje sea revelado ni la llave.
Un ejemplo que luego ocupo para explicar es: "¿Cómo puedo convencerte de que realmente si tengo la receta de la coca-cola para que me la pagues primero y luego te la de?"

2. Shamir threshold: Este algoritmo permitirá que N personas tengan un "pedazo" de secreto "s" y que si k personas (k menor que s) se juntan puedan reconstruir el secreto "s" de tal manera que los pedazos de secreto nunca podrán construirse a partir k-1 personas.

Por ejemplo, imaginen que una bóveda es de 10 personas, pero por alguna extraña razón quieren que si se juntan cualesquiera 3 personas de esos 10 puedan abrirla. La bóveda tiene un password y este solo se puede construir cuando se juntan 3 personas y no menos. (Este algoritmo utiliza polinomios de Lagrange)


3. Diffie-Hellman

¿Cómo podemos negociar una llave secreta dos personas aunque haya un tercero oyendo TODA nuestra negociación?
Esto utiliza logaritmo discreto.

Y por ultimo utilizando Elgamal se simula un esquema de votación de en el conjunto {-1,1} (si o no) , esto es suficiente ya que si hay mas candidatos es como hacer (a,b) o c es ( (a,b), c) (suma directa) .


Como les digo, aquí no discuto la honradez o la educación de la banda para poder votar, sino que hipotéticamente es posible y es seguro.

Con este esquema los votantes podrían hacer lo siguiente:

1. Checar que su voto realmente fue contado
2. Checar que su voto fue contado por quién ellos eligieron
3. Sufragio total, solo el votante puede verificar el punto 2 (todo esto protegido con criptografía asimétrica y certificados)
4. Los votantes pueden contar los votos y quedar convencidos de que el conteo no fué truqueado

A diferencia de los esquemas habituales (Brasil , Australia, Estados Unidos) , con criptografía se pueden asegurar cosas.

y no solamente incrementar un contador como lo ha sido en esos paises. Con criptografía se puede hacer que realmente el voto sea secreto, efectivo y robusto ante tramposos.


Les dejo la liga: aquí


Saludos Eduardo Ruiz Duarte (beck)