# How much information do I gain from each modular inequality?

Problem details:

Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants.

Furthermore let $f(x) = a x + b \pmod{p}$

and let the value $r_k$ be defined by the first-order recurrence relation:

$r_0 = s$

$r_i = f(f(r_{i-1}))$.

Suppose we are given a sequence of values $V = [c(r_1), c(r_2), ... , c(r_n)]$

where we can think of $c(x)$ as a bit mask that reveals only the 6 most significant bits of some bit string $x$.

Question:

How long does $V$ need to be in order to solve for $s$?

Background:

Some implementations of Javascript use a Linear Congruential Generator (LCG) for the Math.random() built-in function. I'd like to see if, given a masked sequence of outputs from Math.random(), I can infer the internal state of the LCG, and thus be able to predict future masked values. If so, how many values do I need to do this?

My educated guess/approach:

I would think that with each $r_i$ we gain at least a little information about the internal state. Since we need to learn about a 48-bit number, and we learn only 6 bits per $r_i$, we probably need at least 8 values ($6*8 = 48$) before it's possible to completely infer $s$. In my specific case I get an average of 30 consecutive values, which I would think would be plenty.
One promising idea that I had last night was to think of each $c(r_i)$ as denoting an inequality over the range of possible $r_i$ values, and then solve for some system of modular inequalities-- which I have no idea how to do.
Do you really mean $f(f(r_{i-1}))$, not $f(r_{i-1})$? Running $f$ twice at each iteration is the same as running some other linear function $g$ once, anyway. – Gerry Myerson Feb 5 '13 at 3:10