The last digit of pi is 1

One of the most interesting Chuck Norris facts states that he knows the last digit of pi. The other day I was thinking that maybe I could join team Norris and find it too.

Now, finding what is the last digit in the decimal expansion of a number is actually something that is not well defined. Even thought that we can say that the last digit of $1/2=0.5$ is 5 and we could argue that the last digit of $1/3=0.\bar{3}$ is 3, for example, for $13/99=0.\overline{13}$ the digits are periodic and hence 1 and 3 will keep repeating without reaching a limit. We of course could say that the last digit for this is the last digit appearing on the period, which gives 3 in base 10.

Likewise, if we define the sequence $d_n$ to be the $n$th digit of the decimal expansion of $\pi$, we have that 

$$\lim_{n\to\infty}d_n$$

does not exist. So maybe we can twist the question a little in order to make it more sound. 

A very nice approach is to use continued fraction representation of numbers,

$$x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ddots}}}\,.$$

Here the $a_i$ are integers. Usually this is abbreviated as 

$$x=[a_0;a_1,a_2,a_3,\dots]\,.$$

With this notation we get rid of the problem about the base expansion, as it is independent from the base in which the numbers are written. Here the problem about finding the last digit of rational numbers is straight forward, as rationals have a finite continued fraction expansion. For example $13/99=[0; 7, 1, 1, 1, 1, 2]$, that is

$$\frac{13}{99}=0+\cfrac{1}{7+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2}}}}}}\,.$$

Then we can say that the last number on the expansion of $13/99$ is $2$. This even works for irrational numbers. For example $\sqrt{2}$ has an expansion as continued fraction $\sqrt{2}=[1;\bar{2}]$, that is

$$\sqrt{2}=1+\cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{2+\ddots}}}\,.$$

Hence we can say that the last number of $\sqrt(2)$ is $2$. Still, not all irrationals have nice continued fraction representations. For instance 

$$\frac{1+\sqrt{3}}{2}=[1;\overline{2,1}]\,,$$ 

which throw us back to the original problem of periodic expansions. This time though, we have a nice ace under the sleeve. It is due to Galois and it establishes an outstanding result about quadratic surds.

It states that given a reduced surd $\alpha=[\overline{a_0;a_1,a_2,\dots,a_n}]$, its conjugate $\phi(\alpha)$ has a relation with the number obtained by reversing the order of the continued fraction expansion for $\alpha$.  This relation is given by

$$-\frac{1}{\phi(\alpha)}=[\overline{a_n;a_{n-1},a_{n-2},\dots, a_1,a_0}]\,.$$

The conjugate $\phi$ is pretty much like the more familiar complex conjugate, but in a more general setting. The conjugate of a quadratic surd simply changes the sign of the radical, 

$$\frac{P+\sqrt(D)}{Q}\mapsto\frac{P-\sqrt(D)}{Q}\,.$$

Thus in the case of 

$$\alpha=\frac{1+\sqrt{3}}{2}$$, we have that the inverse negative of its conjugate should have a reversed continued fraction expansion,

$$\frac{2}{\sqrt{3}-1}=[\overline{2,1}]\,.$$

Thus, is we follow the original idea as for periodic rationals, the last number of $(1+\sqrt{3})/2$ is  $2$, which is the first number of $2/(\sqrt{3}-1)$.

In order to understand how to use this in the general case,  the role of the discriminant is important. For example, for complex numbers we have that $D=-1$. This is called the discriminant and it is related to the quadratic equation that the number satisfy. That is, if $\alpha$ is a quadratic surd, it is the zero of a quadratic polynomial

$$p(\alpha)=a\alpha^2+b\alpha+c=0\,,$$

and $D=b^2-4ac$. The beauty of the conjugate function $\phi$ is that it permutes the roots of the polynomial $p(x)$. In the case of the complex numbers, $D=-1$ and the polynomial is 

$$p(x)=x^2+1\,.$$

