Wednesday, April 19, 2017

Why finding big prime numbers? why study weird arithmetic sequences?

Now I am sitting on my desk thinking on a technique to help me to identify BIG prime numbers in certain arithmetic sequences using algebraic geometry.

This is part of my last project for my PhD, which I think will be very interesting. When I say "BIG" I mean thousands of digits, maybe millions.  When I say "primes in arithmetic sequences" I mean to separate prime numbers in a list like $latex \{ \alpha_n \}_{n=0}^\infty$.

A popular, a prostituted, an important and a "dumb" sequence.

Now we will describe some non trivial sequences and we will see a glimpse of why they are important (or not).

This is of course in my opinion, since there are infinitely many sequences which I ignore and could be more interesting. In fact there is a sequence of "uninteresting numbers" which contains all numbers which appear to not have known/interesting properties (like being prime, Mersenne prime, triangular number, cube, etc...).
But well, this sequence then..., is interesting as is unique, and then we get a paradox.

The popular sequence

The popular is a very famous arithmetic sequence, and is the "Mersenne Sequence", $latex \{ 2^n-1\}_{n=1}^\infty\subset\mathbb{N}$.

$latex \{ 2,7,15,31,63,127,255,...\}$

This is the sequence of all Mersenne numbers.  We denote by $latex M_n$ to the number $latex 2^n-1$.
To identify the primes in this sequence, note that if $latex n=2k$ (is even) then $latex 2^n-1=(2^k-1)(2^k+1)$ and hence... not a prime number. This means that in the sequence we can discard all the values $latex n\in 2\mathbb{Z}$, that is $latex M_{2k}$ is not prime. A less trivial fact is that if $latex n$ is composite, namely $latex n=ab$ then we have that:

 $latex 2^n-1=2^{ab}-1=(2^a-1)(\sum_{k=0}^{b-1}2^{ka})=(2^b-1)(\sum_{k=0}^{a-1}2^{kb})$

and then also $latex M_{pq}$ is not prime. So, we are left with all the elements in the sequence of the form $latex M_p$ for $latex p$ a prime number. A quick inspection says that $latex M_2, M_3, M_5, M_7$ are Mersenne primes. But $latex M_{11} = 2047 =23\cdot 89$ which is not prime. So, which Mersenne numbers are prime ?

This is a difficult question, there are big computer grids working in this, trying to find the most spectacular prime. The biggest Mersenne prime known, (and Biggest Prime in general) is $latex 2^{74207281}-1$. which has 22.3 million digits approximately. The way to check it without putting so much effort in the algebraic geometric or number theory rigor is the following:

 To check that $latex 2^p -1$ is prime:

Consider the sequence $latex \{ \sigma_1=4, \sigma_2=14,...,\sigma_j=(\sigma_{j-1}^2)-2...\}$
then $latex M_p=2^p-1$ is prime if and only if $latex \sigma_{p-1}\equiv 0 \bmod M_p$.

This is the fastest way known today. is called the Lucas-Lehmer test.
There are other elegant tests (but not necessarily faster) using elliptic curves which I knew its existence when I was talking with Benedict Gross at the conference on L-Functions at Harvard the past year, and in some sense I have to do something similar as part of my PhD program.

The prostituted

Another famous and prostituted sequence is the so called "Fibonacci sequence".

$latex \{ 1,1,2,3,5,8,13,...,F_{n-1}+F_{n-2}, ...\} $

This is famous and is always presented as the building blocks of beauty in the universe. This just an exaggeration, but well, that is another story.

Is known that $latex \lim_{n\to\infty} \frac{F_{n}}{F_{n-1}}=\phi=1.618033...$.

This number $latex \phi$ has the property that squared is equal to $latex \phi+1$ so, is appears as a root of the polynomial $latex x^2 -x -1=0$.
The value of $latex \phi$ can be found when you divide lengths of middle lines in some polygons by the length of the sides. Also in your body, if you divide your height by the distance of your feet to your belly button, and in a lot of parts of our body. This number can be analyzed in a Leonardo da Vinci drawing called "Le proporzioni del corpo umano secondo Vitruvio" which can be seen here.
This is why $latex \phi$ has some kind of mystic and esoteric significance for some people, and that is why is called sometimes The Golden Ratio. 

To identify primes in the Fibonacci sequence, there are no good ways. This is mainly because the sequence highly depends on the "addition" operation and not "multiplication", and believe it or not, addition in number theory is a mystery.
A very important Conjecture in mathematics about this mystery, predicts the possible relation between the multiplication and the addition of integers, through its prime factorization, called the abc conjecture, so Fibonacci, is difficult as a problem in terms of primality, but as seen, has more significance in geometry.

The important sequence

Now for the important sequence is this

$latex \{2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344...\}$

Do you see it?

Well, is not too easy to see, is called the "Hardy-Ramanujan sequence", if you denote by $latex \tau(n)$ the $latex n^{th}$ element of the sequence, it means that $latex \tau(n)$ can be written in $latex n$ different ways as a sum of two cubes. Fermat Proved that there are infinitely many of these numbers hundreds of years before, but they caught the attention of Hardy by Ramanujan in a very nice story.

When Ramanujan was dying at the hospital in England, Hardy went to visit him. Hardy told him that the number in his taxi to the hospital was a dull, boring number, 1729. Ramanujan said:

 'No, Hardy, it is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways' 

That is why we use the letter $latex \tau$ because these numbers are called "taxicab numbers" because of this story.

The importance of these numbers, is the new theory in arithmetic geometry that arose,  which in fact I am very interested personally, and professionally.

Practically Ramanujan discovered in his way of thinking, an integral solution to the equation $latex x^3+y^3=z^3+w^3$ which nowadays is studied over $latex \mathbb{Q}$ and then twisted.
This kind of surfaces are called K3 Surfaces (Kodaira-Kummer-Kahler, smooth minimal complete surface with trivial canonical bundle), there is no smart way of obtaining these numbers other than using this algebraic geometry in these surfaces. An example of these surfaces with a family of rational curves parametrized  (the curves may contain taxicab solutions in it) is:


And yeah 1729 has the desired property, that is, $latex \tau(2)$ is a sum of two cubes in only two different ways. 
Srnivasa Ramanujan was a human computer, in fact to verify this, we check for the $latex \tau(2)=1729$ and $latex \tau(6)=24153319581254312065344$ can be written as the sum of 2 cubes in 2 and 6 different ways respectively:

$latex \begin{matrix}\tau(2)&=&1729&=&1^3 + 12^3 \\&&&=&9^3 + 10^3\end{matrix}$
$latex \begin{matrix}\tau(6)&=&24153319581254312065344&=&582162^3 + 28906206^3 \\&&&=&3064173^3 + 28894803^3 \\&&&=&8519281^3 + 28657487^3 \\&&&=&16218068^3 + 27093208^3 \\&&&=&17492496^3 + 26590452^3 \\&&&=&18289922^3 + 26224366^3\end{matrix}$

The "dumb" sequence

There are plenty other sequences, for example, there are some "dumb" sequences that at the end... they are not so dumb, for example, consider the following sequence:

$latex \{1, 11, 21, 1211, 111221, 312211, 13112221, ... \}$

Do you see the pattern?

Well, the pattern is visual, you begin with "1" and then the following will be the "description of the previous", that is, you ask yourself "What symbols are in the preceding element of the sequence?", and you say "one one" (11) then the next is "two ones"  (21), and so on... This sequence is called "look and say sequence".

There are a lot of things you can do in your spare time with this sequence, for example, prove that a "4" cannot appear in any element of the sequence. The number 13112221 is in fact the biggest prime known in this sequence, are there others?

This apparently dumb sequence has an amazing property which transforms it from dumb to analytic and it was due to John Conway.
Consider the $latex k^{th}$ element of that sequence, call it $latex a_k$  , and define $latex \ell(a_k)=$number of digits of $latex a_k$.
Is proved that $latex \lim_{n\to\infty} \frac{\ell(a_k)}{\ell(a_{k-1})}=\lambda=1.303577269034...$. The surprising thing is that $latex \lambda$ is an algebraic number that can be found as a root of a polynomial of degree 71. This was proved by John Conway, for more information, look at wikipedia.

But why?, why you want to find big primes or classify properties of sequences?

 I have been questioned plenty of times "Why you want to find big primes?", today was one of these days where a master student asked me.
There is a FALSE answer which is very popular among a lot of people, namely

 "It has cryptographic applications, since prime numbers are the basis for today's e-commerce and the development of cryptographic schemes" 

This is false, since cryptographic schemes for public key cryptography need prime numbers with no more than 1000 decimal digits (and this is already too long). Using more than 1000 digits maybe would be more secure, but the speed will decrease exponentially, that is why you don't use 1 million bits of security.

 Identifying these "cryptographic" prime numbers at random with certain properties (Like being a Sophie-Germain prime) to generate a public key with 4096 bits which has approx 1234 digits, (which is already paranoid for the public techniques of cryptanalysis) takes less than a second in my workstation (try: time openssl genrsa 4096).
 So, cryptography is not a good excuse to generate BIG prime numbers, when I say big, I mean thousands of digits, millions.

The answer in my case is easy... To collect them...  they are difficult to find, but they are present in a lot of shapes, for example in the last sequence, which elements are prime ? which is the biggest known ? how to identify them with geometric techniques?.

That is how the theory in mathematics is born, with a question regarding classification.

So, finding big primes is difficult, so is valuable, there are only 49 Mersenne Primes and nobody has proved that they are infinite. (but is believed heuristically that they are).

