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 número primo q, es:

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

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

Dicho generador 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 .

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

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

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.

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

En este ejemplo,${\displaystyle f(x)=x^{2}-3x-2}$es irreductible en${\displaystyle \mathbb {F} _{5}[x]}$, 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${\displaystyle \mathbb {F} _{5}[x]/(f)}$y por lo tanto f es primitiva.

La construcción de un generador inverso compuesto (GIC) 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.

Dejar${\displaystyle p_{1},\dots ,p_{r}}$sean números primos distintos, cada uno${\displaystyle p_{j}\geq 5}$. Para cada índice j , 1 ≤ j ≤ r , sea${\displaystyle (x_{n})_{n\geq 0}}$ser una secuencia de elementos de${\displaystyle \mathbb {F} _{p_{j}}}$periódico con duración del período ${\displaystyle p_{j}}$. En otras palabras,${\displaystyle \{x_{n}^{(j)}\mid 0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}}$.

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

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

${\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 un período completo, en sistemas de generación en paralelo.

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 invertidas, ampliamente probadas con diversas pruebas estadísticas, permanecen estables ante la variación de parámetros. ^{[ 2 ] [ 3 ] [ 4 ]}

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

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

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

El procedimiento para diseñar esta compleja estructura comienza con la definición de un campo finito de p elementos y finaliza con la elección de los parámetros a y c para cada generador congruencial inverso, que constituye el generador compuesto. Esto significa que cada generador está asociado a un polinomio IMP fijo. Esta 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 método más eficiente para encontrar los parámetros del generador congruencial inverso con el período máximo.

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 , pueden analizarse en función de la discrepancia de s -tuplas de números pseudoaleatorios sucesivos con${\displaystyle s=1}$y${\displaystyle s=2}$respectivamente.

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

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

Hasta ahora, teníamos secuencias de enteros del 0 al ⁠${\displaystyle T-1}$⁠ , para tener secuencias de${\displaystyle [0,1)^{s}}$, se puede dividir una secuencia de enteros por su período T.

A partir de esta definición, podemos decir que si la secuencia${\displaystyle {\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}}$Si es perfectamente aleatorio, entonces está bien distribuido en el intervalo${\displaystyle J=[0,1)^{s}}$entonces${\displaystyle V(J)=1}$y todos los puntos están en J, así que${\displaystyle F_{N}(J)=N/N=1}$por eso ${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=0}$pero si la secuencia se concentra cerca de un punto, entonces el subintervalo J es muy pequeño.${\displaystyle V(j)\approx 0}$y${\displaystyle F_{N}(j)\approx N/N\approx 1}$entonces${\displaystyle D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=1}$ Luego tenemos, desde el mejor y el peor de los casos:

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

Es necesaria alguna notación adicional. Para números enteros${\displaystyle k\geq 1}$y${\displaystyle q\geq 2}$dejar${\displaystyle C_{k}(q)}$sea ​​el conjunto de puntos de la red distintos de cero${\displaystyle (h_{1},\dots ,h_{k})\in Z^{k}}$con${\displaystyle -q/2<h_{j}<q/2}$para${\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${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in C_{k}(q)}$. Verdadero${\displaystyle t}$la abreviatura${\displaystyle e(t)={\rm {exp}}(2\pi \cdot it)}$se utiliza y${\displaystyle u\cdot v}$representa el producto interno estándar de${\displaystyle u,v}$en${\displaystyle R^{k}}$.

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

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

${\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 |}}$

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

${\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 de la red distinto de cero${\displaystyle {\mathbf {h} }=(h_{1},\dots ,h_{k})\in Z^{k}}$, dónde${\displaystyle l}$denota el número de coordenadas distintas de cero de${\displaystyle {\mathbf {h} }}$.

Estos dos teoremas muestran que el CIG no es perfecto porque la discrepancia es estrictamente mayor 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 acotan el valor promedio de la discrepancia para generadores inversos compuestos, así como otros que toman valores tales que la discrepancia queda acotada por algún valor que depende de los parámetros. Para más detalles, véase el artículo original. ^{[ 9 ]}

• 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

• Generadores inversos archivados el 24/09/2008 en la Wayback Machine de la Universidad de Salzburgo .