Pseudoaleatoriedad

Una secuencia pseudoaleatoria de números es aquella que parece ser estadísticamente aleatoria , a pesar de haber sido producida por un proceso completamente determinista y repetible. ^{[ 1 ]} Los generadores de números pseudoaleatorios se utilizan a menudo en la programación informática, ya que las fuentes tradicionales de aleatoriedad disponibles para los humanos (como lanzar dados) se basan en procesos físicos que no están fácilmente disponibles para los programas informáticos, aunque los avances en la tecnología de generación de números aleatorios por hardware han puesto en entredicho esta situación.

La generación de números aleatorios tiene muchos usos, como el muestreo aleatorio , los métodos de Monte Carlo , los juegos de mesa o las apuestas . Sin embargo, en física , la mayoría de los procesos, como la aceleración gravitatoria, son deterministas, lo que significa que siempre producen el mismo resultado desde el mismo punto de partida. Algunas excepciones notables son la desintegración radiactiva y la medición cuántica , que se modelan como procesos verdaderamente aleatorios en la física subyacente. Dado que estos procesos no son fuentes prácticas de números aleatorios, se utilizan números pseudoaleatorios, que idealmente poseen la imprevisibilidad de una secuencia verdaderamente aleatoria, a pesar de ser generados por un proceso determinista. ^{[ 2 ]}

En muchas aplicaciones, el proceso determinista es un algoritmo informático llamado generador de números pseudoaleatorios , al que primero se le debe proporcionar un número llamado semilla aleatoria . Dado que la misma semilla producirá la misma secuencia cada vez, es importante que la semilla se elija cuidadosamente y se mantenga oculta, especialmente en aplicaciones de seguridad , donde la imprevisibilidad del patrón es una característica crítica. ^{[ 3 ]}

En algunos casos donde es importante que la secuencia sea demostrablemente impredecible, se han utilizado fuentes físicas de números aleatorios, como la desintegración radiactiva, el ruido electromagnético atmosférico captado de una radio sintonizada entre estaciones o la mezcla de tiempos de pulsaciones de teclas . ^{[ 1 ] [ 4 ]} El tiempo necesario para obtener estos números lleva a una solución de compromiso: utilizar algunas de estas lecturas físicas como semilla para un generador de números pseudoaleatorios.

Antes de la informática moderna, los investigadores que necesitaban números aleatorios los generaban mediante diversos medios ( dados , cartas , ruedas de ruleta , ^{[ 5 ]} etc.) o utilizaban tablas de números aleatorios existentes.

El primer intento de proporcionar a los investigadores un suministro inmediato de dígitos aleatorios fue en 1927, cuando Cambridge University Press publicó una tabla de 41.600 dígitos desarrollada por LHC Tippett . En 1947, la RAND Corporation generó números mediante la simulación electrónica de una ruleta; ^{[ 5 ]} los resultados se publicaron finalmente en 1955 como A Million Random Digits with 100.000 Normal Deviates .

En la ciencia de la computación teórica , una distribución es pseudoaleatoria frente a una clase de adversarios si ningún adversario de esa clase puede distinguirla de la distribución uniforme con una ventaja significativa. ^{[ 6 ]} Esta noción de pseudoaleatoriedad se estudia en la teoría de la complejidad computacional y tiene aplicaciones en criptografía .

Formalmente, sean S y T conjuntos finitos y sea F = { f : S → T } una clase de funciones. Una distribución D sobre S es ε- pseudoaleatoria con respecto a F si para cada f en F , la distancia estadística entre las distribuciones${\displaystyle f(X)}$y${\displaystyle f(Y)}$, dónde${\displaystyle X}$se muestrea de D y${\displaystyle Y}$se muestrea de la distribución uniforme en S , es como máximo ε.

En aplicaciones típicas, la clase F describe un modelo de computación con recursos limitados y se busca diseñar distribuciones D con ciertas propiedades que sean pseudoaleatorias con respecto a F. La distribución D se especifica a menudo como la salida de un generador pseudoaleatorio . ^{[ 7 ]}

• Asortatividad : tendencia a que los nodos similares se conecten. 
• Generador de números pseudoaleatorios criptográficamente seguro : tipo de funciones diseñadas para ser irresolubles mediante algoritmos de búsqueda de raíces. 
• Lista de generadores de números aleatorios
• Secuencia binaria pseudoaleatoria : flujo de bits aparentemente aleatorio y difícil de predecir, creado por un algoritmo determinista. 
• Conjunto pseudoaleatorio
• Generador de números pseudoaleatorios : algoritmo que genera una aproximación de una secuencia de números aleatorios. 
• Secuencia de baja discrepancia : tipo de secuencia matemática. 
• Generación de números aleatorios : creación de una secuencia de números que no se pueden predecir. 
• Ruido pseudoaleatorio : señal pseudoaleatoria con características similares al ruido. 
• Número transfinito : número que es mayor que todos los números finitos. 

• Donald E. Knuth (1997) El arte de la programación informática , Volumen 2: Algoritmos seminuméricos (3.ª edición) . Addison-Wesley Professional, ISBN 0-201-89684-2
• Goldreich, Oded (2008). Complejidad computacional: una perspectiva conceptual . Cambridge University Press. ISBN 978-0-521-88473-0.Véase especialmente el Capítulo 8: Generadores pseudoaleatorios, págs. 284–348, y el Apéndice C.2: Pseudorandomidad, págs. 490–493.
• Vadhan, SP (2012). "Pseudorandomness". Foundations and Trends in Theoretical Computer Science . 7 ( 1– 3): 1– 336. doi : 10.1561/0400000010 .

• HotBits: Números aleatorios genuinos, generados por desintegración radiactiva.
• Uso y creación de números aleatorios con calidad criptográfica
• En el RFC 4086 se analiza en detalle el uso de secuencias de números pseudoaleatorios en criptografía. ^{[ 8 ]}