PruebaU01

TestU01 es un paquete de pruebas empíricas estadísticas implementado en ANSI C que proporciona un conjunto de utilidades para probar generadores de números aleatorios . La última versión de la biblioteca fue presentada en 2007 por Pierre L'Ecuyer y Richard Simard de la Universidad de Montreal [1] .

El paquete contiene varios tipos de PRNG , incluidos algunos propuestos en la literatura y algunos ampliamente utilizados en software . Da implementaciones generales de pruebas estadísticas clásicas para generadores de números aleatorios, así como las propuestas en la literatura y algunas originales. Estas pruebas se pueden aplicar a generadores que ya están en la biblioteca, generadores personalizados y secuencias de números aleatorios. Las pruebas especiales prueban cualquier secuencia de números aleatorios distribuidos uniformemente en o secuencias de bits. Las herramientas básicas para construir vectores de puntos generados por generadores también están presentes [1] . ${\ estilo de visualización [0,1]}$

Historia [1]

TestU01 se implementó por primera vez en 1985 en Pascal y contenía pruebas propuestas por Donald Knuth en la segunda edición del segundo volumen de El arte de la programación [2] . Cuatro años más tarde, se volvió a implementar en el lenguaje Modula-2 como un paquete con un diseño modular . Luego, junto con nuevas pruebas, se agregaron algunos de los PRNG más utilizados. Entre 1990 y 2001, el paquete se actualizó periódicamente con nuevos generadores y pruebas, y el manual del usuario se actualizó oportunamente (en francés). Los módulos que contienen herramientas para probar familias de generadores se introdujeron por primera vez en 1997. En 2002, Pierre L'Ecuyer y Richard Simard rediseñaron la biblioteca, la implementaron en C y tradujeron el manual al inglés. $F$

Criterios de Calidad PRNG

Los PRNG están diseñados principalmente para simular bien una secuencia de variables aleatorias independientes , generalmente en un intervalo real o en un conjunto binario . En el primer caso, la hipótesis 0 A dice que los números 0 , 1 , 2 , 3 ... son cantidades independientes de una distribución uniforme en el intervalo [3] . En el segundo, 0 B dice que hay una secuencia de bits aleatorios independientes, cada uno de los cuales toma el valor o con igual probabilidad [3] . $(0.1)$ $[0,1]$ $\mathrm{H}$ $tu$ $tu$ $tu$ $tu$ $(0.1)$ $\mathrm{H}$ ${\ estilo de visualización 0}$ $una$

$\mathrm{H}$ 0 A es equivalente a decir que para cualquiervector entero ( 0 , ...,) se distribuye uniformemente en uncubo bidimensional. Para los PRNG algorítmicos, la declaración es falsa, porque los vectores en ellos toman sus valores de un número finito de vectores detodas lasdimensiones que el generador es capaz de producir [3] . $t$ $tu$ $tu$ $t-1$ $t$ $(0.1)$ $t$ $\psi$ $t$ $t$

Para una secuencia de bits, la hipótesis 0 B tampoco puede llamarse formalmente verdadera en el caso en que la longitud de la secuencia exceda el número de bits de los estados del generador, porque el número de posibles secuencias producidas no puede exceder [3] . La tarea del generador es asegurarse de que las secuencias en el campo de todas las secuencias posibles en . $\mathrm{H}$ $t$ $b$ $2$ $b$ $2$ $t$

Otro criterio de calidad para PRNG se utiliza en criptología y máquinas de juego. Aquí, además de todo lo anterior, se presta especial atención a la imprevisibilidad de los números posteriores [3] .

Características [1]

TestU01 ofrece cuatro grupos de módulos para trabajar con generadores:

implementación de un generador preprogramado (módulo ); $tu$
implementación de pruebas estadísticas especiales (módulo ); $s$
implementación de baterías de pruebas estadísticas (módulo ); $b$
aplicación de ensayos sobre familias enteras de generadores (módulo ). $F$

Cuando se aplica una prueba en particular a la salida de un generador de tamaño , el valor p de la prueba suele ser razonable hasta que el tamaño de los datos alcanza cierto valor . Después de eso, el valor de p diverge hacia oa una tasa exponencial. El módulo permite al investigador explorar la relación entre una prueba específica y la estructura de un conjunto de puntos obtenidos utilizando una familia específica de generadores. Esta técnica se puede utilizar para determinar el tamaño de los datos a probar, dependiendo de la duración del período del generador, antes de que el generador comience a fallar sistemáticamente en las pruebas. $norte$ $n_ {0}$ ${\ estilo de visualización 0}$ $una$ $F$

TestU01 ofrece varias baterías de prueba como SmallCrush (que consta de 10 pruebas), Crush (96 pruebas) y BigCrush (106 pruebas). En una computadora basada en Pentium 4 con un sistema operativo Linux , para un generador simple, la duración de la batería de las pruebas SmallCrush toma varios minutos, Crush, aproximadamente una hora, BigCrush, aproximadamente una docena de horas [3] .

Otros programas para probar PRNG

Uno de los paquetes de prueba de PRNG ampliamente utilizados es DIEHARD [4] , que contiene una gran cantidad de pruebas estadísticas, pero tiene una serie de desventajas y limitaciones. En primer lugar, la secuencia de las pruebas, así como sus parámetros (como el tamaño de la muestra, etc.) son fijos, lo que tiene un efecto negativo en la velocidad de las pruebas [3] . En segundo lugar, DIEHARD requiere enteros de 32 bits escritos en binario como entrada , mientras que muchos generadores producen números menores de 32 bits [3] . En comparación con TestU01, el paquete DIEHARD es menos flexible en estos aspectos [3] .

