Re: BBC BASIC's RND Function



In message <a96349324f.tigger@xxxxxxxxxxxxxxxxxxxxxxxxxx>
Nick Roberts <tigger@xxxxxxxxxxxxxxxxxxxxx> wrote:

In message <yGt*rUjXr@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
Theo Markettos <theom+news@xxxxxxxxxxxxxxxxxxxxxx> wrote:

Seeding the random number generator is a good way to produce longer
sequences, but remember the entropy in the system is still the 32 bit
random seed. If you're using this to generate crypto keys, for
example, that means you only have 2^32 possible keys because you only
have 2^32 seeds (and the rest of the process is deterministic) - and
a 32 bit key is trivial to brute-force these days. Hence the need
for more entropy in the system.

One thing that has been missed in this thread is the purpose for which
the stream is needed.

Not at all, we have been discussing the all important task of
shuffling cards, which turned out to be surprisingly difficult. :-)

If the only requirement is a much longer cycle length than RND (while
retaining the ability to guarantee repeatability by seeding it), then
it shouldn't take much ingenuity to implement a BASIC version of the
Mersenne Twister (cycle length 2^19937 - 1), which is pretty fast[1]
for a generator of such cycle length.

The standard implementation of MT 19937 has a 32-bit seed, so we are
back to a maximum of 2^32 different arrangements of the cards, no
matter how big the cycle length is. :-( In fact, the cycle length is
not really that important for this particular application. It is
important in that it limits the starting entropy because you cannot
have more different seed values than the length of the cycle. Unless
you have at least 226 bits of entropy to start with (i.e., in the
seed) it is impossible to achieve all permutations of a pack of 52
cards.

It should be possible to create MTs with larger word lengths but then,
I suppose that speed will suffer.

Martin
--
---------------------------------------------------------------------
Martin Wuerthner MW Software http://www.mw-software.com/
ArtWorks 2 -- Designing stunning graphics has never been easier
spamtrap@xxxxxxxxxxxxxxx [replace "spamtrap" by "info" to reply]
.



Relevant Pages

  • Re: Fortuna
    ... Waiting for 256bits of entropy before outputting data is a good goal. ... As for the "shifting property" problem of an attacker controlling some input ... pool to aggravate the predictability of where entropy goes. ... > Because of the shifting property, an attacker who knows the seeds added ...
    (Linux-Kernel)
  • Re: Random Seeding
    ... provided by it's inventors allows for longer seeds. ... Because Entropy is typically slow/expensive to obtain, while PRNGs are ... Its actually kind of curious -- CPU manufacturers have actually been ...
    (comp.lang.c)
  • Re: Generating random seeds for simulation
    ... convinced that it will still result in much different seeds if the ... void randomize { ... So we are taking 3 sources of entropy, time, clockand a simple ... RDTSC on Intel platforms, etc. ...
    (comp.lang.c)
  • Re: Generate Random number
    ... You can also seed from the kernel RNG /dev/urandom (or if you don't ... mind waiting for entropy, /dev/random). ... This is particularly handy if ... the seeds are longer than 32 bits. ...
    (comp.unix.programmer)
  • Re: Card dealing and random repetition
    ... the PRNG stores more state than it shows the user in its output. ... No, the length can be no more than the number of seeds; ... >>> in the order they landed on the table, then shuffle them as usual. ... the important issue is how many cards are visible (or ...
    (comp.programming)