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

Homosexuality and evolution, an attempt of an a priori argument to end homophobia

What I am going to say here doesn't have any proof, and maybe is not entirely true, but is something I would like to propose as a conjecture, and I have thought for some time, I don't know the answers a priori, because I am not a professional in other areas in science and sociology, but maybe it could be a good theory and I propose a way to take the proof apriori with a possible argument, maybe you can refute it immediately, but the aim of this is to generate a consistent strong theory to avoid discrimination and homophobia.

In the next words when I say homosexual I will be referring to lesbians or male gays.

Introduction

Lets start, some moments ago I was chatting with a friend, she told me that she has a 'friend' that was a complete retrograde, in the sense that she forbids completely the adoption between homosexuals, or that the best birth control system is god's word in your heart, I do not pretend to offend anybody but if you are going to make an argument trying to forbid or not approve you must have an a priori argument,  and not an argument based on a religious belief or a personal point of view, otherwise, you are imposing an idea like a dictator, making you retrograde.

What I am going to say is a possible-scientific reason to stop being an asshole, and maybe could be a good multidisciplinary work between mathematicians, sociologists, philosophers and evolutive biologists.

The next argument relies in the existence of models to measure situations in the nature, that proves that there is an equilibrium in the reproduction of species, interaction between species and natural resources consumption, this equilibrium is well modeled with five theories which I think are the bridges between mathematics, genetics, macro economy, evolutive biology and game theory, these models are described at the end of this post as an appendix, (Lotka-Volterra equations, Malthus model, logistic function, Nash equilibrium and Memetics).

The idea of this is provide a way to prove this:

Conjecture:
Homosexuality is a consequence of evolution.

Development of the conjecture and possible proof:


The models of population growth in terms of natural resources and interaction between species tell us that the convergence of the population when $latex t\rightarrow \infty$ is 0 when the function representing resource consumption is increasing over time, this in common sense is obvious, but more important than obvious, is that it has a mathematical model to prove it, and this models are Malthus equation and Logistic equation.

Another important theory here is Darwinian evolution which occurs with natural selection meaning that the individuals that adapt better to their environment will spread their genes with more frequency because they will be healthier for more time, this better adaptation is done because of a random mutation that makes the individual better than the others in terms of survival circumstances.

Another fact is that there is an excess of population in terms of some resources, (see variable $latex K$ in the logistic equation at the end of this post), there are more humans that the natural resources can support, but this IS NOT because we are lacking of food (this is important to understand), this is because the economic model that prevails (capitalism) bounds this resources in terms of wealth, so there are MORE humans than resources in function of wealth and economy.

So, If you accept the last paragraph, then we can continue, I accept that the last paragraph is a problem that exists, I dont know why but I have an idea that can be wrong or bad, but the veracity of the next paragraph does no depend on the veracity of the original conjeture (is used only to give an idea of why there's an overpopulation)

Conjecture (independent of the original conjecture)
The population increases in function of the advances in medicine 

This may sound a little cruel, but we are trying to make science, not ethics.

With the advances of medicine, people that develops a mortal disease young due to a letal gene does not die and reproduces passing his/her lethal gene to the next generations, slowing down evolution, (note that there's no such thing as anti-evolution, evolution always goes up in terms of adaptation).

So, technology in medicine make us overpopulated, note that is easy to show that evolution occurs and there are examples of this, if there were not a treatment of wisdom teeth people would die of impacted teeth or infection at maybe a young age, making the population with wisdom teeth less and less over generations.

In the book Selfish Gene from Richard Dawkins, he mentions that a non ethical way to evolve faster will be to only permit child conception in the biological limit of age in order to permit the death generated by letal genes, and in consequence, more genetically healthy human beings.


Now, lets return to the original idea.

We know now (or at least I hope I could convince you) that there's an overpopulation in terms of some natural resource which at the same time is in function of the economic model, and that the persistence of humans even when "they have to die" makes harder the natural selection.

Now we are in a point where humans in order to win the battle of resources they first most prevail and the Nash Equilibrium (see the end of the post for details) tell us that there's a point over time when the players (humans) with mixed strategies in this battle will take the most efficient decision in terms of the best decisions of the other, which is the equilibrium, if we identify the capabilities of each player (human) we will be sitting in the Lotka-Volterra equations, when we will identify which is the predator and the pray in terms of the economic model.

This Equilibrium I claim is homosexuality, which is the most natural way to solve the overpopulation, and proving that homosexuality is a natural property of the genes, a mutation in the human DNA, just as the mutation of distinguishing frequencies in our eyes and not just amplitude (colors) which was a mutation that prevailed making evolution of our eyes

First questions of this argument with a possible answer

1) Gay people are not new, there are proofs they have been in society from centuries ago and we did not have overpopulation problems.

Possible answer:
Yes, gays have been in the society for centuries,

But what I claim is that overpopulation has been there too since centuries, and as I said before, not because there's not food... is because the overpopulation is in terms of the economic model, people cannot take an apple from a tree without taking it from somebody's territory (in most cases), so he/she has to pay to the wealthiest, this makes Malthus and Logistic model of population vs resources being in function of the capabilities of resource taking, so if this is true (Is a conjecture as I said) it justifies the same argument.


2) Darwinian Evolution confirms that the genes must be spreaded, and homosexuality is not spreaded with a homosexual couple (just in an artificial way which takes you to question 3).

Possible answer:
Darwinian evolution is proved to be at the level of particles (See Dawkins, first chapter of Selfish Gene), particles tend to form stable structures, and this structures tend to form particles that are self replicable, this is the principle of  evolution pre-life in the planet, and is proven using the primordial soup experiment which consists in the simulation of the condition of the early earth with methane, hidrogen and amonia in combination with lightening, in a period of time monomers will form, then polymers and then self-replicatation molecules, which are the predecesors of the DNA.
This same behaviour is the basis of Darwinian sociology where the concept of spreading the gene will be a cultural concept for the next generation.

3) Gays can use in vitro methods to procreate children or "rent female" wombs (in the case of male gays)

Possible answer:

For this I need to introduce a concept, Memetics

Memetics (Richard Dawkins work for a treatment):
Theory of mental content based on an analogy with Darwinian evolution, is an approach to evolutionary models of cultural information transfer where the unit transfer is a meme.

Darwinian sociology makes the adaptation, natural selection and gene spreading to be taken in a cultural level, and there it can be introduced the concept of memetics, and consider evolution something more complex in humans than just a biological facts because human are equiped with reasoning and a brain capable of thinking in complex dynamic situations.

Gay people can adopt, procreate artificially or not having children, gays are not capable of reproducing themselves, but when they adopt or procreate they spread the gene that makes them homosexual with a probability of 50%,  or in the case of adoption, memetics from Richard Dawkins can be used and they will spread the Meme (See Memetics), which partially answers the previous question and justifies their existence as an evolutionary individual capable of reproducing his/her genes and memes.


