Tecnología

Cómo generar números al azar con ordenadores que no son tan aleatorios | Tecnología


Muchos programas de ordenador necesitan números aleatorios para funcionar. Desde videojuegos a sistemas de seguridad y simuladores. Los valores aleatorios se utilizan para el análisis estadístico, el arte o simplemente cuando hay que elegir algo al azar, como en los sorteos. Sin embargo, la aleatoriedad perfecta que atribuimos a objetos como monedas, dados o las bolas de un bombo es algo difícil de alcanzar cuando se trata de generarla con ordenadores.

La precisión de los ordenadores y su carácter determinista son la clave del asunto. Un ordenador o un programa siempre dará los mismos resultados de salida ante los mismos datos de entrada. Al menos mientras no se introduzca entremedias algún tipo de factor aleatorio.

Pero es precisamente en los generadores de números aleatorios donde está el problema. En realidad no son “tan aleatorios”. Sirva como ejemplo el famoso botón de “reproducción aleatoria” de los iPod y otras aplicaciones musicales, que crea listas de canciones al azar. Incluso Apple tuvo que afinar la forma en que funcionaba porque había gente que se quejaba de que era “poco aleatoria”.

Para comprobar las secuencias y los generadores pseudo-aleatorios se utilizan diversas pruebas estadísticas. El problema es que matemáticamente no existe la prueba perfecta

Cómo funciona la simulación del azar

Un generador de números aleatorios está limitado por su propia definición. Suelen funcionar así: se toma un valor inicial (llamado semilla), se realizan con él ciertas enrevesadas operaciones matemáticas y de ahí surge el resultado. Si el generador está bien diseñado cada vez que se utilice ofrecerá un nuevo número y la secuencia será aleatoria. O al menos, lo más aleatoria posible. El problema es que cada vez que se comience por la misma semilla la secuencia será idéntica. Como decía el matemático y pionero de la informática Donald Knuth: “los números al azar no deberían generarse mediante un método elegido al azar”.

Podría pensarse que los propios números ya generados pueden utilizarse como semilla. De este modo el proceso tiende a volverse más desordenado e impredecible cada vez. ¿O no? Esto tiene un límite: la precisión de cálculo de esos valores. Supongamos que la semilla puede ser cualquier número entre 0 y 65535. Todo funcionará bien hasta que al cabo de 65536 valores alguno haya de repetirse obligatoriamente. Si un generador está bien diseñado e implementado pasará por el mayor número de valores posibles antes de entrar en el ciclo (y esos posibles valores serán muchos). Pero al final, tarde o temprano, acabará repitiéndose.

Una solución de compromiso es utilizar factores externos, por ejemplo los movimientos del ratón del ordenador o las milésimas de segundo que marca el reloj interno cuando se llama a la función aleatoria – factores poco predecibles. Pero no suelen resolver el problema; por ejemplo el reloj del ordenador puede coincidir en sus ciclos con los de los cálculos de la función aleatoria, y los movimientos del ratón están limitados por su precisión. Debido a todo esto estos algoritmos tuvieron humildemente que cambiar de nombre y técnicamente se denominan generadores de números pseudo-aleatorios. No son aleatorios, pero “casi”.

Pruebas de aleatoriedad

Para comprobar las secuencias y los generadores pseudo-aleatorios se utilizan diversas pruebas estadísticas. El problema es que matemáticamente no existe la prueba perfecta. Una muy sencilla sería comprobar si al aplicarlos a la secuencia de lanzamientos de un dado simulado aparecen más o menos las mismas veces los valores 1, 2, 3… etcétera. Otras pruebas similares exigen comparar las secuencias de dos o tres valores consecutivos (11, 12, 13…) y comparar sus frecuencias.

Curiosamente hay secuencias que pasan todas estas pruebas sin ser aleatorias. Quizá la más famosa de ellas es el número de Champernowne, que comienza así: 0,1234567891011121314… Es simplemente una larga ristra con todos los números naturales. Todos sus decimales, ya sean tomados de uno en uno, de dos en dos o de tres en tres, aparecen más o menos con la misma frecuencia.

Si bien los generadores pseudoaleatorios superan las pruebas más sencillas muchos de ellos fracasan ante la aleatoriedad necesaria para las aplicaciones de análisis numérico o criptografía. Teniendo en cuenta que los resultados de innumerables estudios científicos dependen de lo primero y la seguridad del dinero que guardamos en los bancos y enviamos por internet de lo segundo, más vale que existan métodos mejores.

Una forma que encontraron los matemáticos de comprobar con mayor precisión la aleatoriedad de una secuencia es intentando describirla mediante un pequeño programa que pudiera generarla. Una secuencia como “1111…111” repetida mil veces no parece muy aleatoria, porque puede reducirse a la frase “escribir 1 mil veces”, algo mucho más corto. En cambio, algo como “10010111100…” donde los 0 y 1 se obtienen lanzando una moneda –curiosamente, igual de probable estadísticamente que la primera secuencia– no podría describirse de forma más breve. Esto se conoce como complejidad de Kolmogorov (o entropía algorítmica) y es clave para cuantificar la aleatoriedad.

