Trying to write an invertible PRNG of 8 bits, not a cipher

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.

---

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("%dn", 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.

---

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.

链接地址: http://www.djcxy.com/p/37266.html

上一篇: 测试PRNG的质量

下一篇: 试图写一个8位可逆PRNG，而不是密码