MATEMÁTICAS - EPÓNIMOS

filtro de Wiener es un filtro propuesto por Norbert Wiener en la década de 1940 y publicado en 1949. Su propósito es, utilizando métodos estadísticos, reducir el ruido presente en la señal de entrada de tal modo que la señal de salida del filtro se aproxime lo más posible (en el sentido cuadrático medio) a una señal deseada (sin ruido). El equivalente en tiempo discreto del trabajo de Wiener fue derivado independientemente por Kolmogorov y publicado en 1941. Por esto, la teoría es a veces referida como teoría de filtrado de Wiener-Kolmogorov.

La Firma de Lamport es un esquema de firma digital de un solo uso, inventada por Leslie Lamport en 1979.¹​ La firma se aplica sobre mensajes sin efectuar ninguna modificación previa de los mismos.

La esquema de firma de Lamport utiliza un juego de claves, compuesto por una clave privada y una clave pública. La clave privada es un conjunto de ${\displaystyle 2*n}$ elementos privados. La clave pública es otro conjunto de ${\displaystyle 2*n}$elementos, formados, generalmente, por la aplicación de una función hash a cada elemento privado. Para firmar un documento, se aplica una función hash al documento del que se obtienen ${\displaystyle n}$ bits, y se utilizan para seleccionar ${\displaystyle n}$ elementos de la clave pública.

Representación de la secuencia para firmar un documento con una firma de Lamport.

La firma de Lamport se debe utilizar una sola vez por cada juego de claves. Sin embargo, combinado el esquema de firma de Lamport con un Árbol de Merkle, un solo juego de claves podría usarse para firmar varios mensajes, lo que la convierte en un esquema de firma digital bastante eficiente.

El desarrollo potencial de la computación cuántica amenaza la seguridad de muchas formas comunes de criptografía como RSA, pero se cree que las firmas de Lamport estarían seguras si se usan, como componentes de las claves, valores de tamaño adecuado.

Descripción formal[editar]

A continuación se muestra una descripción de como funciona una firma Lamport, en notación matemática. Notar que el "mensaje" en esta descripción es un bloque de ${\displaystyle n}$ datos siendo posiblemente (pero no necesariamente) el resultado de aplicar una función hash al mensaje que realmente se quiere firmar.

Claves[editar]

Sea ${\displaystyle n}$ un entero positivo y sea ${\displaystyle f:\,Y\rightarrow Z}$ una función unidireccional.

Para ${\displaystyle 1\leq i\leq n}$ y ${\displaystyle j\in \{0,1\}}$ el firmante elige aleatoriamente ${\displaystyle y_{i,j}\in Y}$ y luego calcula ${\displaystyle z_{i,j}=f(y_{i,j})}$.

La clave privada, ${\displaystyle Y}$, consiste en ${\displaystyle 2n}$ valores ${\displaystyle y_{i,j}}$. La clave pública,${\displaystyle Z}$, consiste en otros ${\displaystyle 2n}$ valores ${\displaystyle z_{i,j}}$.

Firma de un mensaje[editar]

Sea ${\displaystyle M}$ el bloque descriptor del mensaje: ${\displaystyle M=f({mensaje})\in \{0,1\}^{n}}$

${\displaystyle M=m_{1}\ldots m_{n}}$

La firma del mensaje es:

${\displaystyle \operatorname {S} (m_{1}\ldots m_{n})=(y_{1,m_{1}},\ldots ,y_{n,m_{n}})=(s_{1},\ldots ,s_{n})}$.

Verificación de la firma[editar]

Quien necesite validar la firma debe verificar que:

${\displaystyle f(s_{i})=z_{i,m_{i}}}$ para todo  ${\displaystyle 1\leq i\leq n}$.

Se debe conservar los elementos privados que forman la firma, la clave pública y el mensaje original para futuras validaciones.

Para que Eva pueda falsificar una firma, debe poder invertir los valores de la clave pública. Y esto se asume como un problema computacionalmente inviable si se usan valores de tamaño adecuado.

Inconvenientes[editar]