Irónicamente esta complejidad de Kolmogorov no puede calcularse, aunque sí que se pueden conocer sus límites, por ejemplo comprimiendo la información: la que no sea aleatoria podrá comprimirse un poco (porque se podrá resumir) mientras que la verdaderamente aleatoria no podrá comprimirse (dado que no habrá repeticiones ni patrones detectables). Esto está íntimamente relacionado con la entropía o “desorden” de la secuencia en cuestión.

Los problemas de no usar correctamente la aleatoriedad pueden ser graves. Tal y como comentaba el experto Sergey Ignatchenko de ITShare.com la versión Debian del Linux fue básicamente insegura entre 2006 y 2008 porque uno de los desarrolladores hizo un cambio en el código de su generador de números aleatorios. Lo mismo sucedió en 2013 con una función del lenguaje Java que limitó su aleatoriedad, permitiendo descubrir claves de carteras de Bitcoin, por ejemplo. En la web de apuestas Planet Poker cometieron en 2000 el error de usar un generador aleatorio pobremente diseñado, que era incapaz de generar todas las mezclas posibles para las barajas, quedando solo un pequeño número que podía estudiarse estadísticamente para obtener ventaja – básicamente era como “poder ver las cartas de los oponentes”.

Física al rescate

Lejos quedan libros como Un millón de dígitos aleatorios, una tabla que la RAND Corporation publicó en 1947 para quienes necesitara números al azar de comprobada validez. Desde hace décadas, sitios como Random.org ofrecen en internet números “verdaderamente aleatorios” para todo tipo de propósitos: análisis científicos, juegos, sorteos… Dicen que su calidad es superior a la de los generadores de números pseudoaleatorios porque obtienen los números de procesos puramente físicos, en su caso del “ruido atmosférico”. Básicamente se trata de tres radios AM/FM sintonizadas entre emisoras, en la zona donde todo lo que se oye es ruido de fondo. Ese ruido es aleatorio y a partir de él se generan los números que luego se preparan para ofrecerse en diversos formatos.

Además de esta ingeniosa solución que emplea el ruido electrónico hay sistema similares basadas en otros procesos físicos que se consideran impredecibles y son normalmente subatómicos: desintegración radioactiva, ruido térmico o el ruido de disparo (shot) típico de los dispositivos electrónicos y ópticos.

Por otro lado, sitios como Random Sanity Project ofrecen comprobaciones gratuitas de la aleatoriedad de cualquier grupo de números. Algo interesante si se planea utilizar software de este tipo para algo importante o simplemente para comprobar que todo es correcto

Por otro lado, sitios como Random Sanity Project ofrecen comprobaciones gratuitas de la aleatoriedad de cualquier grupo de números. Algo interesante si se planea utilizar software de este tipo para algo importante o simplemente para comprobar que todo es correcto. También permite detectar cómo los seres humanos no somos muy buenos generando secuencias aleatorias. Basta examinar una secuencia simulada por un humano intentando imitar los lanzamientos de una moneda o un dado para darse cuenta rápidamente de cuál es la auténtica: las personas apenas superamos las pruebas más básicas debido a nuestros sesgos mentales.

La aleatoriedad de la física cuántica

El último paso en esta carrera por conseguir la aleatoriedad son los generadores aleatorios que aprovechan las propiedades de las partículas subatómicas y el mundo cuántico para generar secuencias aleatorias.

En 2010 el físico español Antonio Acín formó parte de un equipo que publicó un trabajo en Nature acerca de cómo se podía certificar la aleatoriedad de secuencias numéricas aprovechando el teorema de Bell de la mecánica cuántica. En 2012 dos profesores de la Universidad Nacional Australiana desarrollaron un generador basado en la medición del vacío, del que surgen aleatoriamente partículas virtuales produciendo ruido aleatorio. En 2016 investigadores de la Universidad Politécnica de Cataluña desarrollaron un chip capaz de generar varios gigabits aleatorios por segundo usando las propiedades cuánticas de la luz.

Hoy en día las CPU Ivy Bridge de Intel incluyen este tipo de generadores de números aleatorios basados en procesos físicos; sus velocidades generándolos están en torno a los 3 Gbps. Tampoco es demasiado complicado –ni siquiera caro– comprar tarjetas de ampliación especializadas o dispositivos USB que realizan la misma función: basta elegir el método preferido (diodos, ruido eléctrico, efecto fotoeléctrico) y la velocidad deseada, que comienza alrededor de los 100 Kbps. Su precio: a partir de 10 euros. Nunca conseguir lo más parecido al azar verdadero, algo que no es tarea fácil, fue tan barato ni tan cómodo.




Fuente: El país

Comentar

Click here to post a comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *