diff options
Diffstat (limited to 'lib/mt_19937_tempering.txt')
| -rw-r--r-- | lib/mt_19937_tempering.txt | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/lib/mt_19937_tempering.txt b/lib/mt_19937_tempering.txt new file mode 100644 index 0000000..dfdda7a --- /dev/null +++ b/lib/mt_19937_tempering.txt @@ -0,0 +1,34 @@ +Why can we reverse the tempering function? + +There are to kinds of operations in the tempering function of the MT: + + 1) Right shift + 2) Left shift with an AND + +To undo the first operation, a simple shift is straight forward. Let's consider +the following example of a 24-bit number + + 0010 1010 1011 1101 1111 0111 y + 0000 0000 0000 0000 0000 1010 1010 1111 0111 1101 11 y >> 18 := N + ^ + orginal string + 0010 1010 1011 1101 1111 1101 y ^ (y>>18) := M + + +On can see, that the first 18 bits of M are the same than y. That's clear, +because we have shifted 18 new 0 into it. But now we also now N completly, since +the last 6 bits are the first 6 of M (N is a shifted version of M). +If you shift less than 24/2 = 12 bits, you have to do the above steps in a +loop, because you cannot determin N completly one step. + +To understand why one can undo the second operation was a bit harder for me. +For me it was the easiest to understand it with the feistel network. + + + y y << 15 + | | + | | + XOR<--------- F <----------- + | | + \_______________________ / + /\______________________ |