stringtranslate.com

Pseudoaleatoriedad

Una secuencia pseudoaleatoria de números es una 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 tirar dados) dependen de procesos físicos que no están fácilmente disponibles para los programas informáticos, aunque los avances en la tecnología de generadores de números aleatorios de hardware han desafiado esto.

Fondo

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 gravitacional, 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 tienen 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 siempre producirá la misma secuencia, es importante que la semilla esté bien elegida 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 en los que 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 recolectado de una radio sintonizada entre estaciones o tiempos mezclados de pulsaciones de teclas . [1] [4] La inversión de tiempo necesaria para obtener estos números conduce a un compromiso: utilizar algunas de estas lecturas físicas como semilla para un generador de números pseudoaleatorios.

Historia

Antes de la informática moderna, los investigadores que necesitaban números aleatorios los generaban mediante diversos medios ( dados , cartas , ruletas , [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 se produjo en 1927, cuando la 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 con el título A Million Random Digits with 100,000 Normal Deviates .

En complejidad computacional

En informática teórica , una distribución es pseudoaleatoria contra una clase de adversarios si ningún adversario de la 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 la criptografía .

Formalmente, sean S y T conjuntos finitos y sea F = { f : ST } una clase de funciones. Una distribución D sobre S es ε- pseudoaleatoria contra F si para cada f en F , la distancia estadística entre las distribuciones y , donde se toma una muestra de D y se toma una muestra 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 uno está interesado en diseñar distribuciones D con ciertas propiedades que son pseudoaleatorias contra F. La distribución D a menudo se especifica como la salida de un generador pseudoaleatorio . [7]

Véase también

Lectura adicional

Enlaces externos

Referencias

  1. ^ ab George Johnson (12 de junio de 2001). "Los conocedores del caos ofrecen un producto valioso: la aleatoriedad". The New York Times .
  2. ^ SP Vadhan (2012). Pseudoaleatoriedad . Pseudoaleatoriedad, la teoría de generar eficientemente objetos que "parecen aleatorios" a pesar de haber sido construidos utilizando poca o ninguna aleatoriedad.
  3. ^ Mark Ward (9 de agosto de 2015). "Los números aleatorios de la Web son demasiado débiles, advierten los investigadores". BBC .
  4. ^ Jonathan Knudson (enero de 1998). "Javatalk: herraduras, granadas de mano y números aleatorios". Sun Server . págs. 16-17.
  5. ^ ab "Un millón de dígitos aleatorios". RAND Corporation. Enero de 2001. Consultado el 30 de marzo de 2017 .
  6. ^ Oded Goldreich. Complejidad computacional: una perspectiva conceptual. Cambridge University Press. 2008.
  7. ^ "Pseudoaleatoriedad" (PDF) .
  8. ^ D. Eastlake, 3.º; J. Schiller; S. Crocker (junio de 2005). Requisitos de aleatoriedad para la seguridad. doi : 10.17487/RFC4086 . BCP 106. RFC 4086.{{citation}}: CS1 maint: nombres numéricos: lista de autores ( enlace ) Mejor práctica común. Obsoleto RFC 1750.