Epónimos relacionados con las matemáticas

método de cribado de Brun, el teorema de Brun o criba de Brun es un resultado en la teoría de números más específicamente en teoría de cribas dado por Viggo Brun en 1919. Tiene importancia histórica en la introducción de los métodos de cribas.

La criba de Brun nos da el tamaño de ciertos conjuntos que queremos estudiar usando ciertas funciones de las cuales nos valemos para estudiar el conjunto.

Criba de Brun

Como función

Sea la función ${\displaystyle f(d)={\frac {\omega (d)}{d\prod _{p\mid d}\left(1-{\frac {\omega (p)}{p}}\right)}}}$

bien definida para todo d con ${\displaystyle \mu (d)=0}$ . Considere los siguientes conjuntos

• ${\displaystyle \mathbb {A} ^{z}=\{a\in \mathbb {A} :a\leq z\}}$
• ${\displaystyle \mathbb {P} _{z}=\prod _{p\in \mathbb {P} ^{z}}p}$
• ${\displaystyle \mathbb {A} _{d}=\{a\in \mathbb {A} :a\equiv 0\mod {d}\}}$
• ${\displaystyle \mathbb {R} _{d}(x)=|\mathbb {A} _{p}^{x}|-{\frac {\omega (d)}{p}}x}$
• ${\displaystyle S(\mathbb {A} ;\mathbb {P} ^{z},x)}$ es el número de elementos restantes en ${\displaystyle \mathbb {A} ^{x}}$ cribando por los elementos de ${\displaystyle \mathbb {P} ^{z}}$, esto es, todos los elementos restantes al quitar los números correspondientes al conjunto ${\displaystyle \mathbb {P} ^{z}}$.

Considere la siguiente función

• ${\displaystyle \omega (d)}$ es una función o comportamiento de manera tal que ${\displaystyle {\frac {\omega (d)}{p}}x\,\!}$ sea una buena aproximación a la cardinalidad del conjunto ${\displaystyle \mathbb {A} _{p}^{x}\,\!}$, esto es, que las variables implicadas en el error no sea muy grandes o sean errores admisibles.

• Suponga que ${\displaystyle |\mathbb {R} _{d}(x)|\leq \omega (d)}$.

Bajo todas estas condiciones se puede afirmar que para todo entero no negativo r existe ${\displaystyle \theta ,\theta ^{,}}$ con ${\displaystyle |\theta |\leq 1}$, ${\displaystyle |\theta ^{,}|\leq 1}$ tales que,

