Re: new coreutil? shuffle - randomize file contents

[Frederik Eaton]

> Frederik Eaton <address@hidden> writes:
> 
> > On Thu, Jun 02, 2005 at 11:31:26PM -0700, Paul Eggert wrote:
> >> Suppose you're randomizing an input file of 10 million lines.  And
> >> suppose you want to approximate a "truly random" key by using a
> >> 128-bit random key for each input line.
> >> 
> >> Then you'll need about 1.3 billion random bits. 
> >
> > No! Please see my penultimate email. This is what random seeds are
> > for.
> 
> Sorry, I didn't follow your penultimate email.  But my admittedly
> limited understanding of it suggested that you're thinking mostly of
> collaborative applications (e.g., shuffling a CD play list) where I am
> thinking also of adversarial applications (e.g., shuffling a card deck
> for high-stakes poker).  To a first approximation, a pseudorandom
> generator is fine for the first application, but questionable for the
> second one.
> 
> As a practical matter I'm sure the 1.3 billion random bits is overkill
> for sorting 10 million records.  But it's not at all clear to me how
> many bits are adequate for all real-world applications.  Apparently
> even the experts in this field don't always agree on that point; see,
> e.g. <http://www.maa.org/mathland/mathtrek_10_16_00.html>.

How about this: Put an upper limit on the number of samples that your
adversary will be able to try before the earth blows up. Take the
logarithm to base 2. 100 is larger than this number. Therefore 100
bits of seed - pulled by default, say, from /dev/random - will do.

Frederik