1
$\begingroup$

Question

Say I have access to a relatively large (but not huge) amount of truly random data, D, like 100 KiB of random bits from a hardware randomness source (just assume that it is larger than the seed or internal state of a typical PRNG).

How can I make the most of D to improve the quality of an unbounded number of pseudo-random samples, by doing more than just seeding it from some parts of D and discarding the rest?

An answer could either show a method to enhance an arbitrary pseudo-random sequence using D, or modify or combine existing algorithms.

My ideas

One possibility I found was to just add the data to the entropy pool of dev/random. However, that assumes dev/random to exist on a system, which does not hold everywhere. Also, I understand that it blocks when the available "entopy" is too small, which is not the kind of behaviour I'm after. But if I'm mistaken, a description of its approach (which I don't understand) would be a valid answer.

Another thing that came to my mind was to just treat D as a BigInteger and run a regular PRNG algorithm on it, "chunking" down the outputs to word size again. I don't know enough about the implemention of PRNGs to assess the feasibility of this, but I guess there will be performance hits due to all the prevented optimizations.

Or should I just seed as many instances of one PRNG as I can using D, and cycle through them? This might have huge constant memory overhead.

More details about my assumptions

  • By "not huge", I mean that I cannot be sure that the amount of data would suffice to just reinterpret little bits of it directly for each rand call that will happen, and it fits into memory without unreasonably penalties.
  • I don't actually have a real use case -- this question just came across my mind. It is actually a more theoretical thought; I guess adding D wouldn't improve a Monte Carlo algorithm very much in reality.
$\endgroup$
0
$\begingroup$

I found some code in the simplerandom library that does this. The proper term seems to be mixing. Essentially, you just go through the data, XOR the PRNG state with it (taking into account peculiarities of the particular representation), and advance one step. For example:

void simplerandom_shr3_mix(SimpleRandomSHR3_t * p_shr3, const uint32_t * p_data, size_t num_data)
{
    if (p_data != NULL)
    {
        while (num_data)
        {
            --num_data;
            p_shr3->shr3 ^= *p_data++;
            simplerandom_shr3_sanitize(p_shr3);
            simplerandom_shr3_next(p_shr3);
        }
    }
}

Of course this can only work when you have a reasonably small state, not something like a several hundred bytes long Mersenne Twister.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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