Direct consequences of this conjecture

Homosexuality cannot be a disease, or a "condition", in darwinian evolution a mutation that affects the species wont prevail, so homosexuality is a property in human beings making them a naturally evolved organism.

Personal conclusion

Homosexuality is the direct consequence of a future in society when the convergence is of not having men or women, gay or not gay, but having just individuals or human beings, making them the key to find an equilibrium as a specie.

Appendix of used arguments in the previous idea for interaction models for resources modeling in function of population and competition.

Nash Equilibrium
John Nash proved that in a game, (in this case the battle of resources between humans) with mixed strategies (this means that, if there are different set of specific rules to win a game, you can randomly change strategies to win a game) there's always a point of Nash equilibrium between the parts, this means that , if $latex A$ is compiting with $latex B$ , the Nash equilibrium is the point were $latex A$ has the best decision taking in consideration $latex B$ decisions in the evolution of the game, and the same with $latex B$, $latex B$ has the best decision in consideration of $latex A$

Lotka-Volterra Equations tell us the dynamics of two species, where one of this species is a predator of the other (the prey).

$latex \frac{dx}{dt}=\alpha x -\beta xy$
$latex \frac{dy}{dt}=\delta xy -\gamma y$

This equations tell us that if $latex x$ are the number of preys, and $latex y$ are the number of predators , $latex \frac{dx}{dt}$ and $latex \frac{dy}{dt}$ are the changes in population of each other over time $latex t$, $latex \alpha,\beta,\gamma,\delta$ are values that represent the interaction of the species in terms of statistical analysis via observation.

The solution is a function which will tell you what will happen over time with both species and this equations can be generalized to the interaction of more than two.

Malthus equation

Lotka-Volterra equations can be combined with this equation which tells you how the population of an species grow, and what Malthus proved is that is exponential over time.

$latex P(t)=\hat{P} e^{\lambda t}}$

Where $latex P(t)$ is the population at time $latex t$ and $latex \hat{P}$ is the initial number of individuals, and $latex \lambda}$ is a constant (what we want to convert in a function in this idea) that measures the interaction of this specie with their natural resources (or even with other individuals)

Logistic equation

An improved version of the last one is given when you can measure the MAXIMUM number of individuals $latex K$ that an environment can provide resources in a way that no individual will lack of food or a resource that is natural to their lives.

$latex \frac{dP}{dt}=\lambda P(1-P/K)$



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

Intuición en transformada de Fourier discreta y correlaciones entre señales

Me he visto en la necesidad de ocupar un poco de análisis de Fourier, y ahora se está poniendo de moda mucho usar Fourier en teoría de Números como es en uno de los problemas del milenio, que es la conjetura de Goldbach que dice que todo número par mayor que 2 puede expresarse como suma de dos números primos.

Harald Helfgott decidió probar la conjetura de Goldbach débil (todo impar mayor que 5 es suma de 3 primos) hace un par de años usando teorema de Convolución, esto es algo muy de teoría de análisis complejo y real, y yo no me imaginaría que la solución fuera por aquí, el teorema de la convolución generalmente se usa en el contexto de señales y Análisis de Fourier, en otro momento lo expondré aquí, la explicación sencilla de Helfgott y su solución aquí.


Yo no soy experto en Fourier, pero lo he usado para varios proyectos y me interesa mucho, les expongo aquí una manera intuitiva de entender la transformada de Fourier discreta.

La Transformada de Fourier trasforma una función periódica en otra función en el espacio de frecuencia, es decir, busca otra representación de la función en términos de combinaciones lineales de otras funciones, en este caso senos y cosenos, como algunos sabrán, toda función se puede aproximar por senos y cosenos por partes, estos coeficientes de senos y cosenos que arman la función original son la información de la transformada de Fourier de una función $latex f$.

$latex \hat{f}(\psi)=\int_{-\infty}^{+\infty}f(t)e^{-2\pi it\psi}dt$

donde su inversa está dada por

$latex f(t)=\int_{-\infty}^{+\infty}\hat{f}(\psi)e^{2\pi i\psi t}d\psi$

Donde $latex t$ es el tiempo y $latex f(t)$ es el valor de la señal en el tiempo $latex t$,  $latex e^{2\pi i t}=cos(2\pi t)+isen(2\pi t)$ y $latex \psi$ es el valor de frecuencia.

La teoría aquí es muy bonita, pero también muy complicada, así que nos adentraremos en la parte discreta

Transformada de Fourier discreta.

La transformada de Fourier discreta (TFD) es un funcional (una función de funciones) que toma como argumento una función $latex f$ que es una señal en el tiempo y te regresa otra función $latex \hat{f}$ que contiene la información de la frecuencia en la señal original.

Para términos prácticos, una señal será sólo una sucesión de números, por ejemplo:

$latex \tilde{f}=\lbrace 1.9, -3.1, 12.3,4.8,22.9,-13.2, 11.8,4.8,-0.3 \rbrace$

Dónde $latex \tilde{f}(n)$ es el valor $latex n-$ésimo comenzando por el $latex 0$, $latex \tilde{f}(0)=1.9$

Le pongo tilde porque queremos trabajar con otra versión de esta señal que ahora explico.

Señales de promedio cero

Queremos comparar señales, para ello necesitamos trabajar con las señales "normalizadas" , en el sentido que si vamos a correlacionar $latex f$ con $latex g$ , una correlación "0" nos indique que son totalmente diferentes, para esto, sólo basta con trabajar con las señales "centradas" en su promedio y basta con restar a cada coeficiente el promedio de la señal en el intervalo de tiempo, si repitiéramos esto en la señal verían que el promedio de la señal ya sería 0 y no habría nada que restar, por eso le llamo "normalización" , en el caso del ejemplo, vemos que el promedio es $latex 4.6$ por lo que la nueva señal quedaría.

$latex f=\lbrace -2.7,-7.7,7.7,.2,18.3,-17.8,7.2,.2,-4.9 \rbrace$

La cual tiene promedio 0.

Correlación entre dos señales

Ahora, ¿cómo comparo dos señales normalizadas $latex f$ y $latex g$?

La manera más usual para señales discretas de tamaño $latex N$:

$latex \displaystyle \sum_{i=0}^N {f(i)g(i)}$

Si se fijan, gracias a la normalización tenemos las señales centradas en su promedio, por lo que si esta suma da 0 nos indicaría que no se parecen nada, ya que si $latex f(i)g(i)\geq 0$ es porque ambos valores tienen el mismo signo $latex f(i)g(i)\leq 0$ nos indicaría que difieren en signo y son "muy diferentes" , las sumas se van a ir acumulando positivamente si no hay estos cambios de signo, por lo que indica que entre más grande sea el número de la suma, más grande es la correlación siendo el máximo de correlación la suma de cuadrados de cada señal, si es un número muy grande negativo indicará que están inversamente correlacionadas (no se cancelan con los positivos) , y si es 0 , es porque las correlaciones siempre se "matan" entre negativas y positivas (no hay correlación).

