Is it possible to get an approximation to a seed based on a finite sequence of pseudo random numbers?

Question

suppose I have some numbers that form a series for example: 652,328,1,254 and I want to get a seed that if I, for example, do

srand(my_seed);

I will get some kind of approximation with bounded error to my origonal sequence, when all numbers appearing in the same order.

Answer 1

Depends on the algorithm used for the pseudo-random generation. If the algorithm is a simple linear congruential generator, then getting the seed back is just a matter of solving a linear modular equation (note that the solution may be non-unique, but as such a generator is memory-less, it doesn't matter).

If the algorithm is more complex, this may be impossible.

Note that the algorithm used in the C standard library isn't restricted by the standard, so different platforms may have different implementations.

Answer 2

You can't have an error bound in general. Either your algorithm works or it doesn't. The reason for this is that a reasonable error bound is obviously much smaller that RAND_MAX. That in turn means that the the low bits are not as random as the higher bits. But a good PRNG makes certain that all bits are equally random.

Consider this slow but mathematically sound example of an RNG algorithm:

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

If you can find any significant correlation between the output sequence and the previous state, the AES algorithm should be considered broken.

Answer 3

Check out this question.

Like Justin says, it's possible to backtrack a linear congruent generator (which rand() implementations often are) when you have a sequence of generated numbers. I guess the problem is to know which one of the previous values is the original seed...

Answer 4

The definition of a crytographic PRNG is one in which this exact property is computationally infeasible - however, as has been mentioned, there are much weaker (and much faster) PRNGs for which this is possible. So it depends on your algorithm.