On-the-fly pseudo-random permutation of very large set without repeating and with inverse operation

Question

I have a very large set of values (0-300000^700) and I would like to find an algorithm which would bijectively assign a unique value within the same set.

It is the equivalent of a permutation, but because of obvious memory problems, that would have to be done "on the fly". And the algorithm would need to be inverted at some point.

This problem is similar to this one in the "library of babel": http://www.fromquarkstoquasars.com/meet-the-digital-library-of-babel-a-complete-combination-of-every-possible-combination-of-letters-ever/

A LCG is used, with parameters set using the Hull-Dobell Theorem in order to assure no repetitions. The seed is used as the initial value. What I do not get is how the inverse is possible (i.e. getting the seed from the output), as I thought that would require bruteforce.

Answer 1

For LCG, seed is the same as state and serves as previous value to compute next one.LCG is known to be reversible, if

next = (a * prev + c) mod m

then

prev = (next - c) * a_inv mod m

where a_inv could be computed using Euclid's algorithm

more discussion here

Reversible pseudo-random sequence generator