Is it possible to find a seed to generate given set of integers?

Given certain ranfom integer numbers defined over [1 N]. Is it possible to find a SEED that is cappable of doing the inverse operation. As an example N=10, given the random numbers 4, 8, 3, 6, 1, 2, 9, 10, 5, 7, Now

Is it possible to find suitable SEED To generate the random number sequence.

Regards

Answer 1

[John D'Errico]

Even for short sequences, finding a seed that would recover a given sequence will potentialy be difficult and it would strongly depend on the random number scheme used to produce that sequence, but is this possible to accomplish at all in general? NO.

Your goal is provably not possible to accomplish, since you might have a sequence of arbitrary length. Therefore the seed, IF it existed, must have sufficient information content available in it, and a seed, by definition, will be itself a number with a fixed number of bits in it.

We can think of this as a hashing scheme, where you implicitly need to encode ALL of the information content in a sequence of length N, into a single number with a fixed number of bits and N may be as large as you wish. If your sequence is long enough, then this is simply not possible.

Sorry.

[Omar Ali Muhammed]

N might be hundred of thousands

[Walter Roberson]

In the case where you are using any of the pseudo-random generators supported by MATLAB, then the answer is Yes, it is possible, because all of them only support finite periods after which they repeat. You can mechanically try all of the possible seeds one by one until you get a match.

A few years ago I was able to reconstruct sequences up to length (if I recall correctly) 15 (I didn't have a reason to go further at the time.)

This approach is, of course, very very inefficient. For any given generator there might be more efficient ways based upon theoretical analysis of the generators -- for example you might be able to deduce that the seed raised to a certain power had a certain modulo base a certain prime, and each successive known input might add more and more constraints as to what the seed had to be mathematically, allowing you to reduce the search space.

[Omar Ali Muhammed]

Dear, I suppose using the MATLAB function randperm() for PRNG. So what is the theory behind what you deduced based on your experiment. Can you explain in more detailes your stratigy.

Regards

[Walter Roberson]

These days randperm() is implemented using the Fisher-Yates Shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Before that, randperm() was implemented as

function y = randperm(n,k)
   [~,idx] = sort(rand(1,n));
   y = idx(1:k);
end

I am not sure what the theoretic analysis of either of those would be.

My earlier experiments were mechanical: I just kept increasing the seed until I got a match.

Hmmm... If I recall correctly, I was exploring "the numbers games", also known as "The Lottery". A certain number of "balls" are drawn from a pool of balls labeled with consecutive numbers, and prizes are awarded according to how many of your numbers match (in any order) the numbers drawn. My question was "if the numbers were drawn by randperm() instead, how short of a leading subset do you need to know in order to be able to find a seed that gives the complete sequence?". I swept a limited range of seeds, and was surprised how many matches I could get for the entire sequence I was working with. I also got non-matches that stopped one short, which implicitly answered the question that in that context, using that technique, you needed the entire sequence. This left open the hypothesis that if you did a better mathematical analysis that you might be able to do better; it also left open the hypothesis that there might be a prefix length beyond which if you knew the entire prefix you could continue the prediction, having established the seed.

A relevant question is whether the set of positive integer double precision numbers is enough to uniquely identify the state of Mersenne Twister . Mathematically you would expect not.