Generador congruencial inverso

Los generadores congruenciales inversos son un tipo de generador de números pseudoaleatorios congruenciales no lineales que utilizan el inverso multiplicativo modular (si existe) para generar el siguiente número en una secuencia. La fórmula estándar para un generador congruencial inverso, módulo algún primo q es:

${\displaystyle x_{0}={\text{seed}},}$

${\displaystyle x_{i+1}={\begin{cases}(ax_{i}^{-1}+c){\bmod {q}}&{\text{if }}x_{i}\neq 0,\\c&{\text{if }}x_{i}=0.\end{cases}}}$

Un generador de este tipo se denota simbólicamente como ICG( q , a , c , seed ) y se dice que es un ICG con parámetros q , a , c y seed seed .

Período

La secuencia debe tener después un número finito de pasos, y dado que el siguiente elemento depende sólo de su predecesor directo, también etc. El período máximo posible para el módulo q es q mismo, es decir, la secuencia incluye cada valor de 0 a q − 1 antes de repetirse. ${\displaystyle (x_{n})_{n\geq 0}}$ ${\displaystyle x_{i}=x_{j}}$ ${\displaystyle x_{i+1}=x_{j+1}}$

Una condición suficiente para que la secuencia tenga el máximo periodo posible es elegir a y c de manera que el polinomio (anillo polinomial sobre ) sea primitivo . Esta no es una condición necesaria; hay opciones de q , a y c para las cuales no es primitivo, pero la secuencia tiene, no obstante, un periodo de q . Cualquier polinomio, primitivo o no, que conduce a una secuencia de periodo máximo se denomina polinomio de periodo máximo inverso (IMP). Chou describe un algoritmo para elegir los parámetros a y c para obtener dichos polinomios. ^[1] ${\displaystyle f(x)=x^{2}-cx-a\in \mathbb {F} _{q}[x]}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle f(x)}$

Eichenauer-Herrmann, Lehn, Grothe y Niederreiter han demostrado que los generadores congruenciales inversos tienen buenas propiedades de uniformidad, en particular con respecto a la estructura reticular y las correlaciones seriales.

Ejemplo

ICG(5, 2, 3, 1) da la secuencia 1, 0, 3, 2, 4, 1, 0, 3, 2, 4, 1, 0, ...

En este ejemplo, es irreducible en , ya que ninguno de 0, 1, 2, 3 o 4 es una raíz. También se puede verificar que x es un elemento primitivo de y, por lo tanto, f es primitivo. ${\displaystyle f(x)=x^{2}-3x-2}$ ${\displaystyle \mathbb {F} _{5}[x]}$ ${\displaystyle \mathbb {F} _{5}[x]/(f)}$

Generador inverso compuesto

La construcción de un generador inverso compuesto (CIG) se basa en la combinación de dos o más generadores congruenciales inversos según el método que se describe a continuación.

Sean números enteros primos distintos, cada uno . Para cada índice j , 1 ≤ j ≤ r , sea una sucesión de elementos de carácter periódico con una longitud de período . En otras palabras, . ${\displaystyle p_{1},\dots ,p_{r}}$ ${\displaystyle p_{j}\geq 5}$ ${\displaystyle (x_{n})_{n\geq 0}}$ ${\displaystyle \mathbb {F} _{p_{j}}}$ ${\displaystyle p_{j}}$ ${\displaystyle \{x_{n}^{(j)}\mid 0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}}$

Para cada índice j , 1 ≤ j ≤ r, consideramos , donde es la longitud del período de la siguiente secuencia . ${\displaystyle T_{j}=T/p_{j}}$ ${\displaystyle T=p_{1}\cdots p_{r}}$ ${\displaystyle (x_{n})_{n\geq 0}}$

La secuencia de números pseudoaleatorios compuestos se define como la suma ${\displaystyle (x_{n})_{n\geq 0}}$

${\displaystyle x_{n}=\left(T_{1}x_{n}^{(1)}+T_{2}x_{n}^{(2)}+\dots +T_{r}x_{n}^{(r)}\right){\bmod {T}}}$.

El enfoque compuesto permite combinar generadores congruenciales inversos, siempre que tengan período completo, en sistemas de generación en paralelo.

Ventajas del CIG

Los CIG se aceptan a efectos prácticos por varias razones.