We have then that the conjugation takes one root of this polynomial into the other $\bar{i}=-i$. In general, this can be done for any polynomial $p(x)$ of higher degrees. When we go to higher degrees, there is more than one involution that permutes the roots of $p$.  This is the area of study of Galois Theory (no wonder why is connected to the original thing!)

Galois reversing result works only for reduced quadratic numbers, but taking this idea, we can extend it for more general situations,

Let $\alpha$ be the zero of a function $f(x)$ and let $\phi$ be a function that

permutes the roots of $f(x)$. If $-1<\phi(\alpha)<0$ then define the last

number for $\alpha$ to be the first number on the continued fraction of 

$$-\frac{1}{\phi(\alpha))}\,.$$

In the case of $\pi$, we have that $f(x)=\sin(4x)$ is a possibility. Now we need an involution on the roots of $f$. Let $\phi$ be such that $\phi(\pi)=-\pi/4$. Then we can say that the last number of $\pi$ is the same as the first number of 

$$\frac{4}{\pi}=[1; 3, 1, 1, 1, 15, 2, 72, 1, 9, 1, 17, 1, 2, ...]$$

which is 1. 

A naive way of thinking about this is that we can regard $\pi$ as a number with an infinite period and thus the scheme could give something meaningful. But of course, this definition is not well defined as there are infinite possible involutions for the set or roots of $f(x)$. These involutions form a group known as the infinite dihedral group, $D_\infty$.

If there is anything like Galois theory for analytic functions maybe we could find the last number in $\pi$. 

Números analíticos y meromorfos

Hace unos días hablábamos con Vinicio sobre la naturaleza de los números reales. Tradicionalmente los reales se dividen en naturales, enteros, racionales e irracionales.

$$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\,,\qquad\mathbb{Q}\cup\mathbb{I}=\mathbb{R}\,.$$

Históricamente esta clasificación de los números viene dada por las propiedades algebraicas que presentan.  Primero tenemos a los números naturales que surgen de la necesidad del hombre de contar sus bienes. Contar ovejas, alimentos, terreno, etc. Al iniciar las relaciones comerciales se ve la necesidad de "juntar" y "quitar" objetos, así como de representar deudas y créditos. Con esto surgen los números enteros. 

Hasta este punto, los números eran nada más utilizados para contar, ya sea lo que se tiene o lo que se debe, sin embargo con el desarrollo de la geometría, la construcción y la fabricación de objetos, aparece otra necesidad en el ser humano: medir.

Los racionales surgen de considerar mediciones y proporciones entre estas. Hubo que esperar muchos cientos de años hasta que se consideró un conjunto más completo de números. Los reales son obtenidos por medio de considerar la noción de límite. Esto viene de realizar el paso entre lo discreto y lo continuo. 

Algebraicamente se puede describir esto partiendo de $\mathbb{N}$ como el conjunto base dotado de suma. Luego $\mathbb{Z}$ se obtiene al considerar también la resta. Resulta ser que los enteros admiten multiplicación, y para obtener los racionales, se considera la división. Los reales aparecen con el cálculo integral y diferencial. 

Sin embargo, otra forma muy interesante de realizar esta clasificación de los números viene de estudiar sus propiedades por medio de analizar funciones sobre ellos.

Los enteros surgen de considerar ecuaciones del tipo

$$x+n=0\,,$$

donde $n$ es un natural. Esta ecuaciones tendrá soluciones enteras, mas no naturales (excepto $n=0$). Similarmente, al considerar las ecuaciones del tipo 

$$bx-a=0$$

con $a,b$ enteros y $b\neq0$, tenemos que las soluciones son racionales. 

Esta es la idea detrás de los números algebraicos, los cuales son soluciones de polinomios sobre enteros.  

Los algebraicos incluyen a los racionales, sin embargo números irracionales como $\sqrt{2}$ son algebraicos. También hay reales que no so algebraicos, tal es el caso de $e$ y $pi$. Estos se llaman trascendentes.

Una forma de seguir clasificando a los reales por características de este tipo es por medio de considerar soluciones reales a ecuaciones del tipo