El primer inconveniente es que se debe utilizar cada juego de claves una sola vez. La razón es que al firmar se hacen visibles los ${\displaystyle n}$ elementos privados que generaron los ${\displaystyle n}$ elementos públicos. Es decir, se exponen el 50% de los elementos que forman la clave privada, por lo tanto una vez que se firma un documento no se debe reutilizar el juego de clave pública y privada. Además se debe destruir el 50% remanente de elementos privados que forman la clave privada y no que fueron expuestos.

Otro inconvenientes es el de la excesiva longitud de las claves y la firma.

La fórmula de Bailey-Borwein-Plouffe (o fórmula BBP) permite calcular el enésimo dígito de π en base 2 (o 16) sin necesidad de hallar los precedentes, de una manera rápida y utilizando muy poco espacio de memoria en la computadora. Simon Plouffe junto con David Bailey y Peter Borwein hallaron esta fórmula el 19 de septiembre de 1995 usando un programa informático llamado PSLQ que busca relaciones entre números enteros.

La fórmula BBP[editar]

${\displaystyle \pi =\sum _{k=0}^{\infty }{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)}$

La demostración de esta fórmula se encuentra más abajo.

Uso de la fórmula para calcular los decimales del número π[editar]

A continuación se muestra el cálculo del enésimo dígito hexadecimal de π.

Primero se debe observar que el dígito ubicado en la posición N+1 de π en base 16 es el mismo que el primer dígito hexadecimal de 16^Nπ. En efecto, como en la base 10, multiplicar un número en base 16 por 16 equivale a desplazar la coma decimal un lugar hacia la derecha. De esta manera, multiplicando por 16^N, la coma se desplaza N lugares hacia la derecha. El problema original se reduce al cálculo del primer dígito de 16^Nπ. Usando la fórmula BBP:

${\displaystyle 16^{N}\pi =\sum _{k=0}^{\infty }16^{N-k}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)}$

El cálculo de los primeros dígitos hexadecimales a la derecha de la coma de este número no es sencillo por dos razones: el número es muy grande y la suma es infinita.

Supongamos que ${\displaystyle S_{N}(a)=\sum _{k=0}^{\infty }{\frac {16^{N-k}}{8k+a}}}$. El cálculo de los primeros dígitos hexadecimales de S_N(a) permitirá obtener los de 16^Nπ, a través de la relación:

${\displaystyle 16^{N}\pi =4\ S_{N}(1)-2S_{N}(4)-S_{N}(5)-S_{N}(6)}$

Descomponiendo la suma S_N(a) en dos:

${\displaystyle S_{N}(a)=\sum _{k=0}^{\infty }{\frac {16^{N-k}}{8k+a}}=\sum _{k=0}^{N-1}{\frac {16^{N-k}}{8k+a}}+\sum _{k=N}^{\infty }{\frac {16^{N-k}}{8k+a}}=A_{N}(a)+B_{N}(a)}$

se pueden calcular A_N(a) y B_N(a) en forma independiente.

Cálculo de B_N(a)[editar]

${\displaystyle B_{N}(a)=\sum _{k=N}^{\infty }{\frac {16^{N-k}}{8k+a}}}$

Aunque se trata de una suma infinita, es muy fácil de calcular, porque sus términos son pequeños y decrecen rápidamente.

• En efecto, el primer término de la suma es: ${\displaystyle b_{N}={\frac {1}{8N+a}}}$. Si se busca el enésimo dígito hexadecimal de π (N = 1 000 000 000 por ejemplo), el primer término es mucho menor que 1.
• Además, cada término tiene un cero más a la derecha de la coma que el precedente, porque para k ≥ N, b_k > 16 b_k+1:

${\displaystyle {\frac {b_{k}}{b_{k+1}}}={\frac {16^{N-k}}{16^{N-(k+1)}}}{\frac {8(k+1)+a}{8k+a}}=16\left(1+{\frac {8}{8k+a}}\right)\longrightarrow 16^{+}}$.

Finalmente, la suma B_N(a) es de la forma (en el peor caso):

${\displaystyle B_{N}\ =\ \ 0,**********.\ .\ .\ .\ }$

${\displaystyle +\ 0,0*********.\ .\ .\ }$

${\displaystyle +\ 0,00********.\ .\ .\ }$

${\displaystyle +\ 0,000********.\ .\ .\ }$

