Various seed sizes, how to seed?

90 views
Skip to first unread message

k.grocho...@gmail.com

unread,
Jun 24, 2019, 3:55:28 AM6/24/19
to prng
For example, using a 128-bit seed to seed xoshiro256**, what method would be used? or how about a 1024-bit seed, or an infinite seed? Obviously scaling SplitMix64 gets impractical due to 128-bit multiplications and such; a PRNG is slow if its seeding method is slow.

david.j...@gmail.com

unread,
Jun 25, 2019, 1:40:24 AM6/25/19
to prng
On Monday, 24 June 2019 17:55:28 UTC+10, k.groch...@gmail.com wrote:
> For example, using a 128-bit seed to seed xoshiro256**, what method would be used? or how about a 1024-bit seed, or an infinite seed?

The classic method is to use a hash function, something like MD5, to reduce the
big seed to something of fixed size. Doesn't have to be strictly secure, because xoshiro256** isn't secure, but use something fairly good.

>Obviously scaling SplitMix64 gets impractical due to 128-bit multiplications and such; a PRNG is slow if its seeding method is slow.

In most applications you generate a lot more times than you seed. A few microseconds is acceptable.

Mostly there's no reason to use large seeds. 128 bit maybe, but mostly 64 is enough. For crypto work (ie, not with xoshiro256) maybe you could stretch to 512 bit for some purposes. I don't think you want any bigger.

k.grocho...@gmail.com

unread,
Jul 3, 2019, 12:26:16 PM7/3/19
to prng

> > For example, using a 128-bit seed to seed xoshiro256**, what method would be used? or how about a 1024-bit seed, or an infinite seed?
>
> The classic method is to use a hash function, something like MD5, to reduce the
> big seed to something of fixed size. Doesn't have to be strictly secure, because xoshiro256** isn't secure, but use something fairly good.
Are you sure that would work? Isn't there possibly a chance that it will cause a zero seed to be generated?

>
> >Obviously scaling SplitMix64 gets impractical due to 128-bit multiplications and such; a PRNG is slow if its seeding method is slow.
>
> In most applications you generate a lot more times than you seed. A few microseconds is acceptable.

A few microseconds for a virtual "Loading..." screen in a simulation of a game of Tetris can be a problem. Seriously, consider analyzing the RNG on many seeds to determine its quality by testing it on a statistical test. The overhead (equivalent to a virtual "Loading..." screen in a simulation of a game of Tetris) causes issues. The safe option is always for the seeding function to be fast as well.

>
> Mostly there's no reason to use large seeds. 128 bit maybe, but mostly 64 is enough. For crypto work (ie, not with xoshiro256) maybe you could stretch to 512 bit for some purposes. I don't think you want any bigger.

But what if you actually have larger seeds and you need to use them and cannot use smaller seeds? The especially problematic case is for example using a 256-bit seed to generate a seed for xoshiro256**, because it requires a transformation from 2^256 possible values to 2^256-1.

Raimo Niskanen

unread,
Jul 4, 2019, 8:30:52 AM7/4/19
to prng
On Wed, Jul 3, 2019 at 6:26 PM <k.grocho...@gmail.com> wrote:
>
>
> > > For example, using a 128-bit seed to seed xoshiro256**, what method would be used? or how about a 1024-bit seed, or an infinite seed?
> >
> > The classic method is to use a hash function, something like MD5, to reduce the
> > big seed to something of fixed size. Doesn't have to be strictly secure, because xoshiro256** isn't secure, but use something fairly good.
> Are you sure that would work? Isn't there possibly a chance that it will cause a zero seed to be generated?

You only need enough many different seed values with equal probability.

So, for example, take MD5 and OR with 1. This ensures a nonzero seed
but halves the number of possible seeds, from 128 bits to 127 bits. It
must be hard to fathom an application where that is a problem.
It is also hard to fathom how low the probability to generate a 0 with
MD5 is. If you try as fast as you can i predict that there is a
vastly bigger probability that a bit rot in your hard drive or cosmic
radiation flipping a memory bit will fail your program before you find
an input that produces 0 with MD5.

>
> >
> > >Obviously scaling SplitMix64 gets impractical due to 128-bit multiplications and such; a PRNG is slow if its seeding method is slow.
> >
> > In most applications you generate a lot more times than you seed. A few microseconds is acceptable.
> A few microseconds for a virtual "Loading..." screen in a simulation of a game of Tetris can be a problem. Seriously, consider analyzing the RNG on many seeds to determine its quality by testing it on a statistical test. The overhead (equivalent to a virtual "Loading..." screen in a simulation of a game of Tetris) causes issues. The safe option is always for the seeding function to be fast as well.

One example was bad: When analyzing the statistical properties of a
PRNG you generate an incredibly large amount of numbers from every
seed.

I think that a longer seed time than state update is very rarely a
problem, but one that has to be looked at for the particular
application. These PRNGs are designed for extremely fast state
update. To find a different kind of function that generates a seed as
fast will be hard. Except for the existing tip to use a different
class of PRNG to create the seed.

SplitMix64 can generate 2^64 different seed values. Even for a 512
bit state generator that might be enough. The application
requirements determines this.

This might be a use case for the jump function in this class of
generators. Seed once. For every new instance make a jump and copy
the new state to a new generator. The seeded generator is only used
to create start states for the simulation generators. This guarantees
that no simulation generator gets into a number sequence of any other
simulation generator.
A jump is much slower than a state advance, though...

>
> >
> > Mostly there's no reason to use large seeds. 128 bit maybe, but mostly 64 is enough. For crypto work (ie, not with xoshiro256) maybe you could stretch to 512 bit for some purposes. I don't think you want any bigger.
>
> But what if you actually have larger seeds and you need to use them and cannot use smaller seeds? The especially problematic case is for example using a 256-bit seed to generate a seed for xoshiro256**, because it requires a transformation from 2^256 possible values to 2^256-1.

I do not think you need 2^256 different seed values; 2^255 should be
sufficient for any application. OR with 1 or ignore the probability
of a zero seed. It will not happen. Or write a loop that re-seeds
for zero seed. It will never be executed more than once. Not before
the thermal death of the universe.

You only need enough many seed values with equal probability to not
collide with another seed value, with a certain probability.
If you generate 2^64 128 bit seeds; according to the birthday paradox
the probability that two of those seeds are equal is about
fifty-fifty. How long will the application run before having
generated 2^64 seeds? Are all 2^64 previously generated seeds still
relevant to not collide with? The collision resistance requirements
are application dependent.

Best Regards
--
Raimo Niskanen
Reply all
Reply to author
Forward
0 new messages