A couple of years ago I wrote here about finding a big prime of the form $latex 3\cdot 8^n -1$ , which I found here, there are a lot of possible primes disguised in infinitely many shapes, you could just define whatever recursive relation and analyze it.

Other people could say to test a big cluster, or to get some money (yes you get money if you break the records). Maybe an analytic number theorist could say To understand more the distribution of prime numbers which is unknown.


So well in conclusion, I think is good to collect primes and analyze sequences. This to find something hidden in the unknown nature of the logic of sequences of natural numbers, since, we don't know yet how the prime numbers arise. There is still a mystery of how the prime numbers are distributed among all the natural numbers,  even with quantum computers is hard to find them arbitrarily large, so there are still work to do in mathematics.

For more information of all the known published sequences (yes, whatever you think will be there) go to, this is the Online Encyclopedia of Integer Sequences.

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

Wednesday, September 21, 2016

Dominios de factorización única, enteros Gaussianos y números de Heegner

Recientemente alguien me preguntó algo sobre factorización en anillos y unidades de los anillos, y decidí hacer un post sobre esto, esto es un post básico podría decirse de álgebra conmutativa.

Este post pretende que se comprenda el concepto de factorización en general en cualquier anillo numérico (extensión algebraica de $latex \mathbb{Z}$) a través de ejemplos y explorar, comprender y demostrar propiedades de la factorización de los enteros extendidos con una constante imaginaria (enteros gaussianos).

Todos conocemos el anillo $latex \mathbb{Z}$ que consiste en todos los enteros, y sabemos que los enteros son un subanillo de los números racionales $latex \mathbb{Q}$.

¿Qué es ser entero?, es decir, conocemos el caso particular mencionado anteriormente pero como vimos un  post pasado, hay otros campos que podemos extender.

Lo que queremos investigar es el fenómeno de "factorización única", es decir, en $latex \mathbb{Z}$ no es es muy natural decir que todo entero se puede factorizar en primos de manera única salvo permutación. Pero vamos a ver cómo el concepto de elemento primo es aún más general.

Definición: Un anillo $latex R$ conmutativo le llamamos dominio entero  si cuando ab=0 para $latex a,b\in R$ tenemos que $latex a=0$ o $latex b=0$.
También decimos que un elemento $latex u\in R$ es una unidad si tiene un inverso bajo la multiplicación del anillo $latex R$ , es decir, si existe un $latex u^{-1}$ tal que $latex uu^{-1}=1$. Siempre que todo elemento no cero de $latex R$ sea unidad, diremos que $latex R$ es un campo.

Aquí tenemos que el ejemplo usual $latex \mathbb{Z}$ es un dominio y sus únicos elementos invertibles son el $latex 1,-1$

Otra definición importante es la de irreducibilidad.

Definición: Sea $latex R$ un dominio y $latex a,b\in R$ , $latex a\mid b$ si existe un $latex c$ tal que $latex b=ac$ , es decir $latex a$ divide a $latex b$.  Un elemento no cero $latex p\in R$ es irreducible si no es unidad y si siempre que $latex a\mid p$ tenemos que $latex a$ es una unidad o $latex a=up$ para alguna unidad $latex u$.

Noten que si una unidad la podemos factorizar entonces todo factor debe ser también una unidad, por ejemplo si $latex u=ab$ entonces $latex abu^{-1}=1$ entonces $latex bu^{-1}$ debe ser un inverso de $latex a$ .

Con esto ya tenemos lo necesario para poder definir lo que es factorización única.

Definición: Un dominio $latex R$ tiene factorización única si todo elemento no cero $latex a\in R$ puede ser escrito de manera única como

$latex a=u\prod p_i^{d_i}$

Donde $latex u$ es una unidad y los $latex p_i$ son urreducibles. Nota que uso la palabra irreducible en vez de "primo", en general no son lo mismo, sólo significan lo mismo en los enteros, ya que todo irreducible es primo, pero veremos ejemplos donde no lo es.

Si un anillo cumple la definición única le diremos DFU (Dominio de factorización única)


* Los enteros $latex \mathbb{Z}$ son un dominio que no es un campo y sus únicas unidades son el 1 y -1, un entero es irreducible sí y sólo si es un número primo o un número primo negativo. Una consecuencia del teorema fundamental de la aritmética es justamente que $latex \mathbb{Z}$ es un DFU.

* Los campos $latex \mathbb{Q}$ y $latex \mathbb{R}$ son campos, y éstos no tienen irreducibles, por lo tanto son trivialmente un DFU.

*Una familia infinita de dominios la podemos construir si tomamos un entero $latex n\in \mathbb{Z}$ que no sea cuadrado

$latex \mathbb{Z}[\sqrt{n}]=\lbrace a+b\sqrt{n}:a,b\in\mathbb{Z} \rbrace$.

Vamos a profundizar en uno en especial en la siguiente sección cuando $latex n=-1$.

Enteros Gaussianos

Si $latex n=-1$ tenemos la colección de números complejos $latex a+bi$ con $latex a,b\in \mathbb{Z}$, imagínen los puntos de plano complejo o de $latex \mathbb{R}^2$ que tienen coordenadas enteras, es decir una retícula que asemeja cuadrados.

Estos enteros son muy importantes, son $latex \mathbb{Z}[i]$

Estos enteros son como $latex \mathbb{Z}$ pero con algunas cosas raras adicionales, ya que hay más unidades aparte del 1 y -1, también tenemos a $latex i$ y $latex -i$ ya que $latex i\cdot (-i)=1$ .

También tenemos que $latex 2$ es irreducible como un entero en $latex \mathbb{Z}$ pero no como un entero gaussiano en $latex \mathbb{Z}[i]$ ya que $latex 2=(1+i)(1-i)$.

De hecho si un número primo $latex p=a^2 + b^2$ es decir es suma de enteros cuadrados, entonces p no es irreducible como un entero Gaussiano, ya que siempre va a poder factorizarse como $latex p=(a+bi)(a-bi)$. (**)

Vamos a definir lo que es la norma en un anillo en general, pero por ahora, sólo la definiremos para estos enteros que es $latex N(a+bi)=|a+bi|^{2}=a^2 + b^2$, es decir $latex N:\mathbb{Z}[i]\to \mathbb{Z}^{+}$.

La propiedad importante de la norma es que $latex N(wz)=N(w)N(z)$ lo que implica que si $latex u$ es una unidad entonces
$latex 1=N(1)=N(uu^{-1})=N(u)N(u^{-1})$ y como $latex N(u)$ debe ser un entero no negativo por como está definida la norma entonces debe ser 1 forzosamente, por lo que toda unidad tiene norma 1.

 Ahora vamos a examinar la propiedad (**), si $latex p$ es un primo y supongamos que podemos factorizarlo de manera no trivial como $latex p=wz$ en $latex \mathbb{Z}[i]$ , entonces usando la norma sabemos que $latex N(p)=p^2$ por la definición de norma, pero también sabemos que p=wz por lo que $latex N(p)=N(w)N(z)$ por lo que $latex p^2=N(w)N(z)$, como la factorización es no trivial, tenemos que $latex N(w)$ y $latex N(z)$ no son 1 por lo que $latex w,z$ no son unidades, y esto implica que $latex N(w)=N(z)=p$  por lo que si $latex w=\alpha+\beta i$ entonces $latex N(w)=\alpha^2 + \beta^2 = p$ por lo que $latex p$ es suma de dos cuadrados.

Bueno con lo anterior, vemos el poder de la norma, de hecho nos permite diferenciar irreducibles en $latex \mathbb{Z}[i]$ ya que para todo factor $latex p$ de un entero $latex n$ si $latex p$ no es suma de dos cuadrados entonces es irreducible, y si $latex p=a^2  + b^2$ entonces podemos sustituir en la factorización de $latex n$ a las $latex p$ por $latex (a+bi)(a-bi)$ y cada uno de estos factores es irreducible.

Un dato interesante de los enteros gaussianos es que también es un DFU y de hecho con la norma podemos darnos cuenta de toda la factorización en $latex \mathbb{Z}[i]$ ya que todos los irreducibles son los primos $latex p$ que no son suma de dos cuadrados así como todos los $latex a\pm bi$ tal que $latex a^2+b^2$ es un número primo. Para mostrar lo último considera $latex z=a+bi \in \mathbb{Z}[i]$ entonces $latex N(z)=a^2+b^2=z\bar{z}$ (su conjugado) . Como $latex N(z)$ es un entero normal positivo, y sabemos que en $latex \mathbb{Z}$ hay factorización única por lo que todo factor irreducible de $latex z$ debe ser factor de $latex N(z)$  por lo que si $latex N(z)=a^2+b^2$ es primo es irreducible.

¿Quiénes no son DFU?

¿Y qué?, ¿Cuándo no es DFU?,

Para mostrar eso formalmente debería introducir un grupo especial, que se llama grupo de clases de ideales asociado a un anillo, pero eso terminaría con la naturaleza elemental de este post, pero pronto lo haré en una siguiente sección, éste consiste en el cociente del grupo de ideales fraccionarios del campo de fracciones del anillo $latex R$ módulo los ideales principales de $latex R$, este grupo está íntimamente asociado al grupo de Picard de orden 0 de una curva algebraica que se estudia mucho en criptografía pero se ve de manera más "fácil" esto es la generalización pero eso es otro tema.

