#### Topic: Reversing PRNGs

How one could achieve a "random" behaviour of index variable in a polymorphic decription loop? This topic was already mentioned on this forum, here (MentalDriller's PRIDE, xor-based permutation). Another idea is to use a LCG and find the modular mulptiplicative inverse for the selected multiplier. I wont go into math details of the topic (you can easily find all neccessary info in Wiki), so suppose that we have LCG: x_next = (a * x + c) mod m; if we choose prime m, it's immediately follows from the properties of LCG, that there exists such r, that (a * r) mod m = 1, and that **x_prev** = (r * (x - c)) mod m. In other words it is the random numbers generator which could produce the same sequence in a reverse order. Given the multiplier a and modulus m, r could be foud with the followig code:

```
uint32_t xgcd(uint32_t a, uint32_t b)
{
uint32_t x, y, u, v, m, n, q, r, b0;
x = 0; y = 1; u = 1; v = 0;
b0 = b;
while (a != 0) {
q = b / a; r = b % a;
m = x - u * q; n = y - v * q;
b = a; a = r; x = u;
y = v; u = m; v = n;
}
return x % b0;
}
...
r = xgcd(a, m);
```

the you can go through the sequence both forward and back with

```
uint32_t lcg(uint32_t x)
{
return (x * a + c) % m;
}
uint32_t icg(int32_t x)
{
x -= c;
while (x < 0)
x += m;
return (r * x) % m;
}
```

so the following code

```
/* test1 */
for (i = 0; i < 10; i++) {
y = lcg(y);
printf("%d:%u\n", i, y);
}
for (i = 9; i >= 0; i--) {
printf("%d:%u\n", i, y);
y = icg(y);
}
```

would produce:

```
0:222
1:288
2:142
3:196
4:163
5:236
6:209
7:67
8:189
9:44
9:44
8:189
7:67
6:209
5:236
4:163
3:196
2:142
1:288
0:222
```

(with a = 17, m = 317, c = 1 and calculated r = 56).

And don't forget that m must be prime, or the rest of constats should be selected by differet criteria.

P.S. I would like to thank whale who years ago asked how to construct reversible rng, just found his message recently ad bothered to find the aswer.

P.P.S. Most likely I will write a few words more on this topic.

**update (2011-01-28)** Here is the link to the article that appeared in VWB#1:

herm1t Inversing a random numbers

and significant correction.