[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.




Bengt,

> Presumably this is way to complex/slow, but there is a PRNG called Yarrow
> described in http://www.counterpane.com/yarrow-notes.html.
> It uses SHA1 and DES to generate bits.


Nice work you refer to!

If I understand correctly, the RNG used in Yarrow is just a block
cipher applied to the stream {0, 1, 2, ..}, occasionally changing
the secret key to a portion of its own output.

In how far this method of generating random bits is suitable to
applications outside cryptography, such as simulation, I cannot
say. For the purposes I deal with (randomization of algorithms)
it is most likely good enough and may be on the expensive side
with respect to running time because it essentially deals with
bit operations and not with arithmetic operations.

Yet, for simulation purposes it may still be the case that the
distribution properties of Yarrow are not as good as one might
think. That is not because the method is bad but because other
properties of the output are more important. It is known that
we can make streams look random by enforcing certain properties,
but only 'true randomness' can have them all at the same time!

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.

On the other hand: It would be nice to hear what crypto people
would like the interface to the RNG to be. 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.

In any case, thank you for the comment.

Sebastian.