${\displaystyle S(\mathbb {A} ;\mathbb {P} ^{z},x)=xW(z)\left(1+\theta {\frac {1}{r!}}\left(\sum _{p\leq z}f(p)\right)^{r}\exp {\sum _{p\leq z}f(p)}\right)+\theta ^{,}\left(1+\sum _{p$

Tenga en cuenta que ${\displaystyle \exp {\sum _{p\leq z}f(p)}}$ es la ${\displaystyle {\sum _{p\leq z}f(p)}}$-esima potencia de e.

Como versión del principio de inclusión-exclusión

Una versión más simple de la criba de Brun, es una desigualdad combinatoria la cual es una versión de el principio de inclusión-exclusión. Este nos da una comportamiento asintótico del conjunto con ciertas propiedades diciéndonos a qué es menor y a qué es mayor.

Sea X un conjunto no vacío, N un conjunto finito de objetos, sea P₁,...,P_r r diferentes propiedades que tienen ciertos elemetos del conjunto X. Sea N₀ el número de elementos que no cumplen estas propiedades. Para cualquier subconjunto I={i₁,...,i_k}, del conjunto de índices {1,2,...,r}, sea N (I)=N (i₁,...,i_k) denota el número de elementos de X que tienen cada una de las propiedades de P_ik,...,P_ik. SEa N(Ø)=|X|=N. Si m es un enteno par no negativo, entonces

${\displaystyle N_{0}\leq \sum _{k=0}^{m}(-1)^{k}\sum _{|I|=k}N(I)}$

Si m es un entero no negativo impar, entonces

${\displaystyle N_{0}\geq \sum _{k=0}^{m}(-1)^{k}\sum _{|I|=k}N(I)}$

Resultados

Algunos resultados que se obtienen al usar o aplicar la criba de brun son:

• Aproximación de ${\displaystyle \pi (x)}$. A través de este método podemos estimar que existe una constante c>0, tal que:

${\displaystyle \pi (x)={\mathcal {O}}\left({\frac {x\ln \ln(x)}{\ln(x)}}\{1+\theta \,e^{-c\,\ln \ln(x)}\}\right)+o(x^{1-\varepsilon })}$

para todo ${\displaystyle \varepsilon }$ muy pequeño.

• Comportamiento asintótico de ${\displaystyle \pi _{2}(x)}$. Al igual que se puede obtener el comportamiento asintótico de los primos menores que x se puede obtener los el comportamiento de los primos gemelos menores que x:

${\displaystyle \pi _{2}(x)={\mathcal {O}}\left(x\left({\frac {\ln \ln(x)}{\ln(x)}}\right)^{2}\right)}$

• Convergencia de los primos gemelos. Como pilar de esta criba, a pesar de que se puede demostrar como consecuencia de lo anterior, esta la convergencia de la suma de los recíprocos de los primos gemelos

${\displaystyle \sum _{p,p+2=q}{\frac {1}{p}}={\mathcal {O}}(1)}$

Al número al cual converge se le conoce como la constante de Brun.

• Acerca de la conjetura de Goldbach. Viggo Brun en 1920 probó, a través de la criba combinatoria (Criba de brun), que todo número par suficientemente grande puede escribirse como suma de dos enteros cada uno producto de al menos nueve primos.

• Números producto de primos. Brun también mostró que existen infinitos enteros n tales que n, n+2 es producto de al menos 9 primos.

La criba de Sundaram es una tabla de los números naturales impares compuestos, compuesta por progresiones aritméticas organizadas en columnas. La criba se basa en el principio de que, al determinar el conjunto de los números compuestos impares, se puede deducir el conjunto de los números primos. La n-ésima columna tiene por primer término (2n + 1)² y por diferencia entre términos consecutivos d = 4n + 2. Cualquier número impar, distinto de 1, que no se encuentre en la tabla, es primo.

Considérese un número compuesto impar de la forma ${\displaystyle n=(2p+1)(2q+1)}$, donde p y q son números naturales y ${\displaystyle q=p+k}$ para algún k natural. Entonces,

${\displaystyle n=(2p+1)(2p+2k+1)[1]=4p^{2}+4p+4kp+2k+1=(2p+1)^{2}+2\cdot (2p+1)\cdot k}$

con lo que n se encontraría en la p-ésima columna y la k-ésima fila

Al hacer variar p y k a lo largo de ${\displaystyle \mathbb {N} }$ se obtiene el conjunto de los números que son producto de dos impares que se encuentran en la tabla.

9
15	25
21	35	49
27	45	63	81
33	55	77	99	121
39	65	91	117	143	169
45	75	105	135	165	195	225
51	85	119	153	187	221	255	289
57	95	133	171	209	247	285	323	361
63	105	147	189	231	273	315	357	399	441
69	115	161	207	253	299	345	391	437	483	529
...	...	...	...	...	...	...	...	...	...	...	...

Sundaram era un matemático de la India. La criba que publicó en 1934 era algo diferente al modelo aquí presentado.

Una forma cuadrática asociada

La forma cuadrática ${\displaystyle p=\left(\,k+2j+1\right)^{2}-k^{2},con\,k\in \mathbb {N} \;y\;j\in \mathbb {N} ,}$ tiene por lo menos un par (k, j) de soluciones en números naturales, para cada valor de p compuesto. Cuando p es compuesto, k puede tomar cualquier valor natural y también puede ser nulo, si el número p es un cuadrado. El valor de j siempre es distinto de cero para p compuesto. Una solución (k, j) única, con j = 0, indica que p es un número primo en ${\displaystyle \mathbb {Z} }$.

Si desarrollamos el cuadrado, el resultado es análogo a la expresión [1]: ${\displaystyle p=\left(\,k+2j+1\right)^{2}-k^{2}=(2j+1)(2k+2j+1)}$.

Las soluciones de la forma cuadrática no están acotadas todavía, por lo que esta fórmula no puede utilizarse para determinar la primalidad de un número. La criba constituye un método casi de "fuerza bruta", también impracticable para números muy grandes.

Una relación de equivalencia

Si reordenamos la criba de Sundaram y la escribimos de una manera diferente, podemos dividir a los números compuestos en clases disjuntas:

El criterio a seguir consiste en agrupar los números que tienen un mismo divisor mínimo. Comenzamos por el 9, que es un cuadrado y seguimos con todos los múltiplos de 3 que no contengan factores pares. Seguimos con 25, que también es un cuadrado, y agrupamos todos los múltiplos de 5 que no tengan factores menores que 5. Y así sucesivamente (Obsérvese que 81 está, ahora, en la clase que comenzamos con 9). Todas estas clases de números naturales compuestos quedan agrupadas en subconjuntos disjuntos dos a dos.

Ahora ampliamos algo más el contenido de la criba. Colocamos al mínimo divisor como precedente de cada cuadrado y lo aceptamos como representante de la clase (es el divisor mínimo común de la clase). Además, agregamos el 2 y todos los pares como una clase adicional y tenemos, entonces, a todos los números naturales -excepto el 1- divididos en clases disjuntas. Esto indica que se ha realizado un cociente de ${\displaystyle \mathbb {N} -\{1\}}$ por una relación de equivalencia. Los representantes de esas clases son los números primos.

Merkle-Hellman (MH) fue uno de los primeros criptosistemas de llave pública y fue inventado por Ralph Merkle y Martin Hellman en 1978.¹ Aunque sus ideas eran elegantes, y mucho más simples que RSA, no tuvo el mismo éxito que este último, debido a que MH ya fue roto,² y además no ofrece funcionalidades para firmar.

Descripción

Merkle-Hellman es un criptosistema asimétrico, esto significa que para la comunicación, se necesitan dos llaves: una llave pública y una privada. Otra diferencia con RSA, es que sirve sólo para cifrado, es decir, la llave pública es usada sólo para cifrar (no para verificar firma) y la llave privada es usada sólo para descifrar (no para firmar). De este modo, no se puede usar para tareas de autentificación por firma electrónica.

El algoritmo de Merkle-Hellman está basado en el problema de la mochila de decisión (un caso especial del problema de la mochila de optimización): dados una secuencia de números y un número, determinar si existe un subconjunto de la secuencia cuya suma dé dicho número. En general, es sabido que este problema es de clase NP-completo. Sin embargo, si la secuencia de números es supercreciente -- esto es, si cada elemento de la secuencia es mayor que la suma de todos los anteriores -- el problema es "fácil", y es posible resolverlo en tiempo polinómico con un simple algoritmo voraz.

Generación de las claves

En Merkle-Hellman, las claves están compuestas por secuencias. La clave pública es una secuencia "difícil", y la clave privada es una "fácil", o secuencia de valores supercrecientes, junto con dos números adicionales, un multiplicador y un módulo, los cuales son usados para convertir la secuencia supercreciente en una secuencia difícil. Estos mismos números son usados para transformar la suma de la subsecuencia de la secuencia "difícil" en la suma de la subsecuencia de la secuencia "fácil", la cual se puede solucionar en tiempo polinómico.

Cifrado

Para cifrar un mensaje, el cual debe ser una secuencia de bits de la misma longitud de la secuencia difícil, se eligen los elementos de la secuencia difícil que correspondan a bits en 1 del mensaje (mientras que los elementos correspondientes a bits en 0 son descartados). Luego se suman los elementos así elegidos, y el resultado de esto es el texto cifrado.

En caso que el mensaje no sea de la misma longitud de la llave, se subdivide en secuencias que tengan esta longitud y se aplica el mismo procedimiento.

Descifrado

El descifrado es posible, porque el multiplicador y el módulo usados para transformar la secuencia supercreciente (la llave privada) y por tanto "fácil" en la secuencia general (la llave pública) y por tanto difícil, también pueden ser usados para transformar el texto cifrado (representado por un número) en la suma de los elementos que conforman la subsecuencia supercreciente (una subsecuencia de una secuencia supercreciente, también es supercreciente). Luego, usando un algoritmo voraz, el problema "fácil" de la mochila puede ser resuelto usando O(n) operaciones, con lo cual se logra descifrar el mensaje.

Método Matemático

Generación de las claves

Para cifrar un mensaje de n-bits, elegir una secuencia supercreciente :

${\displaystyle w=(w_{1},w_{2},...,w_{n}){\mbox{ tal que }}w_{i+1}>\sum _{j=1}^{i}w_{j}}$

de n números naturales (distintos de cero). Elegir un número q (preferiblemente al azar), tal que

${\displaystyle q>\sum _{i=1}^{n}w_{i}}$

y otro número entero, r tal que mcd(r,q) = 1.

q es escogido de esta forma para asegurar la unicidad del texto cifrado. Si fuera menor, podría haber varios textos claros que resultarían en el mismo texto cifrado. r debe ser coprimo con q puesto que de otra forma podría no tener inverso en ${\displaystyle {\pmod {q}}}$. La existencia del inverso de r es necesaria para que se pueda realizar el descifrado.

A continuación, se calcula la secuencia:

${\displaystyle \mathbf {\beta } =(\beta _{1},\beta _{2},...,\beta _{n}){\mbox{ tal que }}\beta _{i}=rw_{i}{\pmod {q}}}$

La clave pública es ${\displaystyle \beta }$ , mientras que la llave privada es ${\displaystyle (w,q,r)}$.

Cifrado

Para cifrar un mensaje de n-bits

${\displaystyle \mathbf {\alpha } =(\alpha _{1},\alpha _{2},...,\alpha _{n})}$

donde ${\displaystyle \mathbf {\alpha } _{i}}$ es el i-ésimo bit del mensaje y ${\displaystyle \mathbf {\alpha } _{i}\in \{0,1\}}$, calcular

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}}$.

El criptograma o texto cifrado es c.

Descifrado

Para descifrar el criptograma c, el receptor tiene que encontrar los bits del mensaje ${\displaystyle \alpha _{i}}$ tales que satisfacen

${\displaystyle c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}}$.