Hay un problema en matemáticas que estudian los grupos de clases de ideales para saber cuándo hay o no factorización única, de hecho eso lo mide el grupo de clases de ideales en sus elementos ( el area de matemáticas es class field theory), por ejemplo algo raro es que $latex \mathbb{Z}[\sqrt{-5}]$ NO es DFU, pero si consideramos los anillos con raiz cuadrada de $latex n$ que son $latex \mathbb{Z}[\sqrt{-n}]$ para $latex n\in \lbrace 1,2,3,7,11,19,43,67,163 \rbrace$ estos son los ÚNICOS enteros cuya raíz cuadrada imaginaria nos forman un dominio de factorización única, es decir para -5 o -13 no tenemos la propiedad de DFU, y de hecho lo que sucede es que el Class Group asociado al anillo es trivial (tiene un sólo elemento) sí y sólo si el anillo es un DFU.

Esto fue conjeturado por Gauss, probado con errores por Heegner y formalizado por Baker y Stark, de hecho estos 9 números raritos se llaman Números de Heegner.

Esto es impresionante ¿no? , es decir, qué tienen de raro esos 9 números que nos forman anillos con factorización única que otros números primos no puedan hacer... ¿qué hay en la geometría de estas retículas?

Espero les haya gustado

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

Saturday, August 27, 2016

Criptografía asimétrica con curvas elípticas isógenas súpersingulares resistentes a ataques cuánticos

Poco a poco la criptografía como la conocemos está desapareciendo, he hablado con Tanja Lange un par de veces en los congresos que hace la sociedad matemática holandesa y ella parece insistir mucho que estamos ya muy cerca presenciar la existencia de una computadora cuántica, ella afirma que entre el 2024-2030 ya existirá alguna.

Lo relevante es que toda la criptografía actual implementada en los ámbitos económicos, militares y gubernamentales, cuenta con seguridad extrema ante computo clásico como lo conocemos (modelos Von Neumann, Turing...) . El problema es que el modelo de cómputo cuántico rompe todos los algoritmos implementados hoy en día. Esto es debido a la existencia de un algoritmo por Peter Shor que factoriza y calcula logaritmos discretos, es decir, rompe RSA y criptografía basada en el problema de logaritmo discreto (Curvas elípticas) en tiempo polinomial. Esto significará que todos seríamos vulnerables ante el individuo/organización que construya computadora cuántica (IBM, DWave, Google por ejemplo).

Por lo que, las curvas elípticas e hiperelípticas como las implementamos hoy en día, comienzan a ser obsoletas en criptografía, aunque siguen siendo muy útiles para computación en teoría de números algebraica que sirve para hacer nuevos algoritmos, es decir, no estoy diciendo que ya no sirvan las curvas, sino que la criptografía que usa el problema de logaritmo discreto con curvas o variedades abelianas está vulnerado ante la presencia de una computadora cuántica.

En este post les voy a mostrar un análogo de Diffie Hellman que no es vulnerable ante la presencia de un atacante con recursos cuánticos. El post es autocontenido, sólo requieres saber la teoría básica de curvas elípticas la cual la puedes leer en mi blog, recomiendo (aunque no es obligatorio ya que trato de hacerlo autocontenido leer estos artículos aquí en mi blog antes)

Teorema de Hasse en curvas elípticas
Álgebras de endomorfismos en curvas elípticas
j-Invariante en curvas elípticas

El método de Diffie Hellman que funciona bajo cómputo cuántico que describiremos aquí necesita conocimiento de morfismos entre curvas elípticas (isogenias u homomorfismos de los grupos abelianos inducidos por las curvas).
El contenido de este post es el siguiente:

* Background en isogenias y kérneles de éstas antes de irse a lo cuántico.
* Grado de una isogenia
* p-Torsión, j-invariante y características de curvas elípticas súpersingulares
* Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.
* Algoritmo explítico Diffie Hellman con isogenias entre curvas elípticas supersingulares.
* ¿Pero por qué nos enfocamos en súpersingulares?
* ¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis?

Todo esto que escribo fue gracias a la emoción que me causaron las pláticas de Dimitar Jetchev (EPFL, Lausanne, Suiza), Frederik Vercauteren (KU Leuven, Bélgica), Benjamin Smith (INRIA, Francia) y René Schoof (Università di Roma, Italia) en el workshop "Mathematical structures for cryptography" el cual tuve la suerte de poder trabajar con grandes matemáticos del 22-26 de Agosto en Leiden, Países Bajos cuyo objetivo era juntar investigadores en matemáticas y criptografía para resolver problemas abiertos en esta teoría así como la basada en retículas para cómputo cuántico (Lattice Based Cryptography), todos los participantes aportamos algo interesante, y fue una de las más grandes experiencias profesionales que he tenido, aquí hay más información de la gente involucrada


Background en isogenias y kérneles de éstas antes de irse a lo cuántico.

Sea $latex E$ una curva elíptica en forma de Weierstrass sobre un campo finito $latex \mathbb{F}_q$ , es decir $latex E:=\lbrace (x,y)\in \mathbb{F}_q\times\mathbb{F}_q : y^2 = x^3 + ax + b \rbrace$.

Como he explicado en posts anteriores, las curvas elípticas forman un grupo abeliano, es decir, $latex \langle E,\oplus\rangle$ es una estructura donde los puntos se pueden "sumar y restar" , es conmutativa, todos tienen inverso aditivo, es asociativa, cerrada y con elemento neutro $latex \infty$.

Hay fórmulas explícitas para calcular la suma de puntos como en el post anterior mencionado en el párrafo anterior, y también están muy bien explicadas en wikipedia, así que supondré que ya sabemos como funciona la adición elíptica que geométricamente la intuición es con la siguiente imagen:

Isogenias entre curvas 
(mapeos de curvas elípticas, homomorfismos de grupos abelianos inducidos)

Tenemos que si $latex \langle E_1, \oplus\rangle ,\langle E_2,\boxplus \rangle$ son dos curvas elípticas y existe un morfismo $latex \psi:E_1\to E_2$ que respeta la estructura de grupo de cada una, es decir $latex \psi(P\oplus Q)= \phi(P)\boxplus \phi(Q)$ y que mapea el $latex 0$ de una al $latex 0$ de la otra, entonces decimos que ambas son isógenas.

Ahora vamos a ver qué son esos ceros en la curva, ya que no es trivial desde el punto de vista afín.

Kérnel de isogenias

En curvas elípticas tenemos que una isogenia entre dos curvas se ve como $latex \psi(x,y) := (\frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} )$ donde más técnicamente es porque $latex \frac{a_1(x)}{a_2(x)}, \frac{yb_1(x)}{b_2(x)} \in \mathbb{F}_q(E_2)$ es decir son funciones bien definidas en los puntos de la curva en el codominio, son funciones de su campo de funciones (campo de fracciones de la gavilla de funciones del la curva vista como esquema).

Para entender el kérnel de un mapeo como el anterior, necesitamos ver la curva de manera proyectiva, ya que el 0 (cero) en $latex E_1$ y $latex E_2$ no es un punto afín.

Si $latex \psi:E_1\to E_2$ es una isogenia entre curvas elípticas, el kérnel está definido como:

$latex ker\psi := \lbrace P\in E_1 : \psi(P) = \infty_{E_2}\rbrace$

Es decir, todos los puntos que nos mandan al infinito.

Recuerden que las curvas son proyectivas, entonces lo que esto significa exactamente es que si la isogenia está definida por $latex (\frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)})$ entonces podemos proyectivizar estas ecuaciones con una nueva variable $latex z$ (cerradura proyectiva), los puntos que el mapeo manda al infinito veremos a continuación que son justamente donde no están definidas esas funciones racionales sin proyectivizar.

Informalmente pero no incorrectamente, definir la imagen de estos puntos "no definidos bajo $latex \phi$" como $latex \infty_{E_2}$ se hace, deshaciéndose de los denominadores en la isogenia y homogeneizando, eso será la isogenia vista en la cerradura proyectiva de la curva que es $latex zy^2 = x^3 + az^2x + bz^3$ .

Entonces tendremos que los puntos afines de la cerradura proyectiva de la curva están dados por los puntos $latex (x:y:1)$ , es decir, la imagen afín de $latex \psi$ es  $latex (\frac{a_1(x)}{a_2(x)}:y\frac{b_1(x)}{b_2(x)}:1)$ , por lo que entonces la ecuación proyectiva es: $latex (a_1(x)b_2(x):yb_1(x)a_2(x):a_2(x)b_2(x))$ , y todos los puntos $latex (x:y:1)$ donde no está definida la curva afín, justamente estarán bien definidos aquí proyectivamente y esos puntos, son los que tienen imagen al infinito , es decir, que tienen como imagen el punto $latex \infty := (0:1:0)$, y son los puntos en el $latex ker\psi$ incluyendo al $latex \infty_{E_1}$ ya que es requisito de una isogenia mapear infinitos.

Pueden ustedes demostrar de hecho que $latex ker\psi := \lbrace (x,y)\in E_1 : a_2(x)=0\rbrace$ con el hint de que $latex a_2^3 \mid b_2^2$ siempre, y así como que $latex b_2^2\mid f_1a_1^3$ donde $latex f_1$ es la ecuación que define a $latex E_1$ en $latex y^2 = x^3 + a_1x + b_1$, recuerden que esto lo demuestran en el campo de funciones de la curva, es decir tienen que tomar en cuenta la ecuación de la curva al momento de demostrar esto.

Teorema: Si dos curvas elípticas son isógenas sobre un campo finito, entonces tienen el mismo número de puntos.

Grado de una isogenia

Antes de demostrar el teorema, necesitamos entender qué es el grado de una isogenia.

Sea $latex \psi:E_1\to E_2$ una isogenia definida sobre un campo finito $latex \mathbb{F}_q$.

Decimos que el mapeo $latex \psi$ es separable si la extensión de los campos inducida por $latex \mathbb{\psi}$ es separable.

