What's causing the poor randomness in this program: the LCG, or the program logic itself?

Question

(Crypto Gods, I should begin by stressing that I haven't lost my mind: I'm not doing this in real life, I'm just trying to understand the theory behind what's happening. With your help, hopefully I can do that.)

Let's say I choose the parameters for a linear congruential generator $L$, and pick a seed $L_0$. I then use the LCG to generate sequential pseudorandom numbers $L_1, L_2$ for the following program (which, for the sake of argument, picks two different indices in a 52-element array):

$x := L_1 \bmod 52$

$y := (x + 1 + (L_2 \bmod 51)) \bmod 52$

Let's say I choose $m = 8192$, $a = 4801$, and $c = 83$. By looking at the value of $x$, I can learn quite a lot about the value of $y$: for any $x$, there are only about nine or ten possible subsequent $y$s, and they're very unevenly distributed.

Then I tried other values of $a$ and $c$, and got very different results: for instance, $a = 2049$ and $c = 8141$ gives a distribution that produces all possible values of $y$ for a given $x$, and the distribution is much more uniform. It's still poor, but compared to the first set of parameters, it's a huge improvement.

My question is this: what's causing this drastic variation? I initially thought it might be because $m = 8192$, $a = 4801$, and $c = 83$ didn't satisfy the maximum period length theorem, but then I realised that (a) they do, and (b) that would be unlikely to cause this effect on this scale anyway, since I'm only generating two numbers sequentially. Is it some property of the way that the LCG output is being used that leads to this behaviour, or is it intrinsic to the LCG itself? If it's the latter, is there a theorem that states some properties that must hold in order for the joint distribution of $x$ and $y$ to be uniform (as far as possible, given that the program guarantees $x \neq y$)?

Answer 1

Let's say I choose $m = 8192$, $a = 4801$, and $c = 83$. By looking at the value of $x$, I can learn quite a lot about the value of $y$: for any $x$, there are only about nine or ten possible subsequent $y$s, and they're very unevenly distributed.

With a LCG every $L_1$ has a single possible $L_2$, and for a maximal period the reverse is also true. With your formula each $x$ corresponds to about $m/52$ possible $L_1$, and thus $m/52$ possible $L_2$.

The form of the $L_1$ for a given $x$ is $L_1 = x + 52n$, for some $n$. Thus the $L_2$ for a given $x$ is:

$$L_2 = (52an + ax + c) \mod m$$

What you wish is for different values of $n$ to give different $L_2$, i.e. for it to be a decent LCG where $a' = 52a$ and $c' = ax + c$. Substitute $a$ and you get $a' = 3892 = 2^2 \cdot 7 \cdot 139$. For maximal period $a'-1 = 3891 = 3 \cdot 1297$ would have to be divisible by 4 (due to $m$ being), which it is not, so this will give very poor results, as you observe.

If you fixed this, e.g. by choosing another value for $m$, you would also need to consider a condition for $c'$ and how the subsequent modular reductions and addition of $x$ affect it. Also, reducing a random number from the range $0 \le x < m$ modulo 52 will always be biased towards the small numbers unless $m$ is a multiple of 52.