Can it ever be impossible to invert a PRNG? I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output.  624 matches the state size of my implementation of the Twister.  Coincidence?  If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths?  Or is this mathematically and logically impossible?

This leads me to think about a general case.  I got this embryonic analogy from solving simultaneous equations.  Consider each member within the state array as a degree of freedom.  And consider each number output as a degree of freedom.  And if (for some generator) there is a group operation over the whole state such as an addition of all of the elements, this acts as a constraint. Can the following be true?

Let,

$F_o$ = degrees of freedom output,
$F_s$ = degrees of freedom within state,
$C_n$ = number of constraints on the state.

Is the random number generator “impossible to uniquely invert” if $F_o &lt; F_s - C_n$?
I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?


No, it's not a coincidence. The period is related to the state size, and a smaller sample cannot allow unique inversion due to the fact that every shorter number sequence appears in the total output of MT (with equal frequency to boot).

In general the same does not have to be true. A PRNG can use its state "wastefully" in such a manner that not every state is possible and inversion can happen much earlier than state size. Or it can have correlations that break it even without inversion. Contrarily, an actual cryptographically secure PRNG is expected to produce much more output than the state size without ever being invertible.

So I doubt your equation holds without additional assumptions.