Aquí dejo como se ven dos señales correlacionadas y no correlacionadas.

Para que esta medida tenga sentido, recuerden que tienen que normalizar ambas señales.

Ahora, entonces, si recuerdan, la transformada de Fourier, se multiplica la función por una exponencial compleja, es decir, están correlacionando la función con una exponencial compleja que al final son senos y cosenos, es decir... están comparando la función con senos y cosenos, y viendo qué tanto se parecen en cierto tiempo $latex t$.

La transformada para tiempo discreto $latex n$ de Fourier para una señal $latex f$ de $latex N$ valores en el tiempo se define como:

$latex F(k):=\displaystyle \sum_{n=0}^{N-1} {f(n)e^{{-2\pi i kn}/N}}$ donde $latex k\in \lbrace 0,...,N-1\rbrace$

Para cada $latex k$ obtenemos un coeficiente de Fourier, hasta ahora... creo que vamos bien, no es difícil en términos prácticos, pero ... qué es correlacionar con la exponencial compleja esa? , se ve feo y raro, pero no, recuerden que.

$latex e^{-i\theta} = cos(\theta)-isen(\theta)$ 

Entonces realmente tenemos que:

$latex F(k):=\displaystyle \sum_{n=0}^{N-1} {f(n)(cos({2\pi kn}/N) - i sen({2\pi kn}/N))$ 

$latex F(k):=\displaystyle \sum_{n=0}^{N-1} {f(n)cos({2\pi kn}/N)}-i\displaystyle \sum_{n=0}^{N-1} {f(n)sen({2\pi kn}/N)}$

Tenemos que para $latex k$ hay una función diferente.

El juego de signos es por las propiedades de paridad del seno y coseno.

Entonces lo que tenemos aquí es que la transformada de fourier realmente guarda la información en senos y cosenos que es lo que dijimos al principio (para eso se usa la exponencial) , es decir correlaciones con ambos tipos de sinusoides, y el usar la parte compleja, tiene un significado tan simple, como el hecho de hacer "linealmente independientes" a las correlaciones, ya que al final lo que nos interesará será el número real que multiplica a la parte imaginario, y no per sé la $latex i$ de análisis complejo (al menos no en este caso).

¿De qué nos sirve?

Veamos un ejemplo, supongamos que tenemos la siguiente señal $latex x(n)$ con 100 sampleos de tiempo, es decir $latex N=100$

En este caso los coeficientes para cada seno y coseno definido por $latex k$ los denotaremos como $latex X(k)$, es decir.

$latex X(k)=\displaystyle \sum_{n=0}^{N-1} {x(n)cos({2\pi kn}/N)}-i\displaystyle \sum_{n=0}^{N-1} {x(n)sen({2\pi kn}/N)}$

Para $latex k=0$ tenemos que $latex \displaystyle \sum_{i=0}^{N-1}x(n)$ 

Es decir solo es la suma de los valores de la señal ($latex sen(0)=0$ , $latex cos(0)=1$) 

Por lo que $latex X(0)\cong 0$ ya que la señal está normalizada y tiene promedio 0.

Para $latex k=1$ tenemos la siguiente información de cada sumando de la serie la transformada de fourier.

Como pueden ver en la gráfica b) y c) que la $latex X(1)=1+0i$  , es decir, no se parece nada la señal $latex x(n)$ en azul a la negra y roja tanto en seno como en coseno, pueden ver en b) , sin ser muy rigurosos en la siguiente oración: "la mitad de la señal está arriba del 0, y la otra mitad abajo" por lo que la correlación dará 0, lo mismo con c), también se cancela al sumarse sus valores. es decir, no se parecen (recuerden que b, respectivamente c) es la parte (real respectivamente compleja) de $latex X(1)$.

Ahora, veamos que pasa en $latex k=3$

Aquí vemos en $latex k=3$ que el seno con la señal  en c) tiene gran parte positiva, y poco negativo... 

por lo que la correlación nos indicará que es grande (no se cancela con negativos en la función original) y si ven en a) , pueden ver que el seno en negro en esa $latex k$ "asemeja" a la función $latex x(n)$ mientras que el coseno realmente no se parece en nada, nunca coincide con $latex x(n)$... y de hecho $latex X(3)=0+49i$.

Realmente lo que estamos buscando aquí en la transformada de Fourier, es cuando una senoidal se parece a la función original... y qué creen? , ya la encontramos, 

La gráfica de esta transformada de fourier se ve así para $latex k=1...20$

Como pueden ver, la transformada de Fourier, nos dice que $latex X(10)$ en el coseno se parece mucho a la función $latex x(n)$  y en $latex k=3$ tenemos que $latex X(3)$ en la parte imaginaria el seno se parece mucho a la función original, es decir hay correlación alta por ejemplo en el coseno con   $latex cos(\pi t/5)$.

Pero bueno Si quiere ver todo de golpe, sin importarles si es seno y coseno (al final ambas funciones son la misma solamente recorridas) , pueden calcular su densidad espectral para cada valor $latex k$ la cual les dirá si hay sinusoides presentes en la señal la cual se define como

$latex DS_{k}(x)=\mathfrak{R}(X(k))^2 + \mathfrak{I}(X(k))^2$

Que es la suma de los cuadrados de la parte real e imaginaria de la transformada de Fourier para cada $latex k$

Por lo que en este ejemplo, la gráfica de la densidad espectral que ya carece de parte imaginaria, junta toda la información (aunque se pierde de qué tipo de sinodal viene, pero esto es fácil deducirlo)

Aquí pueden ver perfectamente que en $latex k=3$ y en $latex k=10$ existen sinusoides interesantes muy correlacionadas con la señal, 

Mucho se habla de Frecuencia, para esto, lo más popular es usar Hz , es decir "cosas que suceden en un segundo" , y para transformar la $latex k$ en Hz , basta decidir "cada cuanto sucede un suceso" a este número llamale $latex r$ , uso $latex r$ porque es de "sampling rate" , y tenemos que en Hz, la frecuencia es $latex \xi=kr/N$ donde $latex N$ es el número de samples, o el número de valores en tu tiempo discreto, entonces ya pueden sustituir la $latex k$ por la frecuencia $latex \xi$.

Espero les haya servido como a mi, las imágenes las saqué de este sitio 

http://practicalcryptography.com

Aquí les dejo del mismo sitio los valores de la señal $latex x[n]$ en el ejemplo.