Es decir si $latex \mathbb{F}(E_1)/\psi^{*}\mathbb{F}_q(E_1)$ es separable, y su dimensión como espacio vectorial la usamos para definir:

$latex \text{grad}\psi := dim_{\mathbb{F}_q}(\mathbb{F}_q(E_1)/\psi^{*}\mathbb{F}_q(E_1))=[\mathbb{F}(E_1):\psi^{*}\mathbb{F}_q(E_1)]$

Si esta extensión de campos inducida por $latex \psi$ es separable, decimos que es $latex \psi$ es separable, y una propiedad de isogenias separables es que $latex \text{grad}\psi :=$#$latex ker\psi$.

Pero que no cunda el pánico, vamos a ver cómo encontrar este grado sin meternos en la teoría dura, esto sólo es para definir algo (grado) y luego ver que su cálculo se puede hacer sin tener que calcular bases de espacios vectoriales.

Es fácil demostrar que el grado de la extensión de campos se mide siempre de una manera inocente contando el número de elementos en la imagen inversa de cualquier punto (sin ramificación) en el codominio.

O sea si el grado de $latex \psi$ fuera 1, significa que los espacios vectoriales inducidos por $latex \psi$ son los mismos, por lo que la imagen inversa de cualquier punto tiene sólo 1 punto ya que en este caso $latex \psi$ sería un isomorfismo.

El grado mide qué tan "complejo" es $latex \psi$ , por lo que de hecho el grado de una isogenia está definido también por la cantidad de elementos en la imágen inversa de $latex \psi$ para un punto ordinario general, es decir de $latex \psi^{-1}(Q_{E_2})$ donde $latex Q_{E_2}\in E_2$ es un punto ordinario, es decir no presenta ramificación (Por ejemplo un punto $latex (x,y)$ cuya coordenada $latex x$ no sea raíz de $latex x^3 + ax + b$ , ya que estos puntos son de ramificación, pero no entraremos en eso por ahora).

Como $latex \psi$ es un homomorfismos, tenemos que #$latex \psi^{-1}(Q_{E_2}) =$#$latex ker\psi$, por lo que tenemos otra igualdad más.

De tarea ustedes entonces dicho lo anterior pueden probar que $latex \text{grad}\psi$ es fácilmente calculable ya que si $latex P\in E_1$ y $latex Q:=\psi(P)$ es un punto con coordenadas $latex (s,t)$ en $latex E_2$ entonces #$latex \psi^{-1}(Q)$ es exactamente el número de ceros diferentes del polinomio $latex a_1(x)-sa_2(x)$ pero como $latex \psi$ es separable entonces este polinomio no tendrá raíces repetidas, por lo que #$latex \text{grad}\psi = \text{Deg}(a_1(x)-sa_2(x))=$#$latex ker\psi$.

Demostración de teorema

Dicho todo esto, considera el mapeo $latex \phi_1\in End_{\mathbb{F}_q}(E_1)$ y $latex \phi_2\in End_{\mathbb{F}_q}(E_2)$ tal que si $latex (x_i,y_i) \in E_i$ entonces $latex \phi_i(x_i,y_i) = (x_i^q, y_i^q)$ .

Es decir son los endomorfismos de Frobenius de cada una de las curvas.

Recuerden que queremos demostrar que dos curvas $latex E_1,E_2$ isógenas sobre $latex \mathbb{F}_q$ tienen el mismo números de puntos, y tenemos que la isogenia es $latex \psi:E_1\to E_2$.

Es fácil ver que $latex \psi\circ \phi_1 = \phi_2\circ \psi$, ya que si $latex P:=(x_1,y_1)\in E_1$ y $latex (x_2,y_2):=\phi(P)$ entonces $latex \psi(\phi_1(P)) = \psi(x_1^q,y_1^q)$ y en el otro lado $latex \phi_2(\psi(P)) = \phi_2(x_2,y_2)=(x_2^q,y_2^q)$.

Es decir, en el párrafo anterior afirmo que  $latex (x_2^q,y_2^q) = \psi(x_1^q,y_1^q)$, ya que recuerden que $latex \psi$ está formada por funciones racionales en $latex x$ y en $latex y$, entonces es un ejercicio de álgebra básica demostrar que si $latex r(x)$ es un polinomio sobre un campo finito entonces $latex r^q(x)=r(x^q)$, es decir se cumple el sueño de todo niño de secundaria, que por ejemplo si $latex x+y\in \mathbb{F}_q(x,y)$ entonces $latex \phi(x+y)=(x+y)^q = x^q + y^q$.

Entonces con toda mi informalidad que me caracteriza, tenemos ya que $latex \psi\circ \phi_1 = \phi_2\circ \psi$

Por lo que como la operación $latex \circ$ de composición en $latex End_{\mathbb{F}_q}(E_i)$ es distributiva, podemos inferir que:

$latex \psi\circ (\mathbbm{1}_{E_1} - \phi_1) = (\mathbbm{1}_{E_2}- \phi_2)\circ \psi$   (*)

Tal que $latex \mathbbm{1}_{E_i}$ es el mapeo de identidad en $latex End_{\mathbb{F}_q}(E_i)$ .

Calculemos el grado de  (*) .

Sabemos que el $latex \text{grad}\psi_1\circ \psi_2 = \text{grad}\psi_1\cdot \text{grad}\psi_2$ , esto lo pueden demostrar usando mi demostración anterior de que el grado de una isogenia está directamente relacionado con el grado de un polinomio dado por el mapeo, y pues al componerlos, el grado incrementa multiplicativamente.

También tenemos que el grado de $latex \mathbbm{1}_{E_i}-\phi_i$, como es un mapeo separable, es el número de elementos en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$... Pregunta ¿quién está en el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$?

Recordemos que el endomorfismo de Frobenius tiene una propiedad interesante, es decir, si tenemos que $latex \mathbb{F}_{p^n}$ es un campo finito, y definimos para todo $latex x\in \mathbb{F}_{p^n}$ el mapeo $latex \phi_m(x) := x^{p^m}$ entonces $latex \phi_m(x)=x$ sí y sólo sí $latex x\in \mathbb{F}_{q^m}$ por lo que $latex x\in \overline{\mathbb{F}_p}$  es $latex \mathbb{F}_{p^m}$-racional si $latex \phi_m(x)=x$ , es decir, donde el endomorfismo de Frobenius se comporta como la identidad, nos caracteriza a los puntos racionales.

Entonces el kernel de $latex \mathbbm{1}_{E_i}-\phi_i$ son los puntos $latex (x_i,y_i)\in E_i$ que son iguales ante Frobenius y ante la identidad... es decir, puntos racionales $latex \mathbb{F}_q$-racionales.

Con lo anterior tenemos que  $latex \text{grad} (\mathbbm{1}_{E_i}-\phi_i)=$#$latex E_i$ .
Con esto tenemos tenemos que el grado de (*) es:

$latex \text{grad}\psi\cdot$#$latex E_1 = \text{grad}\psi\cdot$#$latex E_2$ por lo que #$latex E_1=$#$latex E_2$. q.e.d. $latex \blacksquare$.

p-Torsión, j-invariante y características de curvas elípticas súpersingulares

Definición: $latex E/\mathbb{F}_{p^n}$ una curva elíptica, entonces definimos la n-torsión de la curva como:

$latex E[n] := \lbrace P\in E : nP=\infty \rbrace$

Es decir, los puntos que al sumarse $latex n$ veces, se anulan.

Definición: Sea $latex E/\mathbb{F}_{p^n}$ entonces decimos que $latex E$ es ordinaria si $latex E[p]\cong \mathbb{Z}/(p)$ y es supersingular si $latex E[p]\cong\lbrace\infty\rbrace$.

Es decir, si no tiene p-torsión más que la trivial, le llamamos supersingular.

La palabra "supersingular" no tiene nada que ver con "singular", ya que una curva es singular si tiene singularidades, pero una curva elíptica por definición no es singular, es decir, no tiene puntos raros (discriminante de la curva es distinto de cero), ni tampoco raices repetidas.

La palabra supersingular es porque realmente son excepcionales,  y de hecho una cosa interesante de estas curvas es que SIEMPRE están bien definidas sobre $latex \mathbb{F}_{p^2}$ para cualquier $latex p$ , es decir, al reducir una ecuación de una curva a $latex \mathbb{F}_{p^2}$ nunca presentará singularidades.

Ahora vamos a ver otra definición importante que justamente será usada por el protocolo Diffie-Hellman.

Definición: Definimos el j-invariante de una curva elíptica $latex E/k$ donde $latex k$ es cualquier campo de caracteristica mayor que 3 y la forma de Weierstrass de $latex E$ es $latex y^2=x^3 + ax+b$ lo definimos como:

$latex j(E):=1728 \frac{4a^3}{4a^3+27b^2}$

Esta función loquita es muy importante en análisis complejo, y se preguntarán de donde sale ese 1728. Primero necesitamos saber para qué es esto.

El j-invariante tiene la propiedad de que si dos curvas tienen el mismo j-invariante, es decir $latex j(E_1)=j(E_2)$ entonces tenemos que $latex E_1\cong E_2$ sobre su campo de definición $latex k$.

Noten que el denominador del j-invariante nunca es 0, ya que es justamente el discriminante de $latex x^3 + ax+b$ y este no es cero porque sino la curva tendría singularidades y por definición una curva elíptica no es singular.

Otro teorema importante es que para todo $latex j_0\in k$ existe una curva elíptica $latex E_{j_0}$ tal que $latex j(E_{j_0})$ por lo que automáticamente podemos inferir que sobre cualquier campo... el moduli de TODAS las curvas elípticas sobre cualquier campo finito o infinito... es unidimensional... es decir, todas las curvas elípticas forman una línea.

Otros teoremas importantes es que los endomorfismos extendidos a $latex \mathbb{Q}$ definido como $latex End_0(E):= End_k(E)\otimes_{k}\mathbb{Q}$ cuando $latex E$ es supersingular, forman una álgebra de cuaternios, es decir no es conmutativa.

En el caso ordinario donde $latex E$ no sea supersingular , tenemos que $latex End_0(E)$ siempre es una extensión cuadrática de $latex Q$ compleja, es decir $latex End_0(E)\cong \mathbb{Q}(\sqrt{d})$  con $latex d$ negativo y libre de cuadrados.

Corolario: Sea $latex E/\mathbb{F}_q$ una curva elíptica supersingular, entonces #$latexE(\mathbb{F}_q)=p+1$.


No lo haré, pero usen el teorema de Hasse, deduzcan que si la curva es supersingular, entonces la traza del endomorfismo de frobenius es 0, todo esto se puede demostrar con lo anterior.

Teorema: Sea $latex \psi:E_1\to E_2$ una isogenia tal que $latex E_1$ es súpersingular, entonces $latex E_2$ también es supersingular.

Lo mismo aplica para curvas ordinarias, es decir, los dos tipos de curvas, súpersingulares y ordinarias sólo "se llevan" entre sus respectivas categorías, esto es importante, porque el protocolo que describiré pronto asegura que todas las isogenias serán entre curvas súpersingulares.

Pero antes veamos cómo construir isogenias cuyo kernel sea el subgrupo del dominio de la isogenia, es decir, dado un $latex H_P\subset E$ un subgrupo de una curva elíptica sobre un campo finito, en este caso $latex H_P$ es el generado por $latex P$ , construiremos explícitamente $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P=H_P$ y la ecuación explícita de $latex E_P$.

Construyendo Isogenias desde subgrupos de la curva usando fórmulas de Velú.

Recuerden que #$latex E(\mathbb{F}_q)=N$ es finito, ya que el campo de definición es finito.
Entonces por el teorema de lagrange, sabemos que la información de sus subgrupos está escondida en la factorización de $latex N$.

Sea $latex P\in E$, definimos el subgrupo $latex H_P\subsetneq E$ como:

$latex H_P:=\lbrace nP : n \in \mathbb{Z}\rbrace$

Este es el grupo de "todos los múltiplos de $latex P$:" en la curva, es trivial que es un subgrupo de $latex E$.

Vamos ahora a construir una isogenia asociada a $latex P\in E$ que denotamos por $latex \psi_P$ cuyo kernel sea $latex H_P$ hacia otra curva que denotaremos como $latex E_P$.

Es decir vamos a construir $latex \psi_P:E\to E_P$ tal que $latex ker\psi_P = H_P$
Todos sabemos que el kérnel de un morfismo de grupos es un subgrupo normal del grupo, así que esto no debe causarles conflicto.

La notación de las coordenadas para los puntos en $latex \langle E,\oplus\rangle$  será $latex P:=(x_P,y_P), Q:=(x_Q,y_Q), P\oplus Q:=(x_{P+Q},y_{P+Q})$.

Definición-Teorema-Vélu: Sea $latex \langle E/\mathbb{F}_q,\oplus\rangle$ una curva elíptica y $latex P_0\in E$, tal que $latex y^2 = x^3 + ax + b$ construyamos como vimos anteriormente el grupo generado por los "múltiplos de $latex P_0$" , $latex H_{P_0}$.

Entonces tenemos que para todo $latex P\notin H_{P_0}$:

$latex \psi_{P_0}:E\to E_{P_0}$
           $latex P\mapsto \Big( x_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(x_{P+Q}-x_Q), y_P+\displaystyle\sum_{Q\in H_{P_0}\setminus\lbrace\infty\rbrace}(y_{P+Q}-y_Q)\Big)$

Y si $latex P\in H_{P_0}$ definimos $latex \psi_{P_0}(P)=\infty$.

Es fácil mostrar que $latex ker\psi_{P_0}:=H_{P_0}$ , de hecho, ústedes háganlo y verán como todo se reduce a hacer matemáticas lindas, no es tan difícil.

Pero bueno, esta función $latex \psi_{P_0}$ no está dada por la forma que mostrarmos al principio, es decir por la isogenia definida con los polinomios $latex \big( \frac{a_1(x)}{a_2(x)},y\frac{b_1(x)}{b_2(x)} \big)$.

Pero Dustim Moody y Daniel Shumow ya lo hicieron en la sección 2.3 de un paper, aquí dejo su páper , así que ya tenemos la isogenia explícita, y de hecho en ese mismo paper se describe la ecuación de la curva $latex E_{P_0}$ la cual es $latex y^2 = x^3 + (a-5v)x + (b-7w)$ donde $latex v,w$ son constantes que dependen de $latex H_{P_0}$ y son explícitamente calculables.

Ahora sí, el algoritmo

Algoritmo explícito Diffie Hellman con isogenias entre curvas elípticas supersingulares.

Considera una curva elíptica supersingular $latex E$ definida sobre $latex \mathbb{F}_{p^2}$  tal que $latex p=w_A^{e_A}\cdot w_B^{e_B}\cdot f \pm 1$, es decir es un número primo especial, donde $latex w_A,w_B$ son números primos chicos y $latex f$ es cualquier entero, así como $latex e_A,e_B$ los cuales se escogerán de tamaños parecidos y tal que $latex p$ cumpla el nivel de seguridad requerido en bits para este esquema, que está probado que es aproximadamente de 3000 bits (referencia aquí). Entonces con todo lo que dijimos en la sección de curvas súpersingulares es fácil inferir que el tamaño de la curva está dado por #$latex E(\mathbb{F}_{p^2})=(p\pm 1)^2$.

Sean A=Artemisa y B=Boris , dos personas que desean intercambiar una llave en un canal no seguro intervenido por un atacante con recursos cuánticos.

Entonces ellos harán lo siguiente:

Algoritmo SIDH (Supersingular Isogeny Diffie-Hellman)

Públicamente harán lo siguiente: 

Se ponen de acuerdo en los siguiente: $latex p=w_A^{e_A}\cdot \w_B^{e_B}\cdot f \pm 1,\langle E/\mathbb{F}_{p^2},\oplus\rangle,P_A,Q_A,P_B,Q_B\in E$ tal que $latex E$ es súpersingular.
donde intercambiar una curva $latex E/\mathbb{F}_{p^2}$ equivale a mandar $latex \lbrace a,b\rbrace$ tal que $latex y^2 = x^3 + ax+b$.

Tenemos que $latex P_A,Q_A$ y $latex P_B,Q_B$ fueron escogidos tal que tienen orden $latex w_A^{e_A}$ y $latex w_B^{e_B}$ respectivamente, lo cual es fácil por el número primo que construimos.

Vamos a denotar por nA, nB, el paso $latex n$ que tiene que hacer Artemisa o Boris respectivamente,.


1A: A genera dos números aleatorios $latex m_A,n_A$ < $latex w_A^{e_A}$
2A: A genera $latex R_A := m_A\cdot P_A \oplus n_A\cdot Q_A$ (secreto)
3A: A usa el punto $latex R_A$ para crear el subgrupo $latex H_{R_A}$ que funcionará como kernel del mapeo $latex \psi_{A}:E\to E_A$, por lo que ya tiene $latex R_A,\psi_{A},E_A$ donde los últimos dos son gracias a las fórmulas de Vélu mostradas en la sección anterior.
4A: A forma los puntos $latex \psi_{A}(P_B)$ y $latex \psi_{A}(Q_B)$ con su isogenia creada en el paso anterior.
5A: A le manda a B $latex \lbrace E_A,\psi_A(P_B),\psi_A(Q_B)\rbrace$
Pero NO le manda la isogenia, sino la imagen de los puntos bajo la isogenia secreta $latex \psi_A$

1B-4B: Ahora Boris hace los mismos primeros 4 que Artemisa, sólo intercambiamos las letras de los subscripts A por B

5B: B manda a A $latex \lbrace E_B,\psi_B(P_A),\psi_B(Q_A)\rbrace$
6A: A tiene $latex m_A,n_A,\psi_B(P_A),\psi_B(Q_A)$ y forma el punto $latex S_{BA}:=m_A\cdot\psi_B(P_A)\oplus n_A\cdot\psi_B(Q_A)$.
7A: A usa el punto para generar la isogenia $latex \psi_{BA}$ usando fórmula de Vélu, así como la imagen de la isogenia que será la nueva curva $latex E_{BA}$ que es isógena a $latex E$ gracias a $latex \psi_{BA}$.
8A. A calcula el j-invariante  de la curva $latex E_{BA}$ que será $latex \kappa:=j(E_{BA})$.
6B: Similarmente al paso 6A, Boris tiene $latex m_B,n_B,\psi_A(P_B),\psi_A(Q_B)$ por lo que forma el punto $latex S_{AB}:=m_B\cdot\psi_A(P_B)\oplus n_B\cdot\psi_A(Q_B)$.
7B: Boris usa el punto $latex S_{AB}$ para generar la isogenia con las fórmulas de Velú asociada al subgrupo generado por $latex S_{AB}$ , esta isogenia es $latex \psi_{AB}$ y genera también el codominio de esta isogenia que es la curva $latex E_{AB}$ que es isógena a $latex E$ gracias a $latex \psi_{AB}$.
8B: B calcula el j-invariante de la curva $latex E_{AB}$ que será $latex \kappa:=j(E_{AB})$.

