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.

Was it helpful?

Solution

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.

OTHER TIPS

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.

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

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow