We have some simple PRNG, like a LCG or LFSR. Easiest is one that follows a output state, transform state cycle. Let's call that cycle an "iteration", and one of these outputs a "word".
Knowing the PRNG used, and all parameters including the starting state, we want to take a given word, and assuming it does appear in the output sequence, find the "index", that is, the number of iterations before that word appears for the first time.
Of course, this problem will vary between PRNGs, but what I want to know now is:
- How hard is it in general? $O(2^n)$ for $N$ bit words, or much less?
- Which PRNGs, if any, is it easy for? Looking for polynomial to $N$, or at least subexponential.
- How to detect when the given word doesn't appear in the output sequence, when it's not obvious like with a LCG.
- What to do with PRNGs which output only part of their state or put it through some mapping (not a crypto hash of course).
Plain LCG would be harder than discrete logarithm right? Discrete logarithm is doable in polynomial time for power of 2 modulus though. Not sure how much difficulty the addition adds.
I'd think enough nonlinearity would make this task intractable due to the complexity. So ones like xorshift and MT19937 should be doable.