Desarrollo y diseño

10 números siguientes a una serie de 1000

R
rapers123 #1 Jun '11

Buenas, tengo un problema que no consigo resolver y me hace aprobar una asignatura:

El juego consiste en encontrar los 10 siguientes numeros que siguen a la lista de 1000 numeros proporcionada, los numeros se han generado mediante un sistema afin similar al de la rutina rand() de la libreria estandar del C en la implementacion de visual C++.

LLevo varios días y no consigo sacar de qué manera se generan los números de la serie, el profesor me ha dicho que actúa como un registro desplazador de 32 bits pero no consigo sacar los 10 números siguientes.

Fichero con los 1000 números:

spoiler

Si conseguis sacar los 10 números siguientes a esos 1000 números os estaría eternamente agradecido.

Gracias.

MaTRiX13
MaTRiX13 #2 Jun '11 TGD.PRO ZaCkETiZOR

editado

1 respuesta
V
vidic #3 Jun '11

#2
eres un crack

R
rapers123 #4 Jun '11

Por favor si alguien lo consigue sacar o sabe como ayudarme lo necesito para aprobarla....

LOc0
LOc0 #5 Jun '11

Puedes probar suerte con:

http://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

http://vierito.es/wordpress/2011/01/22/breaking-lfsr-based-pseudo-random-number-generators/

http://www.redeweb.com/_txt/artikel/3060366.pdf

Y de regalo una herramienta online:

http://berlekamp-massey.appspot.com/

La idea es que conviertas esa lista de números en un chorizo de UNOS Y CEROS y se lo enchufes al programita para que te devuelva la "fórmula" que sigue y a partir de ella sacar los 10 números siguientes.

Por curiosidad #1, ¿qué estudias?

Salu2 ;)

1 respuesta
tOWERR
tOWERR #6 Jun '11

No entiendo muy bien, los 10 siguientes numeros seria los siguientes al mayor de esa lista de 1000 numeros o cual? Es que no entiendo muy bien el ejercicio. Si es lo del mayor es facil, se busca el mayor y luego se sacan los 10 siguientes incrementandolo, pero no creo que sea eso tan facil. ¿Podria alguien explicar el ejercicio un poco mejor, para gente torpe en enunciados?

Pyronhell
Pyronhell #7 Jun '11

Es una sucesión de 1000 números, y el profesor le pide los 10 siguientes.

Caotico
Caotico #8 Jun '11 Cofrade

No sé si es eso lo que buscas, espero que te sirva

Editado por moderador: No sé si intentabas hacer una gracieta, pero evidentemente +1000 números no es la respuesta que #1 espera (10 números). Ojo con lo que ponéis.

R
rapers123 #9 Jun '11

El objetivo es hacer una función parecida a rand() en C++...mi profesor me ha dicho que él ha creado una función parecida ya que rand() se asemeja a un desplazador de registro de 32 bits.
rand() es una función que genera números aleatorios pero que NO SON ALEATORIOS, es decir, genera números en teoría al azar pero lleva un procedimiento conseguirlos. Este procedimiento es el de desplazar 32 bits(creo que a la derecha así que sería un shift register como bien dice un compañero).
El caso es que tengo algo pensado pero es demasiado grande ni mi ordenador con un i7 lo puede procesar porque tendría que hacer 2.64 operaciones.

Estudio ingeniería de Telecomunicaciones y necesito AYUDAAAA.
Jaja gracias.

R
rapers123 #10 Jun '11

#5 No entiendo muy bien que debo hacer con el programa ya que si meto los 1000 números del tirón en binario eso no cabe en ningún lado...Estoy probando con cada número y viendo el LFSR que sale pero de momento no consigo encontrar una secuencia.

1 respuesta
LOc0
LOc0 #11 Jun '11

#10 Hola. A ver, SUPUESTAMENTE si lo que ha usado tu profe es un LFSR de 32 bits para ir generando los números aleatorios puede ser desde bastante chungo hasta casi imposible sacar el "patrón" o polinomio característico del generador aleatorio. Si el generador es muy bueno tendrá un periodo muy largo y viceversa. La idea es que tú tienes un registro de 32 bits tal que así:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

que inicializas con un valor SECRETO, pongamos:

00101000101010010100101010101010

y con un "polinomio" SECRETO (pongamos X4 + x8) (como ves hay "un huevo" de polinomios posibles para 32 bits y de valores iniciales).

En cada "vuelta" tú coges el BIT 4 y el 8 y les haces XOR y te da otro bit (el bit 1 es el primero por la izquierda). Después desplazas a la derecha tu registro y metes por la izquierda el bit que calculaste antes y obtienes el primer bit de salida por la derecha. Esto te irá generando una secuencia de bits de salida que tiene un periodo X desconocido (menor o igual que 232 -1 que es el periodo máximo que consigues con polinomio "primitivo" ). A partir de dicho periodo la lista de salida empezará a repetirse.

Yo entiendo que tu profe va sacando bits del registro y cada 15 bits lo considera un número aleatorio nuevo (lo digo porque de esos 1000 números ninguno pasa de 15 bits). Pero este dato es desconocido también ¬ ¬...