$$f(x)=0\,.$$

Para $f$ un polinomio de grado $n$, se dice que $x$ es un algebraico de grado $n$. Es decir, si $f$ es de la forma

$$f(x)=\sum_{k=0}^na_kx^k\,,$$

con $a_k\in\mathbb{Z}$ (o equivalentemente $a_k\in\mathbb{Q}$).

Siguiendo con esta idea, podemos definir los números analíticos  como aquellos que son soluciones de funciones de la siguiente forma

$$\sum_{k=0}^\infty a_kx^k\,$$

para series con un radio de convergencia positivo. Con esto tenemos que $pi$ es analítico, ya que  para $$f(x)=\sin(x)=\sum_{k=0}^\infty \frac{(-1)^{k}}{(2k+1)!}x^{2k+1}$$

 tenemos que $f(\pi)=0$. De igual manera $\ln(2)$ es analítico, pues

$$f(x)=e^x-2=-2+\sum_{k=0}^\infty \frac{1}{k!}x^k$$

anula a $\ln(2)$. Sin embargo, parece ser que $e$ no es analítico, pero $e-1$ si lo es. Lo extraño de esto viene de que acá consideramos convergencia y ya no es posible en general reordenar términos en las series sin afectar la convergencia.

Aunque los analíticos parecieran cubrir una porción mucho más grande de los reales, estos son nada mas contables. Esto se puede ver dado que cada coeficiente $a_k$ es racional, y tenemos un numero contable de estos. Además, las funciones analíticas distintas de cero solo tienen un numero contable de ceros.

Otro tipo de números que pueden definirse siguiendo esta linea son los números meromorfos, los cuales vienen de encontrar los ceros de funciones de la forma

$$f(x)=\sum_{k=-\infty}^\infty a_kx^k\,,$$

con $a_k\in\mathbb{Q}$. Por la misma razón de antes, estos también seran solo un número contable, así que faltan muchos más por clasificar. Quizás esta linea pueda seguirse para poder ir abarcando poco a poco la totalidad de los reales.

The geometry of irrationals

Many years ago I remember reading about irrational numbers and the various surprising things they hide. One nice thing about irrationals is that even thought we think of them as being bad behaved and ugly, we can still classify them further. For example, we have irrationals that are also algebraic, that is, they are zeros of a polynomial with integer coefficients.

We can think that rationals are algebraic of degree 1, while algebraic of degree 2 include $\sqrt{2}, \sqrt{3} $, the golden ratio, etc.

Then we have numbers that are not algebraic, that is, they are not zeros of polynomials with integer coefficients. These are called Transcendental. Some of the famous ones in this category are $\pi, e$, Liouville's constant, etc.

Another way of studying irrational numbers is by measuring how irrational are they. This really means to study how well a number can be approximated with rational numbers, that is, loosely speaking, how fast the denominators of the fractions approximating the number have to grow to stay close to it.

We can think that this has to do with the representation of real numbers with approximations by rationals. In a more philosophical way, this irrationality measure can tell how well we can approximate numbers in the math world, with numbers in the real world.

Liouville was big into approximating irrationals with rationals trying to do it in the most efficient way, that is, controlling the size of the denominators. More recently, Roth made contributions into a deeper understanding of this, leading him to win the Fields Medal in 1958.

Looking at this Facebook post about the integer lattice in $\mathbb{R}^3$, I remember an attempt at defining another way of measuring the irrationality of a number.

First, consider the integer lattice in $\mathbb{R}^2$.  Given a real number $m$, graph the line $y=mx$.  Thus the line will hit the lattice if and only if $m$ is rational, so the idea is to analyze what happens when $m$ is irrational.

For this, consider the following: consider a radius $r>0$ and draw the biggest circular sector of radius $r$ that is symmetric around the line $y=mx$ and that does not contain any point of the lattice.

That is, the sector must not contain any of the blue points from the lattice.  Now, the idea is to measure this area and treat it as a function of the radius $A_m(r)$. I created a GeoGebra demonstration to show the idea of the sector.

Here you can see how the area of the sector changes when the radius changes, and also how the procedure varies when considering different values for $m$.

Effectively what happens is that we are looking for the best approximation of the number $m$ using a fraction $p/q$ with $p^2+q^2\leq r^2$. This way we control the size of both numbers for the approximation of $m$.

Thus we have that

$$A_m(r)=r^2\big|\arctan(m)-\arctan(f_m(r))\big|\,,$$

where $f_m(r)$ is the best approximation to $m$ with a rational inside the circle of radius $r$, that is

$$f_m(r)=\min \big|m-\frac{p}{q}\big|\,,\quad \text{ where }p^2+q^2\leq r^2\,.$$

Now, the trick is to analyze $A_m(r)$ as $r\to\infty$. One might think that this is trivially zero, since any irrational can be written as the limit of a sequence of rationals, but we also have the radius growing up to infinity, hence becoming an indeterminate form.

That is, it might be possible to propose another irrationality measure as

$$\nu(m)=\lim_{r\to\infty} \sup A_m(r)\,.$$

The $\sup$ just ensures the existence of $\nu(m)$, we don't even know if there is a limit!

If $m$ is rational, this is exactly zero, but the question would be what happens for $m$ irrational. I did some numerics to have an idea of this measure for a couple of cases. Of course this is no evidence, as a limit like this cannot be trivially calculated using numerical methods, but at least gives a bit of insight.

For example, for $m=\sqrt{2}$ we have that the graph of $A_{\sqrt{2}}(r)$ seems to oscillate between 0.2 and 1.4. We can see here that the peaks happen when a new rational approximation is found. Naively speaking, $\sqrt{2}$ is not hard to approximate with rationals, and hence we don't have to increase too much in $r$ to find a new approximation.

On the other hand, for $m=\pi$ we have a different behavior. We have a series of good approximations, but then suddenly we cannot find any more good approximations. Even though it looks like $A_\pi(r)$ went to 0 around $r=400$, if we zoom in we can see that it is slowly rising finding a new approximation. 

I believe this is a very interesting topic and I think there is something nice waiting to be discovered here. Even if it leads to the same notion as the Liouville-Roth exponent, this would provide a more geometric interpretation of the behavior of irrational numbers. 

Con matemáticas no hay sorpresas

Para muchos, las recientes elecciones en Guatemala han resultado en una gran sorpresa debido a sus resultados. Sin embargo, con matemáticas no hay sorpresas.

Hace mas de un mes hice varias proyecciones utilizando los resultados de varias encuestas, tanto las principales, como las diversas encuestas encontradas en internet. Los resultados de las proyecciones en base a las principales encuestas publicadas en medios impresos arrojaron que

Comparación entre proyecciones y resultados actuales

en donde se tenía un error de aproximadamente 3%. Al analizar las proyecciones que incluían las encuestas realizadas por internet se encuentra que estas estaban muy sesgadas, aunque igualmente la tendencia de FCN al primer lugar y a una diferencia muy estrecha entre UNE y LIDER seguía observándose (menos de un 3%).

Participación en elecciones pasadas para 1era y 2nda vuelta

Otra de las grandes sorpresas fue la participación ciudadana. Al momento se calcula que ha sido del 71.32%, algo que no se había dado en la historia política de Guatemala. Sin embargo, al analizar la historia de todas las elecciones desde 1985 se puede observar una tendencia interesante.

Los datos en azul representan los porcentajes de participación en primera vuelta (incluyendo la del 2015) y los datos en rojo la participación en segunda vuelta. A partir de 1995 se nota que la tendencia a la participación ha ido en aumento casi constante, por lo que se puede realizar un análisis de valores atípicos para poder encontrar un modelo de regresión lineal que pueda describir los datos. Al realizar esto, se obtiene que los datos están correlacionados en 98.49% para la primera vuelta, y 95.98% en la segunda vuelta.

Comparación entre proyecciones y valores actuales