1.000000, 0.616019, -0.074742, -0.867709, -1.513756, -1.814072, -1.695685, -1.238285, -0.641981, -0.148568, 0.052986, -0.099981, -0.519991, -1.004504, -1.316210, -1.277204, -0.840320, -0.109751, 0.697148, 1.332076, 1.610114, 1.479484, 1.039674, 0.500934, 0.100986, 0.011428, 0.270337, 0.767317, 1.286847, 1.593006, 1.522570, 1.050172, 0.300089, -0.500000, -1.105360, -1.347092, -1.195502, -0.769329, -0.287350, 0.018736, -0.003863, -0.368315, -0.942240, -1.498921, -1.805718, -1.715243, -1.223769, -0.474092, 0.298324, 0.855015, 1.045127, 0.861789, 0.442361, 0.012549, -0.203743, -0.073667, 0.391081, 1.037403, 1.629420, 1.939760, 1.838000, 1.341801, 0.610829, -0.114220, -0.603767, -0.726857, -0.500000, -0.078413, 0.306847, 0.441288, 0.212848, -0.342305, -1.051947, -1.673286, -1.986306, -1.878657, -1.389067, -0.692377, -0.032016, 0.373796, 0.415623, 0.133682, -0.299863, -0.650208, -0.713739, -0.399757, 0.231814, 0.991509, 1.632070, 1.942987, 1.831075, 1.355754, 0.705338, 0.123579, -0.184921, -0.133598, 0.213573, 0.668583, 0.994522, 1.000000

Eduardo Ruíz Duarte (beck)

twitter: @toorandom

Encontrando números primos grandes con approach matemático-computacional

Si estás de un smartphone no se verán los símbolos, probablemente quieras verlos así que haz click aquí

Recientemente me vi en la necesidad de encontrar algunos números primos grandes de la forma $latex (3*8^n)-1$ por una cuestión de un problema de geometría aritmética y primality testing, quiénes creo que se podrían interesar en esto fueron en Facebook Esteban Gutierrez y Manuel López Michelone quiénes comentaron sobre esto, un análisis rápido te dice que ese número es primo para $latex n\in \lbrace 1,2,6,72,1092,5687 \rbrace$ pero otro análisis no tan rápido que hice fue para descubrir $latex n=17129$, estos número para el ojo inocente parecerían inofensivos, pero para $latex n=17129$ nos encontramos con un número de 16,000 dígitos aproximadamente, y ahora mi workstation está checando $latex >n=35000$ que son como 32,000 dígitos decimales, es decir 105,000 bits, tardándose aproximadamente 30 minutos por cada thread (hice 32 POSIX-threads) entonces me arroja aproximadamente 32 resultados cada media hora, y el tiempo sube por cada iteración logarítmicamente, así que si sigo así pronto comenzará a tardar horas, el código lo voy a publicar ahorita, así que encontrarán las ligas al final de este post para que lo corra cualquier linuxero, o mejor decir... "POSIXERO" ya que toda el api que uso al final es POSIX compliant y para manejar números grandes y hacer aritmética uso BN  (Bignum) de OpenSSL que considero es lo más rápido ya que se usa en la industria, el código detecta tus procesadores y usa TODOS, así que tomalo en cuenta con el nice, tiene macros para funcionar en OSX (Apple) ya que pthread_set_affinity_np() y CPU_SET funcionan diferente.

La pregunta matemática sería:

¿Existen una cantidad infinita de números primos de esta forma?


Ahora explicaré cómo lo hice para que sea lo más óptimo que se me pudo ocurrir.

1. Construir número optimamente

$latex (3*8^n)-1$ lo podemos fabricar en binario en vez de calcularlo, con esto nos evitamos muchos ciclos del procesador


Por un lado tenemos que $latex 8^n=2^{3n}$  y $latex 2^m=1000...000B$ con $latex m$ $latex 0$'s eso significa que $latex 8^n$ tiene $latex 3n$ ceros y un $latex 1$ al principio, después multiplicar por $latex 3$ es lo mismo que sumar $latex 3$ veces $latex 1000...000B$ el cual será el número $latex 11000...000B$ con $latex 3n$ ceros y restar $latex 1$ será negar todos los ceros y el segundo $latex 1$ por lo que va a quedar    $latex (3*8^n)-1=10111...111B$   donde el número de $latex 1$'s menos significativos es $latex 3n$ , con esto ya no tenemos que calcular exponenciación que es muy costosa.

2. Ignorar números que nos harán perder el tiempo

Sucede MUY frecuentemente que $latex (3*8^n)-1$ es múltiplo de $latex 5$ , esto es fácil verlo
ya que si $latex 3*8^n$ termina en $latex 6$ o $latex 1$ entonces $latex (3*8^n)-1$ es múltiplo de $latex 5$, pero no puede terminar en $latex 1$ porque $latex 3*8^n$ es par, y para que termine en $latex 6$ como $latex 8^n$ termina en $latex 8,4,2,6,8,4,2,6,8,...$ (en ese orden comenzando con n=1) nos interesa saber cuándo $latex 8^n$ termina en $latex 2$ para que $latex 3*8^n$ termine en $latex 6$ y por consiguiente $latex (3*8^n)-1$ sea múltiplo de $latex 5$.

Un chequeo rápido y respaldado por la propiedad inductiva en los número naturales sobre $latex n$ tenemos que $latex 8^n$ termina en $latex 2$ si $latex n=3,7,11,15$ es decir si $latex n=4t-1$ y más computacionalmente si $latex n\equiv 3 \mod 4$ o más humano "si $latex n-3$ es múltiplo de $latex 4$" entonces esto nos dice que podemos eliminar automáticamente 25% de todos los exponentes al checar $latex (3*8^n)-1$ ya que serán múltiplos de $latex 5$

3. Optimizar test de primalidad y utilizar números más familiares para una computadora

Una vez construido el número, y filtrados los exponentes que hacen trivialmente compuesto al número, necesitamos ver que lo que tenemos en efecto sea un número primo.

Para hacer esto nos auxiliaremos en el pequeño teorema de Fermat el cual lo escribo diferente a Fermat para que se entienda dice:

Teorema de Fermat
Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^p - a$ es múltiplo de $latex p$

Equivalente

Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^{p-1} \equiv 1 \bmod p$

Esto es lo mejor que tenemos y lo peor es que existe la posibilidad de un "falso positivo"
ya que el teorema aquí ya supone que $latex p$ es primo, es decir estamos checando una propiedad que tiene un número primo siempre, pero podría tenerla otro número también ya que el teorema no es un "si y sólo sí" $latex \Leftrightarrow$ , pero para nuestra fortuna, los números que cumplen la propiedad de Fermat y no son primos son "strong pseudo-primes" , "Fermat Liars" y son raros, de hecho yo prefiero Números de Carmichael quién fue el que los estudió y para nuestra fortuna, no hay tantos y son raros, y si nos toparamos con un "posible primo" , cambiamos la $latex a$ del teorema de Fermat y volvemos a probar y si también se cumple la congruencia, es ya casi un hecho que lo que tenemos es primo.

