C¨®mo generar n¨²meros al azar con ordenadores que no son tan aleatorios

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.

M¨¢s informaci¨®n

Cuando los datos descifran otros futuros posibles

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 ¨C 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 ¨Ccuriosamente, igual de probable estad¨ªsticamente que la primera secuencia¨C 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 ¨C 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 ¨Cni siquiera caro¨C 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.