Con esto, se tenía que la proyección daba una participación del 72.39%, lo cual difiere en 1.07% del valor actualmente registrado. Así mismo, se espera que en segunda vuelta haya una participación de al rededor del 63.4%. 

Al analizar datos de una forma sistemática y formal, no existen sorpresas. 

Series de tiempo dan 20% de abstencionismo y 2% de votos blancos/nulos

Siguiendo con el análisis de datos para estas próximas elecciones en Guatemala, es posible dar un estimado de los porcentajes de abstencionismo y de los votos validos que ocurrirán en esta ocasión.

Utilizando un modelo de series de tiempo, es posible modelar los datos de todas las elecciones ocurridas en Guatemala desde 1985 hasta la fecha.  En base a los datos publicados por el Tribunal Supremo Electoral de Guatemala, se puede obtener una proyección del porcentaje de abstencionismo esperado para estas elecciones del 2015.

Siguiendo la metodología desarrollada en este post, se obtiene que el porcentaje esperado de abstencionismo es del $20%$, con una incerteza del $2%$.

Así mismo, es posible estimar el total de votos nulos/en blanco dentro del total de votos válidos. Al realizar esta proyección, se espera que solamente el $2%$ de los votos válidos son en blanco o nulos.

Esto quiere decir, que con un estimado de más de ocho millones $(8200000)$ habitantes empadronados, solamente seis millones y medio $(6560000)$ asistirán a votar, y de estos , ciento treinta mil $(131200)$ serán votos blancos o nulos.

Elecciones 2015 Guatemala: Modelos de Markov dicen Morales y Baldizón

Estando a menos de un mes de las elecciones presidenciales en Guatemala, quise evaluar los datos existentes sobre las encuestas realizadas. 

Un primer reto fue el encontrar los datos de las encuestas, lastimosamente a pesar de la era tecnológica en la que vivimos, estos datos no están facilmente disponibles. Las referencias de los datos se encuentran al final.

Para poder realizar una proyección de los comicios de este 6 de Septiembre de 2015, es posible tratar los datos de las encuestas como una Cadena de Markov, en donde cada encuesta es un estado en el espacio de distribución de intensión de voto.

Si suponemos que hay $n$ partidos, la idea es utilizar un tipo de Modelo Oculto de Markov con una matriz de transición $T=(t_{ij})$ donde $t_{ij}$ es la probabilidad de que un votante que tenía intención de votar por el partido $i$ cambie de parecer y vote por el partido $j$. Acá, la matriz $T$ es desconocida. El objetivo es encontrar la matriz de transición para poder obtener el estado estable del sistema de Markov.

Para estimar estos datos, se puede definir el espacio de estados como los resultados de las encuestas, en order cronológico. De esta manera se ve la intención de voto como un sistema dinámico.

Con esto, se tiene que 

$$TE_n=E_{n+1}\,,$$

donde $E_n$ es la enésima encuesta considerada. En esta estimación fueron utilizadas 11 encuestas, $E_1,E_2,\dots,E_11$. Con estas encuestas, se obtienen 10 estimadores de la matriz $T$, 

$$T_n=\left(E_{n+1}E^t_{n}\right)\left(E_nE^t_n\right)^{-1}\,.$$

Para poder realizar una estimación de la matriz de transiciones a partir de las matrices $T_n$, es posible analizar la media y desviación de las componentes de las matrices $T_n$, 

$$M=E(T_n)\,,\qquad S^2=E(\left(T_n-T\right)^2)\,,$$

donde las operaciones se hacen componente por componente. Con estos datos, se pueden obtener los intervalos de confianza para los valores de la matriz de transición utilizando el teorema del limite central y la distribución t de student por tener un numero menor de 30 muestras con un $\alpha=5\%$.

En este cuadro están las diferentes proyecciones considerando las encuestas de internet, las impresas, y todas las encuestas, tomadas en orden aleatorio y en orden cronológico.

Con estos datos, se calculan las medias y desviaciones de las proyecciones, para poder calcular el margen de error del modelo. $LI$ y $LS$ denotan los límites inferior y superior respectivamente de las proyecciones realizadas. 