Otro paquete de prueba público es la biblioteca SPRNG [5] , que incluye las pruebas clásicas descritas en El arte de la programación [2] . Además, el Instituto Nacional de Estándares y Tecnología ha desarrollado su propio conjunto de 15 pruebas para probar generadores utilizados en criptografía [6] .

Baterías

La batería Alphabit fue creada para probar generadores de números aleatorios de hardware . Realiza nueve pruebas consecutivas, antes de cada reescritura de los datos de entrada.

Rabbit es una batería enfocada más a probar datos binarios , pero algunas pruebas pasan con parámetros fijos, sin importar cuán grande sea la entrada. Por lo tanto, los datos de más de 64 megas conducen a un error en una de las pruebas y conducen a un desbordamiento de RAM . [7]

SmallCrush , una pequeña y rápida batería de pruebas, lee el generador como un archivo que contiene flotadores dentro de . El límite de archivos es un poco menos de 51320000 números aleatorios. El archivo se sobrescribirá al comienzo de cada prueba. Algunas pruebas requieren que el generador devuelva al menos 30 bits de solución; de lo contrario, es muy probable que el generador falle. Por lo general, se utiliza para comprobar la viabilidad de realizar pruebas en baterías más exigentes [7] . $[0,1)$

Crush - Una batería de rigurosas pruebas estadísticas. Incluye tanto las clásicas pruebas de Knuth como muchas otras. Algunas de estas pruebas asumen que el generador devuelve al menos 30 bits de solución; de lo contrario, las pruebas fallarán. Una de las pruebas requiere 31 bits de datos. La batería utiliza aproximadamente 2 35 números aleatorios [7] .

BigCrush es una batería de las pruebas estadísticas más estrictas. Al igual que con otras baterías, algunas pruebas requieren al menos 30 bits de entrada o las pruebas fallarán. También una de las pruebas requiere 31 bits de datos. La batería utiliza casi 238 números aleatorios. Cuando BigCrush apareció por primera vez, incluso los PRNG que se consideraban buenos tuvieron dificultades para superarlo [7] .

Pruebas de batería SmallCrush

Estos son algunos ejemplos de pruebas de batería de SmallCrush [1] .

Espasmos de cumpleaños	Una prueba basada en la paradoja del cumpleaños . Se eligen puntos aleatorios en un intervalo grande, cuyas distancias deben tener una distribución asintótica de Poisson .
brecha	Prueba utilizada para determinar el intervalo entre repeticiones de un mismo dígito.
Coleccionista de cupones	Sea una sucesión de longitud n y dimensión m. Estudiamos secuencias de cierta longitud que contienen un número de m bits. $\xi _{1},\xi _{2},\puntos,\xi _{n}$
MatrixRank	La prueba selecciona una cierta cantidad de bits de una cierta cantidad de números aleatorios para formar una matriz sobre {0,1}. Luego se determina el rango de la matriz.

Literatura

Pierre L'Ecuyer, Richard Simard. TestU01: Biblioteca AC para pruebas empíricas de generadores de números aleatorios. — D'epartement d'Informatique et de Recherche Op'erationnelleUniversit'e de Montr'eal: ACM Transactions on Mathematical Software, 2007. — 40 p.
Knuth DE El arte de la programación informática volumen 2, - ISBN 0-201-89684-2 .

Enlaces

El sitio TestU01. . (indefinido)
PruebaU01. Una biblioteca de software en ANSI C para pruebas empíricas de generadores de números aleatorios. . (indefinido)

Notas

↑ 1 2 3 4 5 Pierre L'Ecuyer, Richard Simard. TestU01: Biblioteca AC para pruebas empíricas de generadores de números aleatorios // ACM Trans. Matemáticas. Softw .. - Agosto 2007. - T. 33 , no. 4 . — S. 22:1–22:40 . — ISSN 0098-3500 . doi : 10.1145 / 1268776.1268777 .
↑ 12 DE Knuth. El arte de la programación informática, Volumen 2: Algoritmos seminuméricos . - Addison-Wesley, 1981. - 142 p. Archivado el 4 de septiembre de 2008 en Wayback Machine .
↑ 1 2 3 4 5 6 7 8 9 Pierre L'Ecuyer y Richard Simard. Una biblioteca de software en ANSI C para pruebas empíricas de generadores de números aleatorios . - 2013. - Pág. 219. Copia de archivo fechada el 9 de diciembre de 2014 en la Wayback Machine .
↑ Marsaglia . ] DIEHARD: una batería de pruebas de aleatoriedad (enlace descendente) . Departamento de Estadística (1996). Archivado desde el original el 20 de enero de 2016. (indefinido)
↑ M. Mascagni y A. Srinivasan. Algoritmo 806: SPRNG: una biblioteca escalable para la generación de números pseudoaleatorios // Transacciones ACM en software matemático. - 2000. - 1 de diciembre ( vol. 26 , núm. 4 ). — S. 436–461 .
↑ CSRC - NIST SP 800-22: Documentación y software . csrc.nist.gov. Consultado el 24 de septiembre de 2017. Archivado desde el original el 25 de septiembre de 2017. (indefinido)
↑ 1 2 3 4 Resultados de TestU01 - BitBabbler . bitbubbler.org Consultado el 26 de septiembre de 2017. Archivado desde el original el 6 de octubre de 2017.