Por lo tanto, para obtener B_N(a) con una precisión de P cifras detrás de la coma, es suficiente calcular los P primeros términos de la suma, agregándose algunos términos más para evitar errores que aparecen al realizar cálculos con valores aproximados.

Así, se calcula: ${\displaystyle B_{N}'(a)=\sum _{k=N}^{N+P+10}{\frac {16^{N-k}}{8k+a}}}$

Como esta suma sólo posee una pequeña cantidad de términos, el tiempo que insume esta operación es insignificante para una computadora.

Cálculo de A_N(a)[editar]

${\displaystyle A_{N}(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}}{8k+a}}}$

El problema para el cálculo de A_N(a) es que los primeros términos son muy grandes (N cifras de base 16 antes de la coma). Sin embargo, al igual que las primeras cifras detrás de la coma, no importa la parte entera, que también es grande. Por lo tanto, puede "eliminarse" usando aritmética modular.

Toda la dificultad se reduce a hallar la parte fraccionaria de ${\displaystyle {\frac {16^{N-k}}{8k+a}}}$. Para ello realizamos la división entera de 16^N-k por 8k+a:

${\displaystyle \exists q\in \mathbb {Z} ,\exists r<8k 16="" a="" annotation="" k="" q="" r="">$

Así ${\displaystyle {\frac {16^{N-k}}{8k+a}}=q+{\frac {r}{8k+a}}}$

${\displaystyle {\frac {r}{8k+a}}}$ es menor que 1, por lo tanto, es la parte fraccional de ${\displaystyle {\frac {16^{N-k}}{8k+a}}}$.

Y ${\displaystyle {\frac {r}{8k+a}}={\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}}$

Así, se calcula: ${\displaystyle A_{N}'(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}}$.

Utilizando el método de la exponenciación binaria, ${\displaystyle 16^{N-k}{\pmod {8k+a}}}$ se calcula rápidamente (con un tiempo de ejecución de O(log₂(N-k)).

Conclusión[editar]

Al fin y al cabo, para obtener los primeros dígitos de π base 16 (o 2), se deben calcular los primeros dígitos de:

${\displaystyle \pi _{N}=4\ S_{N}'(1)-2\ S_{N}'(4)-S_{N}'(5)-S_{N}'(6)}$

con ${\displaystyle S_{N}'(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}+\sum _{k=N}^{N+P+10}{\frac {16^{N-k}}{8k+a}}}$.

Complejidad de este método[editar]

Para calcular el enésimo dígito de π en base 16 (o el 4n-ésimo dígito en base 2):

Complejidad temporal[editar]

• B_n'(a) se calcula en complejidad lineal (O(1))
• A_n'(a) : utilizando el método de la exponenciación binaria, sus términos se calculan en O(log₂(n)). Así la suma de n términos, A_n'(a), se calcula en O(n*log₂(n)).

Así S_n'(a) se calcula en O(1)+O(n*log₂(n))=O(n*log₂(n)). Finalmente, π_n se calcula en 4*O(n*log₂(n))=O(n*log₂(n)).

Por lo tanto el tiempo de cálculo es proporcional a n*log₂(n), es decir, casi lineal.

Complejidad espacial[editar]

La complejidad en el uso de memoria es constante, ya que sólo se realizan sumas sucesivas de pequeños números (con una precisión de unos diez decimales es suficiente).

Fórmulas derivadas[editar]

Simon Plouffe[editar]

Fórmula original : ${\displaystyle \pi \ =\ \sum _{i=0}^{\infty }{\frac {1}{16^{i}}}\left({\frac {4}{8i+1}}-{\frac {2}{8i+4}}-{\frac {1}{8i+5}}-{\frac {1}{8i+6}}\right)}$

${\displaystyle \forall r\in \mathbb {C} \ \ \ \ \pi \ =\ \sum _{i=0}^{\infty }{\frac {1}{16^{i}}}\left({\frac {4+8r}{8i+1}}-{\frac {8r}{8i+2}}-{\frac {4r}{8i+3}}-{\frac {2+8i}{8i+4}}-{\frac {1+2r}{8i+5}}-{\frac {1+2r}{8i+6}}+{\frac {r}{8i+7}}\right)}$

${\displaystyle \pi {\sqrt {2}}\ =\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{8^{i}}}\left({\frac {4}{6i+1}}+{\frac {1}{6i+2}}+{\frac {1}{6i+3}}\right)}$

${\displaystyle \pi ^{2}\ =\ \sum _{i=0}^{\infty }{\frac {1}{16^{i}}}\left({\frac {16}{(8i+1)^{2}}}-{\frac {16}{(8i+2)^{2}}}-{\frac {8}{(8i+3)^{2}}}-{\frac {16}{(8i+4)^{2}}}-{\frac {4}{(8i+5)^{2}}}-{\frac {4}{(8i+6)^{2}}}-{\frac {2}{(8i+7))^{2}}}\right)}$

${\displaystyle \pi ^{2}\ =\ {\frac {9}{8}}\ \sum _{i=0}^{\infty }{\frac {1}{64^{i}}}\left({\frac {16}{(6i+1)^{2}}}-{\frac {24}{(6i+2)^{2}}}-{\frac {8}{(6i+3)^{2}}}-{\frac {6}{(6i+4)^{2}}}-{\frac {1}{(6i+5)^{2}}}\right)}$

${\displaystyle \pi ^{2}\ =\ {\frac {2}{27}}\ \sum _{i=0}^{\infty }{\frac {1}{729^{i}}}\left({\frac {243}{(12i+1)^{2}}}-{\frac {405}{(12i+2)^{2}}}-{\frac {81}{(12i+4)^{2}}}-{\frac {27}{(12i+5)^{2}}}-{\frac {72}{(12i+6)^{2}}}-{\frac {9}{(12i+7)^{2}}}-{\frac {9}{(12i+8)^{2}}}-{\frac {5}{(12i+10)^{2}}}+{\frac {1}{(12i+11)^{2}}}\right)}$

La última fórmula permite hallar dígitos aislados de ${\displaystyle \pi ^{2}}$ en base 3 ó 9.

Viktor Adamchick y Stan Wagon (1997)[editar]

${\displaystyle \pi \ =\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{4^{i}}}\left({\frac {2}{4i+1}}+{\frac {2}{4i+2}}+{\frac {1}{4i+3}}\right)}$

Fabrice Bellard[editar]

${\displaystyle \pi \ =\ {\frac {1}{64}}\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{2^{10i}}}\left(-{\frac {32}{4i+1}}-{\frac {1}{4i+3}}+{\frac {256}{10i+1}}-{\frac {64}{10i+3}}-{\frac {4}{10i+5}}-{\frac {4}{10i+7}}+{\frac {1}{10i+9}}\right)}$