Los datos en verde muestran los candidatos con mayor intensión de voto proyectada, mientras que los datos en amarillo muestran los candidatos con la segunda intensión de voto proyectada. Es de notar que al considerar todos los datos, el porcentaje comprendido en otros resulta ser el segundo lugar. 

En todas las proyecciones, salvo las realizadas con datos de internet solamente, se tiene que hay segunda vuelta entre FCN y LIDER, teniendo FCN un amplio margen sobre el segundo lugar, con un error promedio del $2.77\%$.

Considerando los posibles escenarios, es posible que haya una segunda vuelta entre FCN y UNE o entre FCN y FUERZA, siendo la segunda la más probable, sin embargo FCN y LIDER es la combinación esperada.

[Referencias de datos]

• https://es.wikipedia.org/wiki/Elecciones_generales_de_Guatemala_de_2015
• http://www.soy502.com/articulo/jimmy-morales-revelacion-encuesta-revista-contrapoder
• http://www.poll-maker.com/results330703x2e3146C6-12#tab-2
• http://www.deguate.com/artman/publish/politica-elecciones2015/2a-encuesta-electoral-Junio-2015.shtml#.VcfflBNViko
• http://eleccionesgt.aquitodito.com/encuesta-tu-por-quien-votarias-para-presidente-de-guatemala
• http://www.guatemalaelecciones.com/encuesta-presidencial-online-guatemala.php

Seguridad, criptografía y grupos simétricos

Hoy en mi clase de matemática discreta hablamos sobre criptosistemas, y en especial, sobre el sistema RSA como un ejemplo de un sistema de llave pública.

Un ejemplo de un criptosistema sencillo es cuando en la escuela jugábamos a mandar mensajes o hablar un lenguaje inventado, el cual solo uno y su mejor amigo sabían hablar. Para esto, se tiene una llave que sirve para encriptar el mensaje,  y la misma llave sirve para descifrarlo. Esto puede ser muy sencillo de implementar, sin embargo cuenta con la desventaja de que debe haber una reunión previa para ponerse de acuerdo en la llave, es decir el cifrado. 

En el ámbito de la escuela, esto resulta suficiente, sin embargo para aplicaciones mas elaboradas, como transacciones por internet, resulta poco práctico. Si por ejemplo compro algo por internet, quiero enviar me manera segura mi numero de tarjeta de crédito, es decir, que solo el destinatario pueda leerla. Siguiendo el sistema anterior, para poder enviar mi mensaje, tendría que haberme reunido con el vendedor anteriormente y ponerme de acuerdo con el en una clave, pero si me hubiese reunido con el antes, le hubiera dado mi número de tarjeta en primera instancia y no me encontraría en este dilema.

La idea de los criptosistemas modernos (asimétricos) es prescindir de la necesidad de un acuerdo previo, y hacerlo todo remotamente. Suena como magia negra, y en cierto modo, lo es.

La magia negra utilizada es matemática, y en particular, algebra moderna. La idea es poder crear una forma de cifrar y descifrar mensajes que resulte difícil de hackear.  Ahora bien, el problema comienza con entender qué significa que algo sea difícil de hackear.

Primero, nuestro objetivo es poder mandar mensajes de una forma segura a través de un canal inseguro. Para esto tenemos un conjunto $M$ de mensajes que podemos mandar. Antes de cifrar un mensaje, es necesario codificarlo, lo que significa traducir la información y manejarla como un objeto matemático.

Para codificar un mensaje, tenemos un conjunto $G$ de códigos y una función codificadora

$$g:M\to G\,,$$

$$m\mapsto g(m)\in G\,.$$

Esto simplemente es una traducción y no contiene ningún aspecto de criptografía, al menos no algo relevante.

Luego, tenemos una función encriptadora,

$$E:G\to G\,,$$

la cual sirve para cifrar los mensajes. Nótese que no se tratan de los mensajes en si, sino de la codificación de los mismos.