Pero bueno aún podemos optimizar MÁS , vamos a optimizar el teorema de Fermat, ya que como pueden ver... vamos a tener que elevar un número (en mi caso 2) a la $latex x$ donde $latex x$ es un número de más de 30 mil dígitos, módulo es número de 30 mil dígitos... afortunadamente existen algoritmos para hacer esto en tiempo logarítmico pero aún así es tardado, así que si podemos eliminar más ciclos sería bueno.

Tenemos que $latex x=(3*8^n)-1$ nunca es el número primo $latex 2$ así que podemos suponer que es impar sin ningún problema , por un lado tenemos que $latex a^{x-1} \equiv 1 \bmod x \Leftrightarrow a^{x-1} -1 \equiv 0 \bmod x$ si $latex x$ es primo,  ahora,  $latex x-1=2k$ es decir es par, entonces $latex a^{x-1}-1 = a^{2k}-1 = (a^k -1)(a^k + 1) \equiv 0 \bmod x$ (diferencia de cuadrados), como $latex k=\frac{x-1}{2}$ entonces tenemos  que $latex (a^{\frac{x-1}{2}}-1)(a^{\frac{x-1}{2}}+1) \equiv 0 \bmod x$ lo que significa que para que se cumpla Fermat, tiene que suceder que $latex a^{\frac{x-1}{2}}\equiv 1$ ó $latex -1 \bmod x$ donde $latex -1\equiv x-1 \bmod x$ y con esto reducimos 1 ciclo más en la exponenciación modular que es muy costosa, y usamos $latex a=2$ ya que la exponenciación por 2 sólo es shifting a la izquierda, y usando 2 es hermoso para el algoritmo de exponenciación modular porque la complejidad
$latex o(3kn^{1.585})$ (Multiplicación Karasuba y reducción Montgomery para mod_exp hasta donde sé que usa BN de OpenSSL) esperada baja considerablemente teniendo muchos 0's en su expresión lo que reduce pasos (por eso la $latex o(g[n]))$ y no la $latex O(g[n]))$),  donde $latex 3k$ es el número de bits de $latex x$ (nota aquí que la $latex n$ representa la variable de complejidad y no el exponente), y con eso hemos encontrado los primos que mencioné al principio.

Espero opiniones, source code aquí

Eduardo Ruíz Duarte
twitter: @toorandom

Por Morbo aquí les dejo el más grande que he encontrado, tardó 3 minutos en 1 thread. el cual es $latex (3*8^{17129})-1$ el cual tiene 51,388 bits .