Los récords[editar]

Para poder comparar, hasta el año 2008 se habían obtenido los primeros 1,241 billones de decimales de π (aproximadamente 4,123 billones de bits).

• 7 de octubre de 1996 (Fabrice Bellard): dígito número 400 mil millones en base 2
• septiembre de 1997 (Fabrice Bellard) : billonésimo dígito en base 2
• febrero de 1999 (Colin Percival) : dígito número 40 billones en base 2
• 2001: dígito número 4000 billones en base 2
• 2011: dígito número 10 billones en base 10

Cálculo del enésimo decimal[editar]

Actualmente, no existe ninguna fórmula eficaz para hallar el enésimo decimal de π en base 10. Simon Plouffe ha desarrollado en diciembre de 1996, a partir de una serie muy antigua que calcula π basado en los coeficientes de binomio de Newton, un método para calcular cifras aisladas base 10, pero debido a su complejidad O(n³*log₂(n)) pierde su utilidad en la práctica. Fabrice Bellard ha mejorado el algoritmo para alcanzar un nivel de complejidad en O(n²), pero no es suficiente para competir con los métodos convencionales que calculan todos los decimales.

Anexo: demostración de la fórmula BBP[editar]

Se demuestra primero el siguiente resultado general:

${\displaystyle \forall n\in \mathbb {N} :\sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+n)}}={\sqrt {2}}^{n}\sum _{k=0}^{\infty }{\frac {\left({\frac {1}{\sqrt {2}}}\right)^{8k+n}}{8k+n}}}$

