Jump to content

Linear congruential generator


Recommended Posts

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:





Thanks a lot for your help

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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?

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.