Lo que yo te decía es que cogieras esa lista de números, la pasaras a binario (metiendo ceros por la izquierda hasta llegar a 15 bits por cada número) y se la enchufaras al programa que usa Berlekamp_Massey para ver si te saca el polinomio)...

Otra opción sería con el chorizo binario ir mirando a ver cuándo empieza a repetir la cadena de salida (si es que se repite)...

No se me ocurre nada más de momento, sorry :(

¡Ánimo!

Salu2 ;)

2 respuestas
R
rapers123 #12 Jun '11

Estoy en ello trabajando en matlab y en C++ con el algoritmo de Berlekamp-Massey pero me sale esto de polinomio C:
L =

77

C =

1.0e+013 *

Columns 1 through 9

0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0001    0.0001

Columns 10 through 18

0.0003    0.0007    0.0015    0.0030    0.0055    0.0097    0.0163    0.0265    0.0415

Columns 19 through 27

0.0626    0.0915    0.1295    0.1779    0.2376    0.3087    0.3907    0.4822    0.5807

Columns 28 through 36

0.6829    0.7847    0.8815    0.9687    1.0415    1.0962    1.1296    1.1399    1.1267

Columns 37 through 45

1.0909    1.0347    0.9614    0.8750    0.7800    0.6809    0.5820    0.4870    0.3987

Columns 46 through 54

0.3194    0.2501    0.1915    0.1432    0.1045    0.0744    0.0516    0.0349    0.0230

Columns 55 through 63

0.0147    0.0091    0.0055    0.0032    0.0018    0.0010    0.0005    0.0003    0.0001

Columns 64 through 72

0.0001    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000

Columns 73 through 78

0.0000    0.0000    0.0000    0.0000    0.0000    0.0000

No se como interpretar el polinomio..

1 respuesta
skv
skv #13 Jun '11

#11 #12 Exacto, como bien te ha dicho L0c0 yo entiendo que será uno posible de romper. El principal problema es que no conoces la semilla ni su tamaño, pero bueno, se pueden hacer suposiciones: como ya te dijeron, todos los números son de 15 bits, así que una vez descubierta la secuencia de actualización puedes probar con todas las semillas posibles (215). Aunque 15 es un tamaño un tanto raro (16 es mucho más común, media palabra), yo he probado a meter el chorro de bits en el algoritmo Berlekamp-Massey y no ha salido nada, es posible que sean grupos de 15. Otra opción es pintar los bits por si reconoces algún patrón visual sencillo. Léete esto:

http://www.painsec.com/?p=58#more-58

1 respuesta
R
rapers123 #14 Jun '11

#11 #13Esto es lo que me ha dado el profesor pero a lo mejor no sirve para nada el caso es que las semillas son 214013L y 2531011L que es lo que hay que variar entre 1 y 216 pero habría que hacer dos bucles anidados y serían 232 iteracciones que no creo que haya ordenador que las soporte...nose si estoy bien encaminado así...

R
rapers123 #15 Jun '11

Aquí el código:
static long holdrand = 1L;