32026423315381466050277915530786335800393823366890894981259290036648161553494994617558347456939958845983080809781780843277379143842511321157300439716316621258468518963948059640880521931439098619360470902127202739263724498727354638561114775469410152002760785630729882805025686247898899808911618409162136670680087277684487378095087887490583145258613139912396900825975697214682477274814156070359889110867811362193110348467393951992492345402056332383241386444305433601523085645869776811285646919087537466338016988423008766811472396005675392998881736916741912590189429331612837325373810452416030933831306867192676710269198951414458490437515264053051733873759760089225408336099284078093859455689148594434825613934497979781554179399202461221624253778300943176804460380502043924360948006335930676276227451427823493631843987911309636588431232386671032205960984005755897461961694816343511105402244581305974926489787769176727530282950574991748927557944410793100152205427813737629867224719749629559616541154571702402344007533555385071678935056951177266337611794442895925353683999178922756717467868112921444235536843814816587988381808259378763566339936575469133821904985670022768297621487042685072937645035397418762898088879966518834617431717616238160653229933317675561804324889864152610093010599664552103022407658203362826225135467122903372349775404454265894274031612183834433948175013815731731843768742711463425691140151259964862216909975488504743216033971257070468582283917816001081411729083210816836157717534301930744010414980424399802727757779067704711766548222713340284109481557728641051371992861091880789035561130198577315011688318769929786698521625431301832480788848469161536541203402106348915684835706031086198583470841503903548287043913330764995542582104558499052946524398642023915418094252775225135009392516216639788849081686649422414816420666524703609315132700144025576596698848194947599190340291543335651139477044320381872498206346425778242974783028340973498127326252357750612335602225108453954123859141624811742539990879575619773935510158546410141054095024924790241748920937072243685910974276469625883231365286281146397745282169224983577575852655025299677792623835241690537842870710528349067292463062257545894983725514137453620357976030228008635191305568411517021214777322011903026859601083554815240483942419038213153965732868181464332882027463093394450027202039114912743513771018541173505400069482374254318086098853632651567194952960545899057851574317234825560325729148747127013748646167661011675033243786731813402924344723783663066299906756407070530905173417647177285662615563890874013554204722859804826783319723895173795270908631147615754087439314263020476261354882689909166015907511051623119212879465867556909644440100632138353562083646966088393779513894343599588950053243809581940981833880678424982730382004328421941439072636800592877300140048085384317222361179303861645355317608391899423839079837905186750572454810469022406363372588948686204901139113299980435620209872045747933603059130972696653746953604532417492903736570671296699105655923819429995588811467179873672852431251204448040809915863163514335540089427059903930482164420870043452193744616222493706789929016164765070777799153453961045107726915484605407070139659338306471198522417856040168525001743452798331018200032516982674115924542207247561332705748100446483628681758170277861279289599258673198185708528378663459785909178096390845218020629053192057841759202932782309711814026123607150376911940748135836533906883752444763036721353897269880408805386078398045366480484951224112577584082675114895273853399084137327610229509328970706333462386945933615225142344089090446121520471032079274695108327379700854569636711391422529411618554876423454704114335714668077792468687086576736091448314825802520170346995090349720987439473605228224586805882340461196462558836145583970685095961833008585739864656363328302986709618224658592061790170440213776071852284933724917317499943202018446618210793294932831097623750797416246378349485892742882242489517967732592792481355599182598675646982241076442612020185511034050637482303910568507849800434585110875928913264144917561728507483873787584779156636819491649231469052768465384827615887208338319057096162237372005045429022403914234522895948109125618822616830011877945500320746041816052399512404707120200149549307311742265568523260555270588190891088146372739404374609532572772005797711009523114710103299579557147452176909952118545682110695102391553837852971501889513088222486987723921202415262209457238513791459203972870093386953048894801746214435712103477352922752928791906655786957516121929344278692478022077201558938914429157414192182892992028571663350174293119784111516284937872290882995528284151163236783105238160116300616254926975435140120536460294894410442753982342285715596774450547688510540950609379199176038748244276624271511162021898465702381739554745903292368453929023793055915664947937134935491330980718736217997428692810379092480664406511201873764269913663647020985956314161402000383439218120742135271552526071319102832539386295104448025731371374719348527163508063409657644511483601027063141269736285818775573658317881599404287364002332020457775029972569361743675624369268068117893284658209857784788545339202829190234333573510725635332114732388415720177686698830992999310828225254838530442450211498457933037804583792899416998160092466471334917779332924285621209393547865615433381452726968988212217944363239160938499077454607308202875136763555648760496640998480414396908114196518199386149585672336456043989071695238312288960081259962428139207487337862311363664235353355741056558668800464140710661218731996083813228309464181512824198473099835338147549021620784938152526403884390915371010004103078720376198785754267231632364475196249423028430296607633185992949806664821669508769010395593020867265768241356602352619944658174291464218293290651513925863985300257092863217772635441366596007681209046202751531928654365904486480637896037524609924560756737487555941653455392568655608180047527596306525572672891104374795309986323951969131709938262130944930794116800383445065248433923593381063574380087876957452711241937139283341986739106521622406898428983948046724085183024676505731621744665800497853221066191995732134553165719198648689135257528892602964255853707448817858352523437863421426102418117389544983206042308860683466269434657391645604299058196009634534319799146142598318942762623665930578733123571550032271299551114477333140685887321380068779030520881901530995711544355981117803607975968517499227648018428854655983473350493961762777920029051990792375397413824629029725111324189020468036861701447775824977257286314969930798035433627722690476216793743259593862757494785251530728454141362285932172007019448646822993271982444067467511428273397361690368237878111466206232963438330207726200080194611554342535208143831928801129239615572665628913222777854337631162257572382401793069038204155873152194648221501879285765056884379731159884546949750078461272929585042335506924134975880741347636497891449035978435021137529059174101402963872488774055561871763906005995523112899268150145675230528838855491232516570415185657872854886290162991073611832895236728088095860213006479909366614293585377658649333618462661081337250855184818048918280095216771124919354017900316074686948848666096561888434199822022864315541727689104723180042673931538717736387214138023901177682380480573112291135017398314529185431570271124814738098761072609216606999034113642258974107978719402360004973983466905902220813267671856406327086943579910433158637016416320152392435734326402865259058273022480138148188943021020384024506061902144679691028765137048209827552145995276652839943973336959426861497791033259830231723590523648498835822832310074455043040176962529346513059433633982359304138147553887485074486267391219132827142128335706403319422134084444025461591415872438467681229654425434633494593254114591133359674756811870187942825563687040492646952300630610982000264767473553602225155962233169190888460758352343896019871785984159532458130055709200931106493045763269590995530937189497063631830785082964079799523231260807321064954724345171548330473944837948003158443648883656429657821491956256504263890572005938508038381077649008380039581215475512164674386754377503163134803108273243041775665133283203530877641413091640784342349226191942006609524592938809381209539984692931251689753565266660069225820293301694201093380755714940533267406389212538472737345389920939638830120261737007640910540478856973611235739472554054732492599378321173386948659654872894505995568627052612775511578286760509286861768721974406755260200693773145017206683870773831784040386709044145859000178680454409827037232424821580153078526733906602635501448413155506471616532000380246549340334416808898434387410310767186271678651657125956330997135514287078037552835249014425147171712299257324870293646478104446879005854587240740583374971104742080118407293376250478292379654435036077102162699707316802765421226043298626360886593259957682295399635161319003729817233310836488878679452228196539460170236747951470219093715468757201428276567346844650203948349754588389125473669983324294915461031237867790032803164212486116627265051342591429261672735326004971500809554757104809198941710250369014929980399788042439092012739807413496910294722408654685906467188445652852679463510111588848714966994012633053111140523488797686496074404075035403032823629222238696411817644483300212092444148203586311124377532534089957832358357772985060452544714354695728594506029245228474290363244268026739022540462324210220094777074046735835916531079392171548754284909023490741942672576020109502086289324949189131229866882158751044579431073510058638580112970399400848012598667869946183555382577600203193941610086977918428282164298924318017243031208758208540683610170253540720335918689087434714730194564568976981777204445322986698373283390613470588168852889384592420528734963148995278955127941606122747080059367271673385322580445859123918237395666091441934678389289512890922392344993878800705035425791621906338667172499766162845453799509129825300440130012452422744967544346925837444005229552678073813615644879122257996997585678579511199674812593313238824764101761027353677321483720341880084732506793520846691464229711911399127721595694352403218401554932929595580588474107092800484536679906402882561774736289011712497922621582368337057910519632385879773294033551311658003580394298225128044755081583957070106775832608786270843701706632218236607363754573786689965846170399266338261414148862926960078807493024676636241821780944571096941752160727585488941102816572881758376655843234513616963008536787097251683013326148161450318083878017455643651554618261609966657262498344963281756373673269194825457120102335098430053525126126433050268325257610505256130462410397690925472067734961438549322304026644954794880041403058925796970496923953825506922111728360818654368875624837101641043903975798923440983174868771201734139437540847299331370990285604146267866907128889409552307757336422613848203004832657228332873404485085691176592522515171277306509004682948792277048468532631094588527157849361469770828540588429898016076708761086577687829794189995013320624862541504004344723993123491408236967534492449686611053666809249670558680801820699727271874125672980265867805587536003161611257602573879807891275145042611104947170932266106091329413068356104455079652564819613052988898269750866283631671361118418750456959898175596314235967214072736323242812555211430437013788931433823216158115282033550906925064093752025137605666797295274782995312635995982152649414790767022457876214220333912735265753742268349688660929764774270479063514369370861571597970542022613471507522362653019693799529912763689666033819469364626587974886877639192115375028613651480474237164637235577738383600508857173217109336525549418866366010878280531299766307762080753760829697569168773083049209471459983537669269749153891301730779513444000645411763110787536847848686483217045928561483760722316598284514141270858839546812101630071239179032956638848984251827861941056826930437770466758033287498621544428023782166008169892843744703334403973198509454469653826983957736270787015555281492220757292858206568385304706192386416009657097062675214919086924216423433082063409209311813441547525266882033030668389112810244305096535177323575119407014819701961205635561634299118583642973681614473867812760938254926147367318960324585092493458614097308885022089170245855482501639479877016629089888620237451538542215959748191190996154872699122004208858124356425712289922851204949134411296871871505058976506035287831568373306323310695563258651236862057327569996796911418552990931961498290680579647629977698154027601737797565070075670436437896473389755670610648189530779671896891147235752619825335341831322815436136245747406230116513486353562601815554701725083110004688886614174662693748369757301146366654631875732233511601846261172108525514149644247885971023535804115307394827643499777188215486121755438199799974589394310076094346886917173548688179362619895779807540625016179427636036019351588403299774724856215195371747489704244497091701187959447220506739300275179481331762578140018563599145933801046835852603238159978903048913593666079142988674647257869565599811291804268574482598601239002812924615248443546197951688030321300760876091551080394357570206848563007174933062203385569468701074474453445181914471929569957932053554812974962824730533730321134981872742052460822465894315329796485647981106519209011070672227096921158799879437700574304848454981802421492286924451866419782080313978740292819201278161706224217725190371403757643026425623517826097611507643390259047590959932320545975284905982569652107326483812384715289985015459922154716822488321689550299263619341284113403436700781861588646420485438604540704027253441622650851675586492071210226532484984591013815461270342863783178683556187689063539912330972619666981892869317909270155819553452716936453676065787164609958676345722669724366516240566266437213654002248924605767519825524209815555833816522154978528910130474700299093317031044211046499872477143240327616617922983636426879957616855080920171289624631399643044926826859302733475147604311961190699077188429263949513452638462772625523478131071010133683582732987635966888334444166545133327777444950723754056816509592356504697117206941441165086849098972184037539794426671844030825833598853963114053824272932540517635711466482759453660721092062140898635239403909145540034949144004169612367460203691048738979781621164967729498632571736651022575485003412715989505615918816044598119400139330568417038172877563337999983250824731788378825900711541921702608288945567177423468793416752642938061266551297859681355577376381057215722300869238366170358650342498421330507990183857556924897965345058959140779958958539450309245045806703864539795637542958885985702987995937529239296860784907341981603308133066795374351314700910108776438125912477798323517153710396153185384044296997650774166602334305686826095686072735997307216804515717706691064830830039274370337931442167526341392075205171338884374247627205672231641873433802187192310055109876868922197752744289994593440764759961686774526545765501935087092519809508864042914699268218861038321472400274858274379127887774609639024710710010354246368036753163679085955338782446481692502409390267529445980102117063380633877777427298698152522242904231639473660870716516498037296215852813557422423482411368716331820788501942447761707086086382920195423676221267291530130105693483847048880634760003583