Las curvas $latex E_{AB}$ y $latex E_{BA}$ son isomorfas, ustedes lo pueden demostrar si hacen todo el diagrama, por lo que el j-invariante será el mismo, y ya ambos pueden usar como password $latex  \text{Hash}(\kappa)$ o cualquier función en Kappa.

¿Pero por qué nos enfocamos en súpersingulares?

La verdad nunca usamos nada de las características supersingulares... Pero recuerden que el álgebra de endomorfismos de una curva elíptica supersingular NO es conmutativa, ya que es isomorfa a un álgebra de cuaternios.

Existe un ataque, que resuelve el problema "difícil" en el que está basado este protocolo en tiempo subexponencial cuántico. El algoritmo está descrito en este paper por Andrew M. Childs, David Jao y Vladimir Soukharev.  El cuál hace uso extenso de la CONMUTATIVIDAD del anillo de endomorfismos de la curva elíptica para resolver subexponencialmente el "Abelian Hidden Shift Problem" que es el nombre del problema que hace seguro al algoritmo descrito en la sección anterior.

Por lo que debemos enfocarnos a curvas cuyo anillo de endomorismos no sea conmutativo... es decir... súpersingulares.

¿En qué se basa la seguridad?, ¿qué tengo que romper si quiero hacer criptoanálisis a este algoritmo?

Lo que hay que romper es el "Abelian Hidden Shift Problem".  Algo así en español como "Problema oculto de desplazamiento oculto", ya que lo que estamos haciendo en el algoritmo anterior, es desplazar grupos, y adquireir nuevas curvas "desplazando" con puntos nuevos.

Este problema en general consta de lo siguiente.

-Sea $latex A$ un grupo abeliano finito.
-Sea $latex S$ un conjunto finito.
-Sea $latex f:A\to S$ y $latex g:A\to S$ dos funciones inyectivas.
-Existe una $latex b\in A$ tal que para todo $latex x\in A$ tenemos que $latex f(x)=g(xb)$
-El valor que un atacante quisiera saber es $latex b$.

Vamos a reformular esto en términos de curvas elípticas de manera básica.

-Tenemos dos curvas isógenas $latex E,\hat{E}$
-Decimos que $latex f_0(a)=a*E$ y $latex f_1(a)=a*\hat{E}$.
-Entonces $latex b*E=\hat{E}$
-También $latex f_1(a)=a*\hat{E}=a*b*E=f_0(ab)$

Resolver el Abelian Hidden Shift Problem en $latex f_0$ y $latex f_1$ es descubrir $latex b$.

Esto realmente significa calcular la acción en las curvas elípticas

Dicho esto, SIDH con curvas elípticas súpersingulares, la seguridad se obtiene es con llaves de 3000 bits para obtener seguridad cuántica exponencial de 128 bits, la cual es más que suficiente.

Esto es todo por hoy, ahora saben cómo implementar un algoritmo que tenga seguridad cuántica.

Espero les haya gustado

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

Monday, August 15, 2016

Definitud en lógica analítica de Solomon Feferman (Descanse en paz 1928-2016)

Hace unos días murió uno de los grandes en Lógica, el cual en mis aires amateur de Lógico analítico me agradaba mucho entender sus ideas, él fue Solomon Feferman, alumno de Alfred Tarski, que a sus 87 años muere pero deja una nueva manera de observar la matemática que nos dejó Gödel después de demostrar sus teoremas de incompletud que rompieron la supuesta "perfección" de la matemática y la sumergieron en un objeto "imperfecto" lleno de hoyos y preguntas sin respuesta que son los indecidibles en el lenguaje de la teoría de conjuntos que gobierna a toda la matemática, eso lo explico y demuestro en mi blog aquí Incompletud de Gödel

Hay nuevas cosas relacionadas hoy en día con un problema en lógica y conjuntos que se creía resuelto, más específico con la hipótesis del continuo, el cual es un problema en matemáticas que es indecidible, es decir no se puede demostrar con el sistema axiomático ZFC que sea verdadero o que sea falso, uno más de los hoyos en la matemática bajo este sistema axiomático que todos usamos que fue demostrado por Gödel en su teorema de incompletud que ahora es una herramienta formal que gobierna a la matemática.

Sólo para recordar rápido un ejemplo en ZF (sin C) de la hipótesis del continuo es

Sí ℵ = |ℕ| y ℑ=|ℝ| son los infinitos que corresponden a los tamaños de los conjuntos de números naturales y reales respectivamente (los cuales es bien sabido que no son iguales ya que por el teorema de Cantor Schroeder Bernstein no están en biyección y uno se puede construir como el conjunto potencia del otro) entonces NO existe un X tal que ℵ<|X|<ℑ.

Es decir, no hay un infinito estrictamente intermedio.

Esto lo explico en mi blog con más detalle aquí Infinitos grandes y chicos

En 1940 Gödel demostró que la hipótesis del continuo no era falsa.

En 1964 Cohen demuestra que la hipótesis del continuo no es verdadera.

Por lo tanto es indecidible. Es decir está demostrado usando teoría de modelos que no se puede demostrar que la hipótesis del continuo es demostrable falsa o verdadera.

Pero hay más

