Pseudoaleatoriedad

Summary

Una secuencia de números con pseudoaleatoriedad 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 seres humanos (como los 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 los generadores de números aleatorios por hardware han desafiado esta aseveración.

Antecedentes

editar

La generación de números aleatorios tiene muchos usos, como el muestreo aleatorio, los métodos de Montecarlo, los juegos de mesa o los juegos de azar. 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 a partir del mismo punto de partida. Algunas excepciones notables son la desintegración radiactiva y la medición en la mecánica 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 denominado generador de números pseudoaleatorios, al que primero se le debe proporcionar un número denominado semilla aleatoria. Dado que la misma semilla producirá la misma secuencia cada vez, es importante que la semilla se elija bien y se mantenga oculta, especialmente en aplicaciones de seguridad, donde la imprevisibilidad del patrón es una característica fundamental.[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 recogido de una radio sintonizada entre emisoras o la mezcla de tiempos de pulsaciones.[1][4]​ El tiempo necesario para obtener estos números lleva a un compromiso: utilizar algunas de estas lecturas físicas como semilla para un generador de números pseudoaleatorios.

Historia

editar

Antes de la informática moderna, los investigadores que necesitaban números aleatorios los generaban por diversos medios como dados, cartas, ruletas,[5]​ etc. o utilizaban tablas de números aleatorios ya 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 L.H.C. 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 Un millón de dígitos aleatorios con 100.000 desviaciones normales.

En complejidad computacional

editar

En Ciencia computacional teórica, una distribución es «pseudoaleatoria» frente a una clase de adversarios si ningún adversario de la clase puede distinguirla de la distribución uniforme con una ventaja significativa. [6]​ Este concepto 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 frente a F si para cada f en F, la distancia estadística entre las distribuciones   y  , donde   se muestrea de D e   se muestrea de la distribución uniforme sobre 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]

Véase también

editar

Referencias

editar
  1. a b George Johnson (12 de junio de 2001). «Los conocedores del caos ofrecen un producto valioso: La aleatoriedad». The New York Times. 
  2. S. P. Vadhan (2012). Pseudorandomness. «pseudorandomness, la teoría de la generación eficiente de objetos que «parecen aleatorios» a pesar de estar construidos con poco o ningún aleatorismo». 
  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 (January 1998). «Javatalk: Horseshoes, hand grenades and random numbers». Sun Server: 16-17. 
  5. a b «A Million Random Digits». RAND Corporation. January 2001. Consultado el 30 de marzo de 2017. 
  6. Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press. 2008.
  7. «Pseudorandomness». 

Bibliografía

editar
  • Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Addison-Wesley Professional, ISBN 0-201-89684-2
  • Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0.  See especially Chapter 8: Pseudorandom generators, pp. 284–348, and Appendix C.2: Pseudorandomness, pp. 490–493.
  • Vadhan, S. P. (2012). «Pseudorandomness». Foundations and Trends in Theoretical Computer Science 7 (1–3): 1-336. doi:10.1561/0400000010. 

Enlaces externos

editar
  • HotBits: Genuine random numbers, generated by radioactive decay
  • Using and Creating Cryptographic-Quality Random Numbers
  •   Datos: Q2115856
  •   Multimedia: Pseudorandomness / Q2115856