Método de Congruencias Lineales Modulares

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 #04mycomplexsoul

2 pensamientos en “Método de Congruencias Lineales Modulares

  1. Hola quisiera saber porque en el primer ejemplo da 17 en el cuarto resultado de la secuencia, a mi me da 12, y tambien quisiera saber que es P
    Muchas Gracias

    • Hola, tienes toda la razón, la secuencia correcta es:

      {10,16,15,12,3,14,9,13,6,4,17,18,2,11,0,5,1,8,…}

      Los puntos 2 y 3 son observaciones a los valores de m y a. Estas observaciones son válidas cuando se eligen valores que proporcionen un ciclo completo. Fuera de eso no tiene importancia el valor de p para el método.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s