int cdecl__rand ( void )
{
return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

R
rapers123 #16 Jun '11

holdrand es el número por el que empezar que lo tenemos y >> 16 también está bien porque es lo que desplaza el número...el problema son las semillas...

R
rapers123 #17 Jun '11

#include "stdio.h"
#include "math.h"

long comprobar(long posicion,long num){

long lista[1000];
long i=0;

if(lista[0]!=17678){
FILE * f;

f=fopen("afin.txt","r");
while(!feof(f) && i<10){
fscanf(f,"%ld",&lista[i]);


printf("lista[%ld]:%ldn",i,lista[i]);
i++;
}
fclose(f);

}

if (lista[posicion]==num)
	return 1;
else
	return 0;

}

void main(int argc,char *argv[]){
long m=3;
long a;
long c;
long x;

int j,ska;

//La estamos peinando

long inicialA=1L;
long finalA=(inicialA<<31)-1;

long inicialC=1;
long finalC=(inicialC<<10);

printf("Datos iniciales:n");
printf("A irá de %ld a %ldn",inicialA,finalA);
printf("C irá de %ld a %ldn",inicialC,finalC);

for(c=inicialC;c<=finalC;c++){
	if (c%100==0)
		printf("nnc:%ldn",c);
	for(a=inicialA;a<=finalA;a++){
		//printf("na:%ldn",a);
		j=0;
		ska=0;
		x=17678;
		//Este while es para comprobar si se están hallando los números de la serie
		while(j<8 && ska==0){
			if (comprobar(j,x)==1){
				j++;
				//Con 7 coincidencias terminaría... (habría q poner 1000 y tal)
				if (j==7){
					ska=88;
					printf("Cerdo a la vista!!=)n");
					printf("a:%ldn",a);
					printf("c:%ldnn",c);
				}
				else if (j>2){
					printf("Coincidencias:%dn",j);
					
				}
			}
			else{
				//Esto es para salir del while si no coincide con el nº de la serie!	
				ska=1;			
			}
			//El algoritmo del tipo!
			x=((a*x+c)>>16)&0x7fff;
		}
	}
}

printf("Esto ha acabado, fijate cuanto ha tardado porq el definitivo sería 4000 veces másnn");
printf("Risas!n");

}
Este es el código que he implementado el caso es que tarda mucho ... deberíamos optimizarlo

skv
skv #18 Jun '11

Ponlo en pastebin.org, no puedo leer nada sin identación!.

R
rapers123 #19 Jun '11

http://pastebin.com/C69za8VP
Otra cosa el profesor me ha dicho que:

pensabas que el numero de la lista era la semilla del siguiente

y ahora resulta que no, que el numero de la lista solo son unos bits

y no sabemos la semilla del siguiente

por eso pueden salir dos numeros "iguales"

pero q en realidad no son iguales

1 respuesta
skv
skv #20 Jun '11

#19 Eso último me ha dejado descolocado, no entiendo que quiere decir.

R
rapers123 #21 Jun '11

A ver,esto ya es como un juego nuevo porque el profesor me ha dado muchas pistas y todo lo anterior no servía para nada.Lo que hay que hacer y con qué hacerlo:

Hola Guillermo:

Si, esa es la rutina,, sobre por donde empezar, pues yo miraria, primero, que tienes muchos bits calculados (te doy mil numeros, que son 15000 bits,, y luego, con un poco de lapiz y papel (aunque luego seguramente tengas que tirar de Matlab o algo que trate matrices), sacar los dos parametros y medio que te faltan (el 16 y el 0x7fff no los he tocado,, y de la semilla,, no te falta toda, te faltan 17 bits...).

Saludos

Esta es la rutina:

static long holdrand = 1L;

int __cdecl rand ( void )
{
return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

Teneis alguna idea?

1 respuesta
R
rapers123 #22 Jun '11

Berlekamp no vale pero a lo mejor valdría pintarlo...no se como hacerlo ya que en la web te dan un código que luego hay que encriptar....

LOc0
LOc0 #23 Jun '11

#21 A ver, entonces el generador sería del tipo:

estado(n+1) = a*estado(n) + c (mod 232)

concretamente:

aleatorio(n+1) = ( ( estado(n+1) = a*estado(n) + c ) >> 16 ) & 0x7FFF

y no tienes ni "a" ni "c" y tp tienes el "estado interno" en cada iteración ya que la función sólo devuelve 15 bits...

Hay un "paper" titulado:
"Inferring Sequences Produced by a Linear Congruential Generator Missing Low-Order Bits" Joan Boyar que te vendría de pm porque describe un algoritmo para hacer justo lo que pides, pero no hay forma humana de encontrarlo por internet (al menos gratis) :(

Puedes deducir tú el algoritmo, pero ¿cómo vas de álgebra y estadística? ¿Y de tiempo?

Salu2 ;)

R
rapers123 #24 Jun '11

De tiempo tengo 10 días y de Álgebra bien pero es que no creo que sea tan complicado...mira yo te pego lo que me ha puesto el profesor a ver si me podeis echar una mano porque ahora ya no se por donde empezar:

Hola Guillermo:

Si, esa es la rutina,, sobre por donde empezar, pues yo miraria, primero, que tienes muchos bits calculados (te doy mil numeros, que son 15000 bits,, y luego, con un poco de lapiz y papel (aunque luego seguramente tengas que tirar de Matlab o algo que trate matrices), sacar los dos parametros y medio que te faltan (el 16 y el 0x7fff no los he tocado,, y de la semilla,, no te falta toda, te faltan 17 bits...).

Saludos

Buenas,

¿es esta la rutina?Es que no sé muy bien como empezar porque si no has modificado unicamente la semilla eso explicaría por qué se obtienen números distintos..¿alguna idea de cómo empezar?.

tatic long holdrand = 1L;

int __cdecl rand ( void )
{
return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

Gracias.

Hola Guillermo:

Si, puede ocurrir, ya que lo que la rutina te da es 15 bits del total de 32 bits de cada numero de la serie. Como te decia, mira el codigo de la rutina rand de visual c++.

Perdón pero he encontrado un número repetido(25090 en la posición 533 y 570) y el número que le sucede no es el mismo en cada caso...

Gracias.

si, claro que se puede estimar, ten en cuenta que cada numero (15 bits de un numero de 32 bits) que os doy puede ser semilla de los siguienes..

Te recomendaria que mirases el codigo de generacion de numeros aleatorios de visual c++, ya que la rutina que yo use para generar los numeros aleatorios es la misma,, solo que con otros valores.

Saludos

wOlvERyN
wOlvERyN #25 Jun '11

Me he leído todo, sin tener ni idea, y me ha parecido una manera totalmente absurda de perder mi propio tiempo pero a la vez muy interesante e imposible para mi, os pregunto, ¿Qué **** estudiais? ¿Matemáticas puras, informática, oposiciones a bombero...?

Saludos y ánimo.

8 días después
R
rapers123 #26 Jun '11

Ingeniería de Telecomunicación.

Usuarios habituales

Tags