How was this Mersenne Twister seed for a 20-character string known a priori found? Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string:

"9!dlroW ,olleH"ck,@


Which is 20 characters long. Why he did it is explained below, but I don't know how he hacked it.

Why he did it:

The user feersum on Code Golf did this to generate a Hello, World! program in the Seed programming language. Obviously he didn't merely brute force his way to this seed, which is 4200 digits in length. How did he do this? Furthermore, this user has other answers in which he uses what is presumably the same trick, see: this answer.

What we know: The seeds tend to be quite large (much larger than if they were brute forced by addition-and-generation). Furthermore, every seed he finds must generate 624 integers with the seed before twisting the next 20 to produce the above string's numerical data. The complexity to brute force a string of n length is O(96^n), very complex indeed.

What I suspect: He filters what seeds he generates in such a way as to reduce the complexity for n length to about O(log(96^n)), which simplifies to O(1). I don't think that "he has access to a supercomputer" is a viable answer.

An acceptable answer: Anything which explains how he might have done this, even if he actually did it differently. It might take a long time for the answer to this to be known.

Interesting Mersenne Twister trivia: You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

Note: Several bounties were pledged on the Hello, World! question for him if he were to explain how he did it. Years have passed, and he is not budging. Maybe those bounties will be passed on to you for having explained this.
How did he do this?


Actually, you gave much of it away when you mentioned:


  You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.


This is true, but you can do other things with it.  You can also generate previous output (that is, what the Mersenne twister output would be on blocks previous to the one you saw),previous states (that is, what the twister state had to be so that, after an iteration of the twister, you would get the selected state) and also compute the necessary seed to obtain a specific state.

Hence, most likely here's what he did:


Created an output of 624 integers, which consisted of the "9!dlroW ,olleH"ck,@ (which is 20 bytes or 5 integers), along with 619 arbitrary values.  These last 619 integers will be ignored, and hence it doesn't matter what values you select for them.
Reconstructed the internal twister state needed to generate this output.
Generated the previous twister state needed to generate this state after going through the twister permutation
Generated the seed needed to generate this twister state


And that's it.  The above is a bit tedious to do by hand; it'd be fairly trivial for a program.