Re: new coreutil? shuffle - randomize file contents

[James Youngman]

On Thu, Jun 02, 2005 at 11:31:26PM -0700, Paul Eggert wrote:

> Then you'll need about 1.3 billion random bits.  On my desktop,
> /dev/random generates only about 200 random bits per second, and
> it'll take me about 2.5 months to randomize the file.

But /dev/random is constrained by the rate of arrival of its source
"random" events.  We probably wouldn't want a sort program whose rate
of progress depended on how quickly the user (if any) types on the
keyboard and wiggles the mouse, for example.  On the other hand, this
is more the sort of thing that /dev/urandom was invented for.  While
/dev/random produces allegedly random bits, /dev/urandom falls back on
a pseudo-random source which is "stirred" with the incoming random
events.

>From Ted Ts'o's comments in the Linux kernel:

 * The two other interfaces are two character devices /dev/random and
 * /dev/urandom.  /dev/random is suitable for use when very high
 * quality randomness is desired (for example, for key generation or
 * one-time pads), as it will only return a maximum of the number of
 * bits of randomness (as estimated by the random number generator)
 * contained in the entropy pool.
 * 
 * The /dev/urandom device does not have this limit, and will return
 * as many bytes as are requested.  As more and more random bytes are
 * requested without giving time for the entropy pool to recharge,
 * this will result in random numbers that are merely cryptographically
 * strong.  For many applications, however, this is acceptable.

I can get about 34 million random bits per second out of /dev/urandom
on my desktop machine.  That implies that 1.3 billion pseud-random
bits could be generated in less than 40 seconds.

I'm pretty sure that most uses of the shuffling functionality would
accept a pseudo-random ordering, which is just as well since
/dev/random and /dev/urandom are only available on some systems; we're
likely in general to have to use some form of PRNG.

Regards,
James Youngman.