Random String generation from a given string, and inverse transform

Question

I am working on a requirement where a function f will use string s as a seed and generate n no of strings y_0..n , I can easily do this, but I also want to do inverse ie, f^-1(y_i) of generated strings will give me back s.

y₀ = f(s) # first time I call f(s) it gives me y₀

y₁ = f(s) # second time I call f(s) it gives me y₁

...

y_i = f(s) # i_th time I call f(s) it gives me y_i

and so on.

The inverse function,

s = f^-1(y_i)

How can find the functions f and f^-1, the other constraint the character size cannot to be too large for these strings, say max 20-25 characters.

Any suggestions please ?

Answer 1

Ok, this will get too channel-coding specific if I do it in broadness, here, but:

These are mathematical concepts, so let's map strings to numbers and look at them algebraically:

Your 20-character string space, assuming we're just using the 128 common ASCII characters, has 2^{7 * 20} elements. That's pretty many elements.

However, communication technology has a method called scrambling which is a reversible process of mingling the bits in a sequence in a way that spreads the per-bit energy over the whole sequence. That leads to pretty randomly looking bit streams. It's typically implemented using feedback shift registers.

It's possible to find a 2¹⁴⁰ state LFSR that fulfills your scrambling needs, and you can interpret the output of a multiplicative scrambler as the next element in your sequence.

However, please be aware that your problem is a hard one, which I hope I've illustrated sufficiently -- getting something that has good random properties is a harsh thing, and I can't recommend implementing something like that yourself -- it's going to make problems as soon as you need to rely on mathematical properties of your pseudorandom string.