generador de numeros aleatorios

Método de Congruencias Lineales Modulares

Posted by

2

z_{n}=\left( az_{n-1}+c\right) \mbox{mod}m

Donde a,c,m,z_{0} son enteros positivos conocidos, n\in \mathbb{N} y z_{0} es la «semilla» del método.

Ésta sucesión así definida, genera un conjunto de números pseudo-aleatorios que tiene periodo completo si se cumplen:

1) El mcd de \left( m,a\right) es igual a 1. (mcd=Máximo Común
Divisor)

2) Si p es un primo tal que p\backslash m entonces

p\backslash \left(a-1\right)

3) Si 4\backslash m entonces 4\backslash \left( a-1\right)

EJEMPLO

Si z_{0}=8,a=3,c=5,m=19 entonces z_{1}=\left( 3\ast 8+5\right) \mbox{mod}19=10 y la sucesión generada es:

z_{i}=\left\{ 10,16,15,17,18,2,11,0,5,1,8,...\right\}

SIN RECURSIVIDAD

Se probará por inducción sobre n que al resolver la recursividad
nos queda

z_{n}=\left( a^{n}z_{0}+\frac{c\left( a^{n}-1\right) }{a-1}\right) \mbox{mod}m

Para n=0 es obvio que z_{0}=\left( z_{0}\right) \mbox{mod}m, al igual que para n=1 queda z_{n}=\left( az_{0}+c\right) \mbox{mod}m

Suponemos para n=k que

z_{k}=\left( a^{k}z_{0}+\frac{c\left( a^{k}-1\right) }{a-1}\right) \mbox{mod}m

Y ahora para n=k+1 tenemos por definición

z_{k+1}=\left( az_{k}+c\right) \mbox{mod}m

Sustituyendo z_{k}

z_{k+1}=\left( a^{k+1}z_{0}+\frac{ac\left( a^{k}-1\right) }{a-1}+c\right) \mbox{mod}m

z_{k+1}=\left( a^{k+1}z_{0}+\frac{c\left( a^{k+1}-a\right) +c\left(a-1\right) }{a-1}\right) \mbox{mod}m

z_{k+1}=\left( a^{k+1}z_{0}+\frac{c\left( a^{k+1}-1\right) }{a-1}\right) \mbox{mod}m

Demostrado \forall n\in \mathbb{N}\cup \left\{ 0\right\} .

Post #04 – mycomplexsoul