Este problema sería difícil de resolver si los ${\displaystyle \beta _{i}}$ fueran valores aleatorios, debido a que el receptor tendría que resolver una instancia del problema de la mochila, el cual se sabe que es NP-hard. Sin embargo, los valores ${\displaystyle \beta _{i}}$ fueron elegidos de forma que el descifrado sea fácil si la clave privada ${\displaystyle (w,q,r)}$ es conocida.

Para el descifrado se debe encontrar un entero s tal que es el inverso de r módulo q. Esto es, s satisface la ecuación :

${\displaystyle rs\equiv 1{\pmod {q}}}$

o equivalentemente, existe un entero k tal que sr = kq + 1. Dado que r fue escogido como un coprimo de q es posible encontrar s y k usando el Algoritmo de Euclides extendido. Luego el receptor del criptograma c calcula:

${\displaystyle c'\equiv cs{\pmod {q}}.}$

Por tanto

${\displaystyle c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q}}.}$

Ya que ${\displaystyle rs\equiv 1{\pmod {q}}}$ y ${\displaystyle \mathbf {\beta } _{i}\equiv rw_{i}{\pmod {q}}}$ entonces

${\displaystyle \beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q}}.}$

Con esto

${\displaystyle c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q}}.}$

La suma de todos los valores ${\displaystyle w_{i}}$ es menor que q y por ende ${\displaystyle \sum _{i=1}^{n}\alpha _{i}w_{i}\,{\bmod {\,}}q}$ también está en el intervalo ${\displaystyle \mathbf {[} 0,q-1]}$.

