Hi, if I have a sequence of 1000 random numbers generated by a linear congruential generator of the form:

 

Xn+1=Xn*a+c mod 32

 

And i know that the 1000 numbers are extracted from the bits 30-16 (15 bits) of the numbers generated with the formula above. (i.e, they range from 0 to 32767).

 

How can i predict the 10 next numbers, i.e, how can i calculate the a, c and seed(Xo) values?

 

I know that it is possible, but i don't have access to the next paper, which i think could be very useful:

 

http://portal.acm.org/citation.cfm?id=66886

 

 

Thanks a lot for your help

You can actually do this naïvely with brute force. there are 32 choices for a and 32 choices for c, so you only have 934 possibilities. So take any two numbers next two each other in the sequence and use it as a check for all the possible values of a and c. Store the ones that work for this pair, and then try these out on another pair in the sequence. Do it until needed. This should be O(n).

Are you sure your formula is correct? It would seem to me that the numbers generated by this would be from 0 to 31.

Are you sure your formula is correct? It would seem to me that the numbers generated by this would be from 0 to 31.

Mr. Skeptic brings up a good point... Mary, are your 1000 numbers an ordered sequence?

I think it's rather obvious that mary meant "(... ) mod 2^32", not " ... mod 32".

Ah, that makes more sense timo.

 

I think brute forcing this one won't work too well.