Complejos de de Rham y cohomología (Derivaciones parte 1/4)

Esta es una especie de continuación de un post donde traté de llegar desde el cálculo hasta la cohomología de de Rham utilizando rotacional, divergencia y gradiente (De Rham), pero es hora de hacerlo formalmente, y para ello necesitaremos imaginarnos unos espacios que se llaman diferenciales de Kähler, antes hablé de diferenciales y k-formas diferenciales , pero lo retomaremos, el punto de este post será poder usar la cohomología de de Rham para saber si una curva hiperelíptica sobre un campo finito es segura criptográficamente hablando calculando el número de elementos de su jacobiana el cuál nos dice sobre su seguridad de acuerdo a su factorización, y para esto utilizaremos el teorema del punto fijo de Lefschetz sobre el morfismo de Frobenius en característica 0 p-ádico (lift a $latex \mathbb{Q}_p$) definido en el primer grupo de cohomología de una subálgebra de de Rham, para eso primero veremos como construir toda el álgebra de de Rham usando diferenciales de Kähler.

Pero antes de todo esto necesitamos empezar con los preliminares, que serán el concepto de derivacion en cualquier álgebra.


Derivaciones en un punto

La derivada en dirección de un vector tangente $latex v$ a un punto $latex p\in \mathbb{R}^n$ de una función $latex f\in C^{\infty}(\mathbb{R}^n)$ es un número real:

$latex D_v(f):=\sum_{i=1}^n x_i(v) \frac{\partial f}{\partial x_i}(p)$

Donde $latex x_i$ son las coordenadas en $latex \mathbb{R}^n$ y $latex x_i(v)=v_i$ (i-ésimo componente de $latex v$)

Para todo vector tangente $latex v$ a un punto $latex p\in \mathbb{R}^n$ tenemos que la derivada direccional en $latex p$ nos da un mapeo de espacios vectoriales

$latex D_v:C^{\infty}_p\rightarrow \mathbb{R}$


que manda $latex f$ definida en $latex p$ a un número real, en general la función $latex D_v$ está definida como:

$latex D_v=\sum x_i(v) \frac{\partial}{\partial x^{i}}\mid_p$


Tenemos que $latex \forall v\in T_p(\mathbb{R}^n)$ hay un $latex D_v$ y todos cumplen la regla de Leibniz, es decir $latex D_v(fg)=(D_vf)g(p)+f(p)D_vg$.

Todos los mapeos $latex \mathbb{R}$-lineales $latex D:C^{\infty}_p\rightarrow \mathbb{R}$ que satisfacen la regla de Leibniz son derivaciones en $latex p$  y denotamos a todas las derivaciones en $latex p$ como $latex \mathbb{D}_p(\mathbb{R}^n)$ y de hecho este espacio es un espacio vectorial ya que dos derivaciones sumadas en el mismo punto es una derivación, y como es $latex \mathbb{R}$-lineal no pierden la propiedad de Leibniz al multiplicarlas por un escalar, entonces por ahora ya tenemos que TODAS las derivadas direccionales en $latex p$ son todas las derivadas en $latex p$ por lo que tenemos un mapeo.


$latex \phi:T_p(\mathbb{R}^n)\rightarrow \mathbb{D}_p(\mathbb{R}^n)$
$latex v\mapsto D_v=\sum x_i(v) \frac{\partial}{\partial x^{i}}\mid_p$


Como $latex D_v$ es lineal en $latex v$ , el mapeo $latex \phi$ es un mapeo de espacios vectoriales, faltaría ver qué sucede con las constantes, es decir que si $latex D\in \mathbb{D}_p(\mathbb{R}^n)$ entonces si $latex c\in\mathbb{R}$ entonces $latex D(c)=0$ pero esto se sigue que la linealidad y la regla de Leibniz haciendo que $latex c=1c$.

Función $latex \delta$ de Kronecker