Por último, se tiene una función desencriptadora,

$$D:G\to G\,,$$

tal que $D\circ E=\text{Id}$, la identidad en $G$. Con esto,  el proceso total para transmitir un mensaje $m$ resulta ser

$$g^{-1}\circ D \circ E\circ g(m)=m\,.$$

La parte relacionada con criptosistemas se enfoca en el medio, en $E$ y $D$, la cual es mas teórica. La parte de codificación tiene que ver mas con aspectos físicos del medio sobre el cual se realiza la transmisión.

Ahora bien, la magia de la criptografía recae en el conjunto $G$ y las funciones definidas sobre $G$. Desde un punto de vista computacional, $E$ y $D$ son algoritmos que poseen cierta complejidad computacional. Que nuestro sistema sea difícil de hackear significa que las funciones sean altamente complejas. Esto, a grandes rasgos, significa que es necesario invertir muchos recursos para poder obtener un resultado. Generalmente el recurso crítico resulta ser el tiempo.

Las funciones $E$ y $D$ son las que se conocen como las llaves del criptosistema, y es necesario entonces poder tener una forma de generar dichas llaves.

Una de las maneras de atacar esto es hacer que el conjunto $G$ tenga la estructura de grupo. Entonces, se pueden ver a las llaves como pertenecientes al conjunto de biyecciones de $G$ en si mismo, es decir, permutaciones.

Para efectos prácticos, $G$ es un grupo finito, digamos con cardinalidad $n$. Entonces se tiene que las posibles llaves son elementos del grupo de permutaciones $S_n$, el cual tiene $n!$ elementos.

Puesto que una llave $A$ es un elementos del grupo $S_n$, sabemos que su inverso $A^{-1}$ es otro elemento de $S_n$, es decir, es otra llave.  Por lo tanto $(A,A^{-1})$ sirven para encriptar y desencriptar mensajes, y vice versa.

La idea con sistemas de llave pública es que se hacen públicos el grupo $G$ y la función $A$ y se mantiene la función $A^{-1}$ en secreto. La magia del asunto es que nada más teniendo $G$ y $A$, calcular $A^{-1}$ resulta ser difícil computacionalmente hablando. Sin embargo, teniendo toda la información, sobre $G$, es fácil generar $A$ y $A^{-1}$.

Generalmente la generación de pares de llaves se realiza en base a parámetros aleatorios. Esto es, la llave $A$ depende de parámetros que uno puede escoger, es decir,  $A(P)$. Conociendo estos parámetros, es fácil generar $A^{-1}(P)$, sin embargo, sin los parámetros $P$, esto resulta difícil.

Al no tener los parámetros $P$, alguien puede encontrar $A^{-1}$ nada mas por prueba y error, tratando de encontrar el inverso de $A$ en $S_n$, multiplicando $A$ con cada elemento hasta encontrar la identidad. Para valores pequeños de $n$ esto resulta no ser tan tedioso, sin embargo ya para $n=60$ tenemos que $S_n$ tiene más elementos que el número de átomos en el universo visible.

Al final, lo crucial es el algoritmo $A(P)$, el cual toma parámetros y devuelve un elemento de $S_n$, es decir

$$A:\mathcal{P}\to S_n\,,$$

donde $\mathcal{P}$ es el espacio de parámetros, el cual suele ser un producto cartesiano del tipo $\mathbb{F}^k$.

Por lo tanto, se puede decir que el cuadro completo es

$$g^{-1}\circ A^{-1}(P)\circ A(P)\circ g(m)\,,$$

Cuando $G=\mathbb{Z}_{pq}$ tenemos el caso de encriptación RSA. Al considerar $G$ como puntos en una curva elíptica, se obtiene la criptografia de curva elíptica, y así con cualquier grupo $G$.

Siguiendo la misma idea, es posible considerar criptografía con matrices, nudos, simetrías, cohomologías y cualquier grupo que se pueda imaginar. Acá hay una lista de grupos no tradicionales con los cuales sería posible realizar criptosistemas.