1

I'm trying to build a PRNG of bytes where I can take a set of bytes (say, 10 or 15 bytes) and return a list of seeds that would yield that list of bytes. I'm not concerned about cryptography, but it must be roughly uniformly distributed, it must hit all possible 2^8 combinations and it must occasionally be able to repeat a number without getting stuck.

The problem is, most algorithms I've read about either use ciphers, which probably means it won't allow repeats, or they use modulus or non-circular shifts that induce loss and make reversing the function impractical at best. Also, if the algorithm used counting, it would be hard to work backwards as the byte list input would not know what the internal PRNG's counter was at the generation time.

I realize what I'm looking for is a have-your-cake-and-eat-it-too situation, but I wanted to make sure there wasn't another solution I was missing.

While searching I came across this post which has similar requirements. I was writing in C# but really, syntax is not important.

Every algorithm I've tried to write myself has been a cipher and thus failed to repeat and/or not uniform in distribution. I used inversion, circular shifting and seed masking.

2
  • The post your referenced seems to answer your questions. Jan 11, 2012 at 2:19
  • The answers in that thread use ciphers, which, unless I'm missing something, would not allow for repeated output without getting stuck.
    – digdig
    Jan 11, 2012 at 15:58

2 Answers 2

1

Does this work?

#include <stdio.h>

int seed = 1;

int next() {
    seed = 1664525*seed + 1013904223;
    return (seed & 0xff) ^ (seed>>8 & 0xff) ^ (seed>>16 & 0xff) ^ (seed>>24 & 0xff);
}   

int main() {
    int i;
    for(i = 0; i < 1000; i++) {
        printf("%d\n", next());
    }   
}  

Since it is based on a linear congruential generator (LCG) with a full period, every byte will be generated by every seed, eventually. There seems to be repeats. And it inherits the uniformity of the underlying LCG.

1
  • The major problem I see with this is that the shifting induces loss by using only part of the seed, leaving millions of possible combinations. Unless I'm missing something, the conversion from seed to byte isn't invertible, but other than that I like it.
    – digdig
    Jan 16, 2012 at 22:31
0

My advisor has modified a PRNG (based on L'Ecuyer's clcg4) to be reversible to support our group's HPC simulation efforts. You can read about these here.

Basically, it "undoes" what has been done and, as you may have guessed, this may require "undoing" random number generation and then re-generating those same values again along a different path of computation. You can look at this code here and here. It's BSD-licensed code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.