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:

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

Thanks a lot for your help

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

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

##### 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?

##### Share on other sites

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

##### Share on other sites

Ah, that makes more sense timo.

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

## 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
×

• #### Activity

• Leaderboard
×
• 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.