[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: your implementation of L'Ecuyer's MRG32k3a generator

This page is part of the web mail archives of SRFI 27 from before July 7th, 2015. The new archives for SRFI 27 contain all messages, not just those from before July 7th, 2015.

sebastian.egner@xxxxxxxxxxx writes:
> However, all this is speculation. It would be most interesting
> to hear of scientific results where people have tried Yarrow
> (or the like) on statistical tests related to simulation.

If you browse around on counterpane you should be able to find
something. Bruce Schneier is pretty well respected in the crypto field
and seems thorough in his analyses. That said, I'm basically a
crypto-dilettante so I'm not really qualified to judge.

> On the other hand: It would be nice to hear what crypto people
> would like the interface to the RNG to be. 

Cryppies tend to distinguish between sources of entropy (which PRNGs
most definitely are not) and bitstream-generators (which is what PRNGS
are). So if the interface works equally well for both types of
information that is good. In particular, there is a tendency to use
chaotic data derived from multiple OS internal data structures to
develop entropy bits. In Scheme terms, this means that the API must
not be problematic to implement on top of various FFI calls.

FWIW, the key factor for a crypto-quality PRNG is that it not "leak"
any information about the original seed: if you know some portion of
the generated bit-stream you'll have to perform an exhaustive search
in seed-space in order to discover the seed.

It turns out that there is a deterministic algorithm which can take a
bit-stream and determine a linear feedback shift register (aka LFSR)
of minimal size which will generate the stream. If the size in bits of
the LFSR turns out to require fewer bits than the seed, then the PRNG
algorithm is considered weak. AFAICT, from the US NIST standard
statistical test suite for PRNGs, LFSR PRNGs tend to be the strongest
overall anyway. If you're trying to evaluate PRNG quality, you owe it
to yourself just to read the documentation of the NIST suite.

> Your earlier proposal
> for a method to obtain a stream of bytes rather than range-limited
> integers with variable range is a start. I am still thinking on
> how to solve that one nicely.

I presume that you're trying to avoid more reduction in precision
(that's my terminology) resulting from additional range
reductions. Otherwise this doesn't seem that hard to me, but I may be
missing something.

david rush
Version 3.12
GCS d? s-: a C++$ ULSAH+++$ P+(---) L++ E+++ W+(--) N++ K w(---) O++@
PS+++(--) PE(++) Y+ PGP !tv b+++ DI++ D+(--) e*(+++>+++) h---- r+++