Linear congruential generator

[mary_201091]

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

[cosine]

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).

[Mr Skeptic]

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

[cosine]

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?

[timo]

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

[Mr Skeptic]

Ah, that makes more sense timo.

 

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