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

Question

Suppose I have some numbers that form a series, for example: 652,328,1254, and I want to get a starting number, which, if I, for example, do

srand(my_seed); 

I will get some kind of limited error approximation to my original sequence when all numbers appear in the same order.

Answer 1

Depends on the algorithm used for pseudo-random generation. If the algorithm is a simple linear congruent generator , then getting the seed back is a matter of solving a linear modular equation (note that the solution may not be unique, but since such a generator has no memory, it does not matter).

If the algorithm is more complex, this may not be possible.

Note that the algorithm used in the C standard library is not limited by the standard, so different platforms may have different implementations.

Answer 2

Check out the question .

As Justin says, it is possible to cancel a linear congruent generator (which is often implemented by rand() ) when you have a sequence of generated numbers. I think the problem is to find out which of the previous values ​​is the original seed ...

Answer 3

You cannot have a common mistake. Either your algorithm works or not. The reason for this is that the reasonable margin of error is obviously much smaller than RAND_MAX. This, in turn, means that the lower bits are not as random as the higher bits. But a good PRNG ensures that all bits are equally random.

Consider this slow but mathematically sound example of the 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 4

The definition of cryptographic PRNG is one in which this exact property is computationally impracticable, however, as already mentioned, there are much weaker (and much faster) PRNGs for which this is possible. So it depends on your algorithm.