En 2011 Solomon Feferman encontró un argumento filosóficamente complejo en lógica analítica, en este paper se explica su teoría (Feferman) que propone una nueva teoría de "Definitud" usando un sub sistema semi intuicionista del sistema de teoría de conjuntos que usamos generalmente, el cuál es ZF, que acepte lógica clásica (donde toda proposición P tiene un valor de verdad) para operadores acotados (ej en el universo de los números reales. ∀x>0", "∃y<0", "∀x ∊ ℝ", para todo x>0, Existe y<0 , para todo x real ), y para operadores no acotados que uses lógica intuicionista (donde toda proposición no necesariamente tienen asignado un valor de verdad pero tiene una noción de pruebabilidad constructivista... Sí "pruebabilidad", es decir que se puede construir un camino lógico en el sistema axiomático de una teoría que conlleva a una demostración de su veracidad o falsedad) (ej. en teoría de conjuntos de un operador no acotado. ∀A ∅⊆A).
Feferman define que una proposición P es matemáticamente definida si el subsistema semi intuicionista puede probar P∨¬P (Es decir que existe una demostración para la proposición P o su negación).
Sólomon Feferman conjetura que la hipótesis del continuo NO está definida bajo este concepto de definitud por lo que la hipótesis del continuo está definida de manera "incompleta" y no tiene un valor de verdad. Koellner el mismo año propone que la teoría de conjuntos vista desde un sistema multiverso podría definir la hipótesis del continuo bajo la noción de Feferman.

Un documento de Hamkins define y usa los "Set Theoretic Multiverses" pero no ahondaré en ello ya que estoy en proceso de comprenderlo pero para el curioso que sepa de ultrafiltros aquí lo tiene: The Set theoretic multiverse

En este documento se demuestra la conjetura de Feferman.

Solomon Feferman 1928-2016

Sunday, July 17, 2016

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

Sunday, April 17, 2016

Parametrización racional de curvas con teoría de Galois

El siguiente teorema me parece que es de las cosas más importantes en álgebra, y es debido a David Hilbert e hizo nacer la teoría de Kummer, pero en eso no entraremos.

Veremos cómo encontrar puntos racionales del círculo geométricamente y cómo hacerlo puramente algebraico.

El teorema se puede explicar con un poco de teoría algebraica de números y teoría de Galois, lo que trataré de resumir en el contexto de este teorema sólo para poder entenderlo de manera informal.

Nota importante:
Si no entienden el siguiente teorema, no importa, no se asusten ni dejen de leer los interesados, todo este post será dedicado a explorar cada concepto, hablaremos un poco de teoría de Galois, de Normas, Trazas y extensiones de campos, y veremos que este teorema inofensivo nos ayudará con muchos problemas geométricos.

Teorema 90 (David Hilbert)
Sea $latex L/K$ una extensión de campos cuyo grupo de Galois  $latex G:=Gal(L/K)=Aut_{K}(L) =\langle \sigma \rangle$ es cíclico y si $latex x\in L$ tiene norma $latex 1$, es decir $latex N_{L/K}(x)=1$ , entonces existe $latex y\in L$ con $latex x = \frac{\sigma(y)}{y}$

Seguramente hay muchas dudas, ¿por qué es tan importante?, vamos a analizar un problema, que es el de encontrar puntos con coordenadas racionales en una circunferencia, es decir con coordenadas $latex (\frac{a}{b},\frac{c}{d})$ con $latex a,b,c,d\in \mathbb{Z}$

Ejemplo para motivación 

Todos sabemos que la parametrización de una circunferencia de radio 1 está dada por los puntos $latex (cos(\theta),sen(\theta) )$ con un parámetro $latex \theta$, ya que tenemos el teorema de Pitágoras que nos dice en este contexto que $latex cos^2(\theta) + sen^2(\theta)=1$ es decir, el coseno es el lado en $latex x$ y el seno el lado en $latex y$ de todos los posibles triángulos rectos cuyo ángulo en el origen es $latex \theta$ con hipotenusa $latex 1$ forma una familia infinita de triángulos que está parametrizada por una sóla variable $latex \theta$, por lo que decimos que la circunferencia es un objeto geométrico de dimensión 1.

 Las coordenadas $latex (cos(\theta),sen(\theta))$ justamente por la hipotenusa estar fijada a 1, formarían todos los puntos de una circunferencia de radio 1.

Es decir, el círculo está definido justamente por triángulos de hipotenusa 1 (en rojo), con su lado en la base $latex x=cos(\theta)$  y en su altura $latex y=sen(\theta)$ por lo que es el conjunto de puntos en el plano tal que $latex x^2 + y^2 = 1$.

Ahora, pero como algebrista, a mi me interesan los puntos racionales de esa circunferencia, es decir, todos los puntos cuyas coordenadas son puntos racionales, es decir cuando los puntos del círculo
$latex (x,y) \in\mathbb{Q}\times\mathbb{Q}$, queremos excluir puntos como $latex (\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$  o $latex (\frac{\sqrt{3}}{2},\frac{1}{2})$  que respectivamente corresponden cuando el ángulo del eje $latex x$ y la hipotenusa es $latex 45^{o}=\frac{\pi}{4}$ y $latex 30^{o}=\frac{\pi}{6}$ que claramente pertenecen al círculo pero tienen componentes irracionales.

Si queremos localizar puntos racionales, primero nos aseguramos de conocer un punto racional (por ejemplo el $latex (-1,0)$ ,  después construimos la recta que pasa por $latex (-1,0)$ y un punto en general $latex (x,y)$, es decir, vamos a variar la pendiente $latex t$ de la recta que pasa por $latex (-1,0)$ , al final, al tener este haz de rectas parametrizadas por su pendiente $latex t$  para todo $latex t \in \mathbb{Q}$ vamos a intersectar esta recta con el círculo y ver qué nos da, es decir, vamos a buscar todas las intersecciones de las rectas fijadas en un punto racional del círculo y con pendiente racional, a ver si de pura coincidencia nos da un punto racional del círculo. 

La idea visual es ésta:

La recta que pasa por $latex (-1,0)$ y con pendiente parametrizada por $latex t$ está dada entonces por $latex y = t(x+1)$ , es fácil ver que esta familia de rectas para todo $latex t\in\mathbb{Q}$ son las rectas verdes en el dibujo de arriba que pasan con $latex (-1,0)$

Por otro lado, tenemos que como explicamos anteriormente, la ecuación del círculo algebraica está dada por todos los puntos $latex (x,y)$ cuya suma de sus cuadrados nos da una hipotenusa de tamaño 1, es decir $latex x^2 + y^2 = 1$.

Con esto, vamos a introducir la familia de rectas paramétrizadas por la pendiente dentro del círculo, sí, esto es que si las rectas son $latex y=t(x+1)$ entonces $latex y^2 = (t(x+1))^2$ , y si intersectamos este conjunto de soluciones en el plano con el conjunto de soluciones en el círculos nos queda $latex x^2 + t^2(x+1)^2 = 1$  que es una ecuación cuadrática, y de hecho representa explícitamente al polinomio $latex (t^2 + 1)x^2 + 2t^2x+t^2-1$.

Tenemos que este polinomio tiene como raíces a la $latex x=-1$ que ya conociamos, y también a $latex x=\frac{1-t^2}{1+t^2}$ lo cual suena ya interesante.

En otras palabras, el haz de rectas choca con el círculo en $latex x=-1$ y en $latex x= \frac{1-t^2}{1+t^2}$.

Vamos a despejar la $latex y$ en la familia de rectas dada esta nueva $latex x=\frac{1-t^2}{1+t^2}$ que obtuvimos al intersectar con el círculo y obtenemos $latex y=\frac{2t}{1+t^2}$, con esto tenemos que estas dos ecuaciones como son parte del círculo y una recta racional, pues nos dieron por suerte una función racional, por lo que  la ecuación del círculo funciona con estas soluciones, $latex \Big (\frac{1-t^2}{1+t^2}\big)^2 + \Big(\frac{2t}{1+t^2}\big)^2=1$ que es fácil verificar, y tenemos una nueva parametrización con números racionales del círculo, dada por todos los puntos $latex \Big(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\Big)\in \mathbb{Q}\times\mathbb{Q}$ con $latex t\in\mathbb{Q}$.

¿Qué tiene que ver este ejemplo con el Teorema 90?

Vamos a contextualizar el ejemplo con las hipótesis, y ver ¿cuándo podemos parametrizar con funciones racionales? , ya que no siempre se puede hacer esto, el Teorema 90 de Hilbert nos puede decir en qué casos conviene buscar esta parametrización, y en qué caso, simplemente... no existe de manera natural (a veces existe con otras funciones modulares, o en otros espacios).

Para ello necesitamos un poco de teoría.

Embarrada de Teoría de Galois en este contexto y grupo Gal(L/K)

Vamos a describir unos ejemplos, y definiciones, sin rigor, sólo queremos por ahora entender lo que nos dice el teorema 90 de Hilbert.

Tenemos que el campo en el que trabajamos es el de los racionales $latex \mathbb{Q}$ , vamos a extenderlo a que incluya el nuevo entero algebraico $latex i$ donde $latex i^2 = -1$, por lo que tenemos.

$latex \mathbb{Q}(i) = \lbrace a+ib : x,y\in\mathbb{Q} \rbrace$

Este como pueden observar es un espacio vectorial sobre $latex \mathbb{Q}$ , son los números complejos racionales.

Vamos a ver qué es una extensión de campos pero antes una nota de cómo construir este espacio algebraicamente, ya que de esto se trata esto... de álgebra, después entraremos a la parte de extensiones de campos y teoría de Galois.

Nota de construcción algebraica de $latex \mathbb{Q}(i)$ para interesados, si no te interesa puedes omitir este párrafo: 
Decimos que $latex i \in \mathbb{Q}(i)$ es un entero algebraico sobre $latex \mathbb{Q}$ ya que podemos construir este nuevo campo tomando el anillo de polinomios con coeficientes en $latex \mathbb{Q}$ módulo el ideal máximo generado por el polinomio irreducible con coeficientes en $latex \mathbb{Q}$ que tiene como raíz a $latex i$ , y esto es:  $latex \mathbb{Q}(i) = \mathbb{Q}[X]/\langle X^2 + 1 \rangle = \lbrace a+bX : X^2 + 1 = 0\rbrace$.
La última construcción simplemente por el hecho de que $latex \mathbb{Q}[X]$ es un anillo (dominio euclídeo) , podemos usar el algoritmo de la división (como en la prepa la división sintética) y sólo dice que $latex \mathbb{Q}[X]/\langle X^2 + 1 \rangle$ son todos los polinomios en una variable módulo $latex X^2 + 1$ , lo que significa que todos los de la forma $latex g(X)(X^2 + 1)\equiv 0 \bmod X^2 + 1$,  y como es un dominio entero si $latex g(X)\neq 0$ entonces eso implica que $latex X^2 = -1$ por lo que la variable $latex X$ en esta construcción actúa como la $latex i$ imaginaria, y así se construyen los números complejos algebraicamente.

Tenemos que la extensión de campos $latex \mathbb{Q}(i)/\mathbb{Q}$ como su construcción depende de un polinomio de grado 2 como lo hicimos anteriormente (no se puede con grado 1 ya que el campo resultante sería $latex \mathbb{Q}$ ) es un espacio vectorial de dimensión 2 con base $latex \lbrace 1,i \rbrace$.

Esta extensión $latex \mathbb{Q}(i)/\mathbb{Q}$ es normal lo que quiere decir que todos los polinomios irreducibles con coeficientes en el campo chico, es decir $latex \mathbb{Q}[X]$ que tienen alguna raiz en $latex \mathbb{Q}(i)$ entonces tienen todas ahí, en este caso es fácil, ya que si un polinomio cuadrático lo puedes factorizar, entonces lo puedes factorizar con factores lineales.

Un antiejemplo de extensión normal sería $latex \mathbb{Q}(\sqrt[3]{2})\cong \mathbb{Q}[X]/\langle X^3 -2 \rangle$  sobre $latex \mathbb{Q}$, ya que $latex X^3 - 2$ tiene como raíz $latex \alpha=\sqrt[3]{2}\ $ y también tiene $latex \alpha\omega$ donde $latex \omega = e^{\frac{2\pi i}{3}}$  y pues $latex \omega \notin \mathbb{Q}(\sqrt[3]{2})$.

Regresando a $latex \mathbb{Q}(i)/\mathbb{Q}$  donde aparte de ser una extensión normal tenemos que también es una extensión separable, lo que significa que para todo $latex \beta \in \mathbb{Q}(i)$ tenemos que el polinomio de grado mínimo de $latex \beta$ sobre $latex \mathbb{Q}$,  $latex f(X)$   (es decir tal que $latex f(\beta)=0$) , tiene raíces diferentes.

Un antiejemplo de un polinomio separable sería el polinomio $latex X^3 - 2 \in \mathbb{F}_3[X]$ (con coeficientes en el campo finito de 3 elementos), ya que   $latex X^3 - 2=(X+1)^3$ en ese campo, por lo que tiene una raíz triple.

Es fácil demostrar formalmente ya con estas observaciones que $latex \mathbb{Q}(i)/\mathbb{Q}$ es una extensión de campos separable y normal , por lo que decimos que la extensión es Galois.

Estas extensiones $latex L/K$ se les puede asociar un grupo , que es el Grupo de Galois, este grupo está formado por todos los Automorfismos de $latex L$, (isomorfismos de $latex \psi:L\rightarrow L$) tal que dejan a $latex K$ fijo, es decir, que $latex \psi(K)=K$, cuya operación naturalmente es la composición de funciones, el hecho de considerar que fijen a $latex K$ sirve para tomar los automorfismos interesantes, es decir, que nos permitan estudiar a $latex L$ con respecto a $latex K$.

Este grupo mide la simetría de la extensión de campos, y de hecho el numero de elementos en el grupo de Galois, está acotado por $latex [L:K]!$ es decir, por el factorial del grado de la extensión (el caso de extensión de grado infinito existe, como por ejemplo $latex \bar{\mathbb{Q}}/\mathbb{Q}$, y obviamente es un resultado diferente pero no lo necesitamos aquí)

En el caso de  $latex \mathbb{Q}(i)/\mathbb{Q}$  tenemos que el grado de la extensión es 2, y lo denotamos por $latex [\mathbb{Q}(i):\mathbb{Q}]=2$ (hay teoremas que te dicen cómo acotar también por el grado del polinomio mínimo, en este caso el polinomio mínimo de $latex i$ tiene grado 2) por lo que $latex |Gal(\mathbb{Q}(i)/\mathbb{Q})|=2$.

De hecho, tenemos que $latex id\in Gal(\mathbb{Q}(i)/\mathbb{Q})$ por lo que ya tenemos un elemento de este grupo de Galois, ya que la identidad es un automorfismo.

El otro elemento es un $latex \psi:\mathbb{Q}(i)\rightarrow \mathbb{Q}(i)$ tal que si $latex z=a+bi\in \mathbb{Q}(i)$ entonces $latex \psi(z)=\psi(a)+\psi(bi)=a+b\psi(i)$ ya que $latex a,b\in\mathbb{Q}$ y $latex \psi$ es un automorfismo, y como mencionamos anteriormente $latex \psi(\mathbb{Q})=\mathbb{Q}$.

Por otro lado tenemos que $latex i^2 = -1$ por lo que $latex \psi(-1)=\psi(i^2)=\psi(i)\psi(i)=\psi^{2}(i)=-1$, esto implica que $latex \psi(i)=\pm i$ , ya que $latex (-i)(-i)=-1$ y $latex (i)(i)=-1$ .

Para la opción de $latex \psi$ tal que $latex \psi(i)=id(i)=i$ tenemos ya a la identidad, pero la otra opción $latex \psi(i)=-i$ tenemos ya el otro automorfismo, que es la conjugación por lo que.

$latex Gal(\mathbb{Q}(i)/\mathbb{Q})=\lbrace id,\psi \rbrace$.

Y como es un grupo de grado primo (2) , es cíclico, es decir está generado por 1 sólo elemento, en este caso la conjugación, ya que $latex \psi \circ \psi = id$ 

Normas y trazas 
Para terminar de entender el Teorema 90 nos hace falta lo que es la norma.
Esto ya lo expliqué en otro post en mi blog aquí, pero doy un resumen en este contexto.

Lo que queremos es definir una manera de poder medir a los elementos de un campo $latex L$ con respecto a un valor en $latex K$ para una extensión de campos $latex L/K$

Considera la extensión $latex L/K$ y define los siguientes $latex K$-endomorfismos de $latex L\rightarrow L$ para todo elemento $latex \alpha \in L$

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

Es decir, es sólo multiplicar cualquier elemento $latex z\in L$ por $latex \alpha \in L$ , lo cual claramente es $latex K-$lineal, es decir $latex \mu_\alpha(z_1+z_2)=\mu_\alpha(z_1)+\mu_\alpha(z_2)$, por lo que le podemos asociar una matriz a $latex \mu_\alpha$, y tenemos entonces que la norma de $latex x\in L$ es:

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

Es claro que $latex N_{L/K}(xy)=N_{L/K}(x)N_{L/K}(y)$ y $latex Tr_{L/K}(x+y)=Tr_{L/K}(x)+Tr_{L/K}(y)$ por propiedades de determinantes.

Ejemplo. en $latex \mathbb{Q}(\sqrt{2})/\mathbb{Q}$

Sea $latex \mathbb{Q}(\sqrt{2})/\mathbb{Q}$ , y como espacios vectoriales fijemos la base $latex \lbrace 1, \sqrt{2} \rbrace$, entonces tenemos que si $latex \alpha=a+b\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ entonces tenemos que las columnas de la matrix definida por la multiplicación por $latex \alpha$ , es decir la matriz asociada a $latex \mu_\alpha$ la podemos armar evaluando en los elementos de la base: 

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

Por lo que:

$latex \mu_\alpha = \mu^{*}_\alpha = \begin{pmatrix} a &2b \\ b & a \end{pmatrix}$

Es fácil ver que si para $latex \alpha=a+b\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ multiplicamos la matriz $latex \mu^{*}_\alpha$ por cualquier elemento $latex x+y\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ nos da el mapeo de multiplicación por $latex \alpha$, $latex \mu_\alpha$

Es decir:

$latex \mu^{*}_\alpha \begin{pmatrix}x \\ y\end{pmatrix} = \begin{pmatrix} a &2b \\ b & a \end{pmatrix}\begin{pmatrix}x \\ y\end{pmatrix}=(ax+2by,bx+ay)$

El cual un cálculo rápido verifica que es lo mismo que esta matriz es lo mismo que el mapeo:

$latex \mu_\alpha(x+y\sqrt{2}) = \alpha(x+y\sqrt{2})=(a+b\sqrt{2})(x+y\sqrt{2}) =ax + 2by + (bx+ay)\sqrt{2}$ 

Por lo que tenemos que la norma y traza de $latex \alpha=a+b\sqrt{2}\in \mathbb{Q}(\sqrt{2})$ es:

$latex N_{\mathbb{Q}(\sqrt{2})/\mathbb{Q})}(\alpha)=det(\mu^{*}_\alpha)=a^2-2b^2$
$latex Tr_{\mathbb{Q}(\sqrt{2})/\mathbb{Q})}(\alpha)=Tr(\mu^{*}_\alpha)=2a$

Ejemplo. en $latex \mathbb{Q}(i)/\mathbb{Q}$

No vamos a hacer el detalle aquí , pero tenemos que si usamos la base de $latex \mathbb{Q}(i)/\mathbb{Q}$ dada por $latex \lbrace 1,i \rbrace$ tenemos que para $latex \alpha=a+bi$ la matriz de la multiplicación por $latex \alpha$ 

$latex \mu_{\alpha}:\mathbb{Q}(i) \rightarrow \mathbb{Q}$
$latex z \mapsto \alpha z$

Por lo que las columnas generadas por $latex \mu_\alpha(1)=a+bi$ y $latex \mu_\alpha(i)=-b+ai$

por lo que 

$latex \mu^{*}_\alpha = \begin{pmatrix}a&-b\\b & a\end{pmatrix}$

Por lo que:

$latex N_{\mathbb{Q}(i)/\mathbb{Q})}(\alpha)=det(\mu^{*}_\alpha)=a^2+b^2$
$latex Tr_{\mathbb{Q}(i)/\mathbb{Q})}(\alpha)=Tr(\mu^{*}_\alpha)=2a$

