Is it possible to reverse a pseudo random number generator?

Question

Is it possible to reverse a pseudo random number generator? For example, take an array of generated numbers and get the original seed. If so, how would this be implemented?

Answer 1

This is absolutely possible - you just have to create a PRNG which suits your purposes. It depends on exactly what you need to accomplish - I'd be happy to offer more advice if you describe your situation in more detail.

For general background, here are some resources for inverting a Linear Congruential Generator: Reversible pseudo-random sequence generator

pseudo random distribution which guarantees all possible permutations of value sequence - C++

And here are some for inverting the mersenne twister: http://www.randombit.net/bitbashing/2009/07/21/inverting_mt19937_tempering.html http://b10l.com/reversing-the-mersenne-twister-rng-temper-function/

Answer 2

In general, no. It should be possible for most generators if you have the full array of numbers. If you don't have all of the numbers or know which numbers you have (do you have the 12th or the 300th?), you can't figure it out at all, because you wouldn't know where to stop.

You would have to know the details of the generator. Decoding a linear congruential generator is going to be different from doing so for a counter-based PRNG, which is going to be different from the Mersenne twister, which is going to be different with a Fibonacci generator. Plus you would probably need to know the parameters of the generator. If you had all of that AND the equation to generate a number is invertible, then it is possible. As to how, it really depends on the PRNG.

Answer 3

Use the language Janus a time-reversible language for doing reversible computing.

You could probably do something like create a program that does this (pseudo-code):

x = seed
x = my_Janus_prng(x)
x = reversible_modulus_op(x, N) + offset

Janus has the ability to give to you a program that takes the output number and whatever other data it needs to invert everything, and give you the program that ends with x = seed.

I don't know all the details about Janus or how you could do this, but just thought I would mention it.

Clearly, what you want to do is probably a better idea because if the RNG is not an injective function, then what should it map back to etc.

So you want to write a Janus program that outputs an array. The input to the Janus inverted program would then take an array (ideally).