Ésta es una función muy útil para la notación
$latex \delta_j^i=\left\{\begin{array}{11} 1&\mbox{if } i=j\\ 0 & \mbox{if }i \neq j \end{array}\right$

Ahora, tenemos que es fácil demostrar que $latex \phi$ definido previamente es un isomorfismo, es decir $latex T_p(\mathbb{R}^n) \cong \mathbb{D}_p(\mathbb{R}^n)$ ya que si procedemos naturalmente al suponer que $latex D_v=0$ para algún $latex v\in T_p(\mathbb{R}^n)$ entonces $latex 0=D_v(x_j)=\sum_i v^i \frac{\partial}{\partial x_i}\mid_p x_j = \sum_i x_i(v)\delta_i^j = x_j(v)$ y entonces $latex v=0$ lo que nos dice que $latex \phi$ es inyectiva.

Aquí la función $latex \delta$ nos ayuda a eliminar las parciales en las variables que no son iguales al índice con notación más limpia, la suprayectividad la pueden demostrar ustedes.

Lo que sucede aquí es que para todo vector tangente a $latex p$ tenemos una derivación en $latex p$ entonces si ambos son espacios vectoriales, uno de puntos... y otro de derivaciones, lo más natural es identificar sus bases estándares, si $latex \lbrace e_1,e_2,...,e_n \rbrace$ es base de $latex T_p(\mathbb{R}^n)$ entonces bajo este isomorfismo tenemos que:

$latex \phi(e_i) = \sum_i \delta_i^j \frac{\partial}{\partial x_i}\mid_p=\frac{\partial}{\partial x_i}$

Por lo que: 

$latex \bigg \lbrace \frac{\partial}{\partial x_1}\mid _p,..., \frac{\partial}{\partial x_n}\mid_p\bigg\rbrace$ genera al espacio vectorial $latex \mathbb{D}_p(\mathbb{R}^n)$ y es su base estándar.

Con esto nos conviene denotar a los vectores $latex v\in T_p(\mathbb{R}^n)$ tangentes a $latex p$ más explícitamente en términos de la base de $latex \mathbb{D}_p(\mathbb{R}^n)$ los cuales son puntos $latex v=\sum v_i e_i = \sum x_i(v) e_i = (v_1,...,v_n)$ como:

$latex v=\sum v_i \frac{\partial}{\partial x_i}\mid_p$


Campos vectoriales

Si $latex U\subset \mathbb{R}^n$ es un abierto un campo vectorial $latex X$ es una función que asigna a $latex p\in U$ un vector tangente $latex X_p \in T_p(\mathbb{R})^n$, este vector $latex X_p$ en términos de la base $latex \bigg \lbrace \frac{\partial}{\partial x_j}\mid_p \bigg \rbrace$ es:

$latex X_p=\sum a_i(p) \frac{\partial}{\partial x_i}\mid_p = (a_1,...,a_n)$ 

con $latex p\in U$, $latex a_i\in C^\infty(U)$, $latex a_i(p)\in \mathbb{R}$ 

Podemos omitir la $latex p$ en este caso y decir que el campo vectorial $latex X=\sum a_i \partial/\partial x_j$ 

Ejemplos típicos:

$latex X=\frac{-y}{\sqrt{x^2+y^2}}\frac{\partial}{\partial x}+\frac{x}{\sqrt{x^2+y^2}}\frac{\partial}{\partial y}= \bigg ( \frac{-y}{\sqrt{x^2+y^2}},\frac{x}{\sqrt{x^2+y^2}} \bigg )$

y

$latex Z=\frac{x\partial}{\partial x} + \frac{-y\partial}{\partial y}=(x,-y)$

Es importante la notación como punto y la de vector para que noten la base y la importancia del operador $latex \partial/\partial x_i$

Aquí están los dos campos vectoriales dibujados en $latex \mathbb{R}^2\setminus \lbrace 0 \rbrace$ y $latex \mathbb{R}^2$ respectivamente, ustedes vean la definición y el dibujo.

Entonces un campo vectorial $latex X=\sum a_i \partial/\partial x_j$ nos permite "mover" la $latex p\in U\subset \mathbb{R}^n$  , podemos multiplicar cualquier función $latex f\in C^{\infty}(U)$ por un campo vectorial $latex X$ y aún así seguir teniendo un campo vectorial ya que $latex fX=\sum (fa^i)\partial/\partial x_i$ es un campo vectorial $latex C^\infty$ en $latex U$ por lo que podemos sumarlos y multiplicar por 'escalares' del anillo $latex C^\infty(U)$ entonces tenemos que todos los campos vectoriales en $latex U$ los denotamos por $latex \mathfrak{X}(U)$ es un $latex C^\infty(U)-$módulo 


Derivaciones a partir de campos vectoriales

Vamos a definir más derivaciones ahora a partir de esto.

Sea $latex X \in \mathfrak{X}(U)$ con $latex U\subset \mathbb{R}^n$ y sea $latex f\in C^{\infty}(U)$ definimos la función $latex Xf$ en $latex U$ como:

$latex (Xf)(p)=X_pf = \sun a_i(p)\frac{\partial f}{\partial x_i}(p)$   $latex \forall p\in U$

sin la $latex p$ tenemos que la función es $latex Xf=\sum a_i \frac{\partial f}{\partial x_i}$
donde se ve claramente que $latex Xf\in C^\infty(U)$ , por lo que podemos definir a el campo vectorial $latex X$ como una función que mapea funciones a funciones

$latex X:C^{\infty}(U)\rightarrow C^\infty(U)$
$latex f\mapsto Xf$


Como podemos intuirlo este mapeo para todo campo vectorial cumple la regla de Leibniz es decir

$latex X(fg)=(Xf)g+fXg$

Ya que puntualmente se cumplirá la regla de Leibniz si ustedes lo verifican.

Una derivación en el álgebra $latex C^\infty(U)$ sobre  $latex \mathbb{R}$ es un mapeo $latex \mathbb{R}$-lineal
$latex D:C^{\infty}(U)\rightarrow C^{\infty}(U)$ tal que $latex D(ab)=(Da)b+aDb$ donde $latex a,b\in C^{\infty}(U)$ .

Todas las derivaciones de $latex C^{\infty}(U)$ están cerradas bajo suma y multiplicaciones escalar por lo que forma un espacio vectorial el cual lo llamamos $latex Der(C^{\infty}(U))$ y esto funciona con cualquier álgebra, no sólo con las funciones infinito diferenciales, por lo que tenemos el siguiente mapeo


$latex \Phi:\mathfrak{X}(U)\rightarrow Der(C^{\infty}(U))$
$latex X\mapsto [f\mapsto Xf]$

Esto como imaginarán es un isomorfismo lo que quiere decir es que todos los campos vectoriales de un abierto $latex U$ pueden ser identificados con derivaciones del álgebra $latex C^{\infty}(U)$.

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

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

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

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

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

El teorema de Hasse dice.

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

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

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

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

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

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

Teoría necesaria.

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




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



Motivación de la demostración de Hasse

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


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



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


Espero les haya servido.

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

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

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

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

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

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

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


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

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

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

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

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

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

Ahora, ya para geometrizar esto por completo, considera:

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

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


Isogenias

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

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

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


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

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

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

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

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

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

Decimos que un mapeo racional entre dos curvas proyectivas

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

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

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


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

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

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

$latex P\mapsto 2P$

Pueden demostrar que eso realmente es una isogenia

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

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

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

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


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

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

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

donde

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

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


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

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

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

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

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

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

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

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

Corolario-Definición

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



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


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

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

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

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

Teorema: 

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

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

Esto es muy fácil de probar

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

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

$latex \alpha_n$

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

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

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


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


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

entonces:

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


Con esto ya estamos bien equipados.

j-Invariante

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

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

Llamada j-invariante que cumple que:

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

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

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

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

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

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

Torsiones cuadráticas de curvas elípticas

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

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

Ejemplo:

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

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

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

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

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

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


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

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

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

o

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

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

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

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

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

bajo las siguientes operaciones

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

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

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

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

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

esto debería ser para ustedes pero lo pongo.

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

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

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



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

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