Puedes notar que esta última norma, es la misma norma que utilizas en $latex \mathbb{C}$ , así es como formalmente se construyen las normas algebraicamente.

Todo listo para El teorema 90 de Hilbert y el ejemplo de la parametrización racional de la circunferencia.

Vamos a volver a enunciar el teorema y luego el corolario del ejemplo de parametrización con todos los ejemplos y lo anterior ya desarrollado.

Teorema 90 (David Hilbert)
Sea $latex L/K$ una extensión de campos cuyo grupo de Galois  $latex G:=Gal(L/K)=Aut_{K}(L) =\langle \sigma \rangle$ es cíclico y si $latex x\in L$ tiene norma $latex 1$, es decir $latex N_{L/K}(x)=1$ , entonces existe $latex y\in L$ con $latex x = \frac{\sigma(y)}{y}$

Corolario 90 
Considera la extensión de grado 2 $latex \mathbb{Q}(i)/\mathbb{Q}$  sabemos que es Galois y que tiene grupo  $latex G:=Gal(\mathbb{Q}(i)/\mathbb{Q})=Aut_{\mathbb{Q}}(\mathbb{Q}(i)) =\langle \psi \rangle=\lbrace id, \psi \rbrace$ (donde $latex \psi$ es la conjugación como ya la construimos anteriormente), tenemos que este grupos es cíclico y de 2 elementos, si $latex \alpha=x+yi\in \mathbb{Q}(i)$ es tal que $latex N_{\mathbb{Q}(i)/\mathbb{Q})}(\alpha)=1$ esto implica que $latex N_{\mathbb{Q}(i)/\mathbb{Q})}(\alpha)=x^2 + y^2 = 1$ por lo que existe $latex \beta=c-di \in \mathbb{Q}(i)$ tal que:
$latex \alpha = \frac{\psi(\beta)}{\beta}=\frac{c+di}{c-di}=\frac{c^2-d^2}{c^2+d^2}+i\frac{2cd}{c^2+d^2}$

Por lo que $latex (\frac{c^2-d^2}{c^2+d^2}, \frac{2cd}{c^2+d^2} )\in \mathbb{Q}\times\mathbb{Q}$ es la caracterización de los puntos de norma 1 (circulo en este caso) , usando teoría de Galois.

Puedes verificar que $latex \Big(\frac{c^2-d^2}{c^2+d^2}\Big)^2 + \Big(\frac{2cd}{c^2+d^2} \Big)^2 = 1$ por lo que si $latex c=1$ obtenemos la misma ecuación de parametrización que construimos anteriormente dada por $latex \Big(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\Big)$


El álgebra y la geometría son prácticamente lo mismo, un razonamiento puramente geométrico tiene respuesta algebraica,, de eso se encargó Alexander Grothendieck de formalizar, vimos que con teoría de Galois podemos llegar al mismo resultado geométrico.

No me dio tiempo de demostrar el teorema 90, pero tal vez pronto lo haga, no es tan difícil teniendo más herramientas a la mano que sólo para el que tenga curiosidad le podrá ser útil.

Eduardo Ruiz Duarte (beck)
twitter: @toorandom