En primer lugar, las secuencias binarias producidas de esta manera están libres de desviaciones estadísticas indeseables. Las secuencias inversas que se han probado ampliamente con una variedad de pruebas estadísticas permanecen estables ante la variación de los parámetros. ^{[2] [3] [4]}

En segundo lugar, existe una forma constante y sencilla de elección de parámetros, basada en el algoritmo de Chou ^[1] que garantiza la máxima longitud del período.

En tercer lugar, el enfoque compuesto tiene las mismas propiedades que los generadores inversos simples, ^{[5] [6]} pero también proporciona una longitud de período significativamente mayor que la obtenida por un generador congruencial inverso simple. Parecen estar diseñados para su aplicación con plataformas de hardware multiprocesador en paralelo.

Existe un algoritmo ^[7] que permite diseñar generadores compuestos con longitud de período predecible, nivel de complejidad lineal predecible, con excelentes propiedades estadísticas de los flujos de bits producidos.

El procedimiento de diseño de esta compleja estructura comienza con la definición de un campo finito de p elementos y termina con la elección de los parámetros a y c para cada generador congruencial inverso que es el componente del generador compuesto. Esto significa que cada generador está asociado a un polinomio IMP fijo. Tal condición es suficiente para el período máximo de cada generador congruencial inverso ^[8] y, finalmente, para el período máximo del generador compuesto. La construcción de polinomios IMP es el enfoque más eficiente para encontrar parámetros para el generador congruencial inverso con una longitud de período máxima.

La discrepancia y sus límites

Las propiedades de equidistribución e independencia estadística de las secuencias generadas, que son muy importantes para su utilidad en una simulación estocástica , se pueden analizar con base en la discrepancia de s -tuplas de números pseudoaleatorios sucesivos con y respectivamente. ${\displaystyle s=1}$ ${\displaystyle s=2}$

La discrepancia calcula la distancia de un generador con respecto a uno uniforme. Una discrepancia baja significa que la secuencia generada se puede utilizar con fines criptográficos , y el primer objetivo del generador congruencial inverso es proporcionar números pseudoaleatorios.

Definición

Para N puntos arbitrarios la discrepancia se define por , donde el supremo se extiende sobre todos los subintervalos J de , es multiplicado por el número de puntos entre que caen en J y ⁠ ⁠ denota el volumen s -dimensional de J . ${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}\in [0,1)}$ ${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})={\rm {sup}}_{J}|F_{N}(J)-V(J)|}$ ${\displaystyle [0,1)^{s}}$ ${\displaystyle F_{N}(J)}$ ${\displaystyle N^{-1}}$ ${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}}$ ${\displaystyle V(J)}$

Hasta ahora teníamos secuencias de números enteros de 0 a ⁠ ⁠ ${\displaystyle T-1}$ , para tener secuencias de , se puede dividir una secuencia de números enteros por su periodo T . ${\displaystyle [0,1)^{s}}$

A partir de esta definición, podemos decir que si la secuencia es perfectamente aleatoria, entonces está bien distribuida en el intervalo y todos los puntos están en J, por lo tanto , pero en cambio, si la secuencia está concentrada cerca de un punto, entonces el subintervalo J es muy pequeño y entonces , entonces, tenemos del mejor y peor caso: ${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}}$ ${\displaystyle J=[0,1)^{s}}$ ${\displaystyle V(J)=1}$ ${\displaystyle F_{N}(J)=N/N=1}$ ${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=0}$ ${\displaystyle V(j)\approx 0}$ ${\displaystyle F_{N}(j)\approx N/N\approx 1}$ ${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=1}$

${\displaystyle 0\leq D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})\leq 1}$.

Notaciones

Se necesita alguna notación adicional. Para números enteros y sea el conjunto de puntos reticulares distintos de cero con para . ${\displaystyle k\geq 1}$ ${\displaystyle q\geq 2}$ ${\displaystyle C_{k}(q)}$ ${\displaystyle (h_{1},\dots ,h_{k})\in Z^{k}}$ ${\displaystyle -q/2<h_{j}<q/2}$ ${\displaystyle 1\leq j\leq k}$

Definir

${\displaystyle r(h,q)={\begin{cases}q\sin(\pi |h|/q)&{\text{for }}h\in C_{1}(q)\\1&{\text{for }}h=0\end{cases}}}$

y

${\displaystyle r(\mathbf {h} ,q)=\prod _{j=1}^{k}r(h_{j},q)}$

