21 Jul 2009 randombit   » (Journeyer)

Inverting Mersenne Twister's final transform

The Mersenne twister RNG 'tempers' its output using an invertible transformation:

unsigned int temper(unsigned int x)
   {
   x ^= (x >> 11);
   x ^= (x << 7) & 0x9D2C5680;
   x ^= (x << 15) & 0xEFC60000;
   x ^= (x >> 18);
   return x;
   }

The inversion function is:

unsigned int detemper(unsigned int x)
   {
   x ^= (x >> 18);
   x ^= (x << 15) & 0xEFC60000;
   x ^= (x << 7) & 0x1680;
   x ^= (x << 7) & 0xC4000;
   x ^= (x << 7) & 0xD200000;
   x ^= (x << 7) & 0x90000000;
   x ^= (x >> 11) & 0xFFC00000;
   x ^= (x >> 11) & 0x3FF800;
   x ^= (x >> 11) & 0x7FF;

   return x;
   }

This inversion has been confirmed correct with exhaustive search.

This is more a note to my future self than anything else; I'm cleaning out my ~/projects directory, and I can either publish this somewhere or check it into revision control (well, actually the contents of this blog are also in revision control, but no matter).

Syndicated 2009-07-21 20:40:01 from Jack Lloyd

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!