How many 12 bit integers output are required to reverse the Mersenne Twister?

Question

I am creating a web app that applies Python's random algorithm (Mersenne Twister) to generate random 12-bit integers. I am concerned as to how a user can predict future results by recording the needed number of sequence using API calls

import random
def rand12bits():
    return random.randint(0, 4095)

How many of these outputs do i need to predict the future sequence?

I am aware that with enough (624) observed outputs of 32 bit integers, it can be reversed. But in this case, the RNG is only giving off 12 bit integers. Am I missing something? Pardon me for my naivity I am new at this.

Answer 1

How many of these outputs do i need to predict the future sequence?

Well, to recover the RNG state, you need to observe 19968 bits of output (which translates into state); by seeing 12 bits at a time, you'll see enough after 1665 outputs.

One question you might have is: the 12 bits might not come from consecutive Mersenne Twister outputs, so we won't be able to trivial reconstruct the 624 word state. This is true; however Mersenne Twister is completely linear in GF(2); hence we can describe the 19968 bit initial state as a linear function of the observed output states, and (with enough linear equations), solve for the initial state. This is obviously more work than the trivial 'here's one intermediate 624-word state'; however it is practical.

The other thing to note is this estimate assumed that the initial state was completely unknown. If it is partially known (e.g. the initial state was 256 bits of unknown values, followed by a known pattern), this reduces the number of outputs that are needed (because those known initial state bits give us free equations)