para . En realidad se utiliza la abreviatura , que representa el producto interno estándar de en . ${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in C_{k}(q)}$ ${\displaystyle t}$ ${\displaystyle e(t)={\rm {exp}}(2\pi \cdot it)}$ ${\displaystyle u\cdot v}$ ${\displaystyle u,v}$ ${\displaystyle R^{k}}$

Límite superior

Sean y números enteros. Sea con para . ${\displaystyle N\geq 1}$ ${\displaystyle q\geq 2}$ ${\displaystyle {\mathbf {t} }_{n}=y_{n}/q\in [0,1)^{k}}$ ${\displaystyle y_{n}\in \{0,1,\dots ,q-1\}^{k}}$ ${\displaystyle 0\leq n<N}$

Entonces la discrepancia de los puntos satisface ${\displaystyle {\mathbf {t} }_{0},\dots ,{\mathbf {t} }_{N-1}}$

${\displaystyle D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})}$≤ + ${\displaystyle {\frac {k}{q}}}$ ${\displaystyle {\frac {1}{N}}}$ ${\displaystyle \sum _{h\in \mathbb {C} _{k}(q)}}$ ${\displaystyle {\frac {1}{r(\mathbf {h} ,q)}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}}$

Límite inferior

La discrepancia de puntos arbitrarios satisface ${\displaystyle N}$ ${\displaystyle \mathbf {t} _{1},\dots ,\mathbf {t} _{N-1}\in [0,1)^{k}}$

${\displaystyle D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})\geq {\frac {\pi }{2N((\pi +1)^{l}-1)\prod _{j=1}^{k}{\rm {max}}(1,h_{j})}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}}$

para cualquier punto reticular distinto de cero , donde denota el número de coordenadas distintas de cero de . ${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in Z^{k}}$ ${\displaystyle l}$ ${\displaystyle {\mathbf {h} }}$

Estos dos teoremas muestran que el CIG no es perfecto porque la discrepancia es mayor estrictamente que un valor positivo, pero también el CIG no es el peor generador ya que la discrepancia es menor que un valor menor que 1.

También existen teoremas que limitan el valor promedio de la discrepancia para generadores compuestos inversos y también otros que toman valores tales que la discrepancia está limitada por algún valor que depende de los parámetros. Para más detalles, consulte el artículo original. ^[9]

Véase también

• Generador de números pseudoaleatorios
• Lista de generadores de números aleatorios
• Generador congruencial lineal
• Números pseudoaleatorios congruenciales inversos generalizados
• Función pseudoaleatoria de Naor-Reingold

Referencias

1. WS Chou, Sobre polinomios de período máximo inverso sobre cuerpos finitos , Álgebra aplicable en ingeniería, comunicación y computación, n.º 4/5, 1995, págs. 245-250.
2. J. Eichenauer-Herrmannn. Los números pseudoaleatorios congruenciales inversos evitan los planos , Math.Comp., vol. 56, 1991, págs. 297-301.
3. J. Eichenauer-Herrmannn, H. Grothe, A. Topuzoglu, Sobre la estructura reticular de un generador no lineal con módulo ${\displaystyle 2^{\alpha }}$ , J.Comput. Appl. Math., Vol. 31, 1990, págs. 81-85.
4. J. Eichenauer-Herrmannn, H. Niederreiter , Límites inferiores para la discrepancia de números pseudoaleatorios congruenciales inversos con módulo de potencia de dos , Math. Comp., Vol. 58, 1992, págs. 775-779.
5. J. Eichenauer-Herrmannn, Independencia estadística de una nueva clase de números pseudoaleatorios congruenciales inversos , Math. Comp., Vol 60, 1993, págs. 375-384.
6. P. Hellekalek, Generadores de números pseudoaleatorios inversos: conceptos, resultados y vínculos , Actas de la Conferencia de simulación de invierno, 1995, págs. 255-262.
7. J. Bubicz, J. Stoklosa, Algoritmo de diseño de generador congruencial inverso compuesto , §3.
8. H. Niederreiter , Nuevos desarrollos en generación de números pseudoaleatorios uniformes y vectores , Métodos de Monte Carlo y cuasi-Monte Carlo en computación científica, Berlín, 1995.
9. J. Eichenauer-Herrmann, F.Emmerich, Números pseudoaleatorios congruenciales inversos compuestos: un análisis de caso promedio , American Mathematical Society.

Enlaces externos

• Generadores Inversores Archivado el 24 de septiembre de 2008 en la Wayback Machine en la Universidad de Salzburgo .