${\displaystyle ={\sqrt {2}}^{n}\sum _{k=0}^{\infty }\left[{\frac {x^{8k+n}}{8k+n}}\right]_{0}^{\frac {1}{\sqrt {2}}}}$

${\displaystyle ={\sqrt {2}}^{n}\sum _{k=0}^{\infty }\left(\int _{0}^{\frac {1}{\sqrt {2}}}x^{n+8k-1}dx\right)}$

${\displaystyle ={\sqrt {2}}^{n}\int _{0}^{\frac {1}{\sqrt {2}}}\left(\sum _{k=0}^{\infty }x^{n+8k-1}\right)dx}$

${\displaystyle ={\sqrt {2}}^{n}\int _{0}^{\frac {1}{\sqrt {2}}}{\bigg (}x^{n-1}\underbrace {\sum _{k=0}^{\infty }\left(x^{8}\right)^{k}} {\bigg )}dx}$

${\displaystyle ={\sqrt {2}}^{n}\int _{0}^{\frac {1}{\sqrt {2}}}{\bigg (}x^{n-1}{\frac {1}{1-x^{8}}}{\bigg )}dx}$

por lo tanto: ${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+n)}}={\sqrt {2}}^{n}\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {x^{n-1}}{1-x^{8}}}dx}$

Aplicando este resultado a la fórmula BBP:

${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{16^{k}}}\left({\frac {4}{8k+1}}-{\frac {2}{8k+4}}-{\frac {1}{8k+5}}-{\frac {1}{8k+6}}\right)}$

${\displaystyle =4\sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+1)}}-2\sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+4)}}-\sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+5)}}-\sum _{k=0}^{\infty }{\frac {1}{16^{k}(8k+6)}}}$

${\displaystyle =4\left({\sqrt {2}}^{1}\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {x^{1-1}}{1-x^{8}}}dx\right)-2\left({\sqrt {2}}^{4}\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {x^{4-1}}{1-x^{8}}}dx\right)-\left({\sqrt {2}}^{5}\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {x^{5-1}}{1-x^{8}}}dx\right)-\left({\sqrt {2}}^{6}\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {x^{6-1}}{1-x^{8}}}dx\right)}$

${\displaystyle =\int _{0}^{\frac {1}{\sqrt {2}}}{\frac {4{\sqrt {2}}-8x^{3}-4{\sqrt {2}}x^{4}-8x^{5}}{1-x^{8}}}dx}$

Sustituyendo ${\displaystyle y={\sqrt {2}}x}$:

${\displaystyle =\int _{0}^{1}\left({\frac {4{\sqrt {2}}-{\frac {8}{{\sqrt {2}}^{3}}}y^{3}-{\frac {4{\sqrt {2}}}{{\sqrt {2}}^{4}}}y^{4}-{\frac {8}{{\sqrt {2}}^{5}}}y^{5}}{1-{\frac {1}{{\sqrt {2}}^{8}}}y^{8}}}\right){\frac {dy}{\sqrt {2}}}}$

${\displaystyle =16\int _{0}^{1}{\frac {4-2y^{3}-y^{4}-y^{5}}{16-y^{8}}}dy}$

${\displaystyle =16\int _{0}^{1}{\frac {y-1}{(y^{2}-2y+2)(y^{2}-2)}}dy}$

Descomponiendo en fracciones simples:

${\displaystyle =\int _{0}^{1}\left({\frac {8-4y}{y^{2}-2y+2}}+{\frac {4y}{y^{2}-2}}\right)dy}$

${\displaystyle =-2\int _{0}^{1}{\frac {2y-2}{y^{2}-2y+2}}dy+4\int _{0}^{1}{\frac {1}{1+(y-1)^{2}}}dy+2\int _{0}^{1}{\frac {2y}{y^{2}-2}}dy}$

${\displaystyle =-2\left[ln(y^{2}-2y+2)\right]_{0}^{1}+4\left[arctan(y-1)\right]_{0}^{1}+2\left[ln(2-y^{2})\right]_{0}^{1}}$

${\displaystyle =-2\ ln(1)+2\ ln(2)+4\ arctan(0)-4\ arctan(-1)+2\ ln(1)-2\ ln(2)}$

${\displaystyle =4\ arctan(1)}$

${\displaystyle =\ \pi }$