De este modo el receptor tiene que resolver el siguiente problema de la mochila.

${\displaystyle c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.}$

Este problema es fácil debido a que la secuencia w es supercreciente.

El algoritmo avaro para resolver esto consiste en lo siguiente:

   Tomar el elemento más grande en ${\displaystyle w}$, digamos ${\displaystyle w_{k}}$. 
   Si ${\displaystyle w_{k}>c'}$, luego ${\displaystyle \alpha _{k}=0}$,
   Sino ${\displaystyle \alpha _{k}=1}$
   Disminuímos  c'  en ${\displaystyle w_{k}\alpha _{k}}$ 
   y repetimos estos pasos hasta que se haya alcanzado c'.

El pseudo código para este algoritmo sería:

   While ${\displaystyle (c'>0)}${
       ${\displaystyle w_{k}={\mbox{ extract-max }}(w)}$
       If ${\displaystyle (w_{k}>c')}$
          then ${\displaystyle \alpha _{k}=0}$,
       Else ${\displaystyle \alpha _{k}=1}$
          ${\displaystyle c'=c'-w_{k}*\alpha _{k}}$
   }

Este algoritmo no se puede usar para firmar puesto que el criptograma es un número (c) y no un texto, de este modo no se puede descifrar un mensaje claro y por ende no se puede firmar.