Index in PRNG output sequence

Question

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:

1. How hard is it in general? $O(2^n)$ for $N$ bit words, or much less?
2. Which PRNGs, if any, is it easy for? Looking for polynomial to $N$, or at least subexponential.
3. How to detect when the given word doesn't appear in the output sequence, when it's not obvious like with a LCG.
4. 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.

Answer 1

Pick your favorite $b$-bit block cipher $E_k$, say AES-256. Let $k$ be the seed and let the $i^\text{th}$ output be the $b$-bit string $x_i = E_k(i)$. Then $i = E_k^{-1}(x_i)$. Given $k$ and $x_i$, this is widely considered to be ‘easy’, for most block ciphers including AES-256. Note that every possible $b$-bit string has an index.

$\newcommand{\Z}{\mathbb{Z}}$Pick your favorite 2048-bit safe prime $p$, say $2^{2048} - 1942289$, and your favorite nonzero generator $a$ of $(\Z/p\Z)^\times$, say $5$. Let $x_0 \in (\Z/p\Z)^\times$ be the seed and let the $i^\text{th}$ output be $$x_i = a x_{i - 1} = a^i x_0.$$ Then $a^i = x_i x_0^{-1}$, so that $i = \log_a x_i x_0^{-1}$. This is widely considered to be ‘hard’, for sufficiently large safe primes including $2^{2048} - 1942289$. Note that every possible element of $(\Z/p\Z)^\times$ has an index.

Defining ‘easy’ and ‘hard’ is left as an easy exercise for the reader. Deciding whether to encode $i$ as little-endian or big-endian for $E_k$ is left as a hard exercise for the reader.

This does not address any security of these PRNGs. One of these is fit for use in cryptography; the other is emphatically not. Since you didn't mention any security requirements in your question, I didn't mention any security properties in my answer. Figuring out which one is which is also left as an exercise for the reader. (I hope you're taking notes, because there'll be a quiz on Thursday next week about all these exercises!)