Looking for a small pseudo random generator with good equidistribitions properties
Marc Battyani
I'm looking for a small pseudo random generator with good equidistribitions
properties at least up to dimension 1000 or more.
MT is only good up to 623 for instance, and takes too much data for its
state for my needs. The WELL series has some big generators but with an even
bigger state.
I would like to use something like KISS (the shift only version) but I'm not
sure about its equidistribution properties.
Also, as this will run on some hardware where I can't use a multiplier, and
without much memory, I would prefer one based only on shift, add, xor, etc.
Any pointer to a suitable PRNG?
A last question, is is safe to contatenate two independent 32 bits random
generators to make a 64 bits one?
Thanks,
Marc
Peter Pearson
> I'm looking for a small pseudo random generator with good equidistribitions
> properties at least up to dimension 1000 or more.
If you base your PRNG on a respectable block cipher,
equidistribution failure at any dimension up to 1000 (or
more) would be a publishable result, so . . . you couldn't
lose!
[snip]
> Also, as this will run on some hardware where I can't use a multiplier, and
> without much memory, I would prefer one based only on shift, add, xor, etc.
I believe the AES block cipher fits this description, although
if you're over 45 years old the "without much memory" will
probably be a problem. (The meaning of "without much memory"
varies over several orders of magnitude, depending on the age of the
speaker.)
> A last question, is is safe to contatenate two independent 32 bits random
> generators to make a 64 bits one?
If the independent generators are crypto-quality, then yes. On the
other hand, if you use AES, you'll get your random bits in 128-bit
blocks.
--
To email me, substitute nowhere->spamcop, invalid->net.
John E. Hadstate
"Marc Battyani" <Marc.B...@fractalconcept.com> wrote in
message news:xoqdnW4PwIq...@giganews.com...
>
> I'm looking for a small pseudo random generator with good
> equidistribitions properties at least up to dimension 1000
> or more.
>
> Also, as this will run on some hardware where I can't use
> a multiplier, and without much memory, I would prefer one
> based only on shift, add, xor, etc.
>
> Any pointer to a suitable PRNG?
>
George Marsaglia "Xorshift RNGs":
http://www.jstatsoft.org/v08/i14/paper
You'll find ready-made, fast, high-quality 32 and 64 bit
PRNGs that I'm sure will meet your needs. Just don't use
them for crypto.
Marc Battyani
"John E. Hadstate" <jh11...@hotmail.com> wrote
>
> "Marc Battyani" <Marc.B...@fractalconcept.com> wrote
>>
>> I'm looking for a small pseudo random generator with good
>> equidistribitions properties at least up to dimension 1000 or more.
>>
>> Also, as this will run on some hardware where I can't use a multiplier,
>> and without much memory, I would prefer one based only on shift, add,
>> xor, etc.
>>
>> Any pointer to a suitable PRNG?
>>
>
> George Marsaglia "Xorshift RNGs":
>
> http://www.jstatsoft.org/v08/i14/paper
>
> You'll find ready-made, fast, high-quality 32 and 64 bit PRNGs that I'm
> sure will meet your needs. Just don't use them for crypto.
It seems that they have no good equidistribution properties according to
this paper:
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
Looks like xorgens might be better:
http://wwwmaths.anu.edu.au/~brent/pd/rpb224.pdf
Having a true equidistribution is not possible with a not too big PRNG state
but what I want to avoid is to have points clustered in planes or
hyper-planes in higher dimensions.
Marc
Marc Battyani
"Peter Pearson" <ppea...@nowhere.invalid> wrote
> On Wed, 14 Nov 2007 00:36:17 +0100, Marc Battyani wrote:
>
>> I'm looking for a small pseudo random generator with good
>> equidistribitions
>> properties at least up to dimension 1000 or more.
>
> If you base your PRNG on a respectable block cipher,
> equidistribution failure at any dimension up to 1000 (or
> more) would be a publishable result, so . . . you couldn't
> lose!
>
> [snip]
>> Also, as this will run on some hardware where I can't use a multiplier,
>> and
>> without much memory, I would prefer one based only on shift, add, xor,
>> etc.
>
> I believe the AES block cipher fits this description, although
> if you're over 45 years old the "without much memory" will
> probably be a problem. (The meaning of "without much memory"
> varies over several orders of magnitude, depending on the age of the
> speaker.)
Hehe... I'm not 45 yet but close enough that your argument holds (IIRC my
first computer had 1024 bytes of memory)
So yes AES would be very good but it's too slow/too big and I indeed count
my memory in bytes. :)
>> A last question, is is safe to contatenate two independent 32 bits random
>> generators to make a 64 bits one?
>
> If the independent generators are crypto-quality, then yes. On the
> other hand, if you use AES, you'll get your random bits in 128-bit
> blocks.
ok.
Marc
Cristiano
> So yes AES would be very good but it's too slow/too big and I indeed
> count my memory in bytes. :)
Then use RC5 with a small number of rounds (3 or 4) and with a short key; it
will be very good and reasonably fast.
Cristiano
Cristiano
> It seems that they have no good equidistribution properties according
> to this paper:
> http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
>
> Looks like xorgens might be better:
> http://wwwmaths.anu.edu.au/~brent/pd/rpb224.pdf
They both fail some tests at moderately high dimensions and don't meet your
requirements.
> Having a true equidistribution is not possible with a not too big
> PRNG state but what I want to avoid is to have points clustered in
> planes or hyper-planes in higher dimensions.
I think RC5 in CTR mode should be very good for you.
Cristiano
Marc Battyani
"Cristiano" <cristi...@NSquipo.it> wrote
Thanks, RC5 look very well suited indeed.
To use a counter mode to generate random numbers, I have to use only a part
of the output bits otherwise I can't get any number a second time in the
stream? Or is it worthless for any practical purpose?
BTW it's patented though. Are there some unpatented alternatives?
Marc
Cristiano
The output is 2 32-bit numbers; you can XOR the counter with output[0] for
the 1st 32-bit number, with output[1] for the 2nd 32-bit number, with
output[0] for the 3rd 32-bit number and so on.
> BTW it's patented though. Are there some unpatented alternatives?
Yes, I wrote this:
static unsigned long A=__rdtsc(),B=time(0),y=A+B;
for(int i=0; i<5; i++) {
y=y*2147001325L+715136305L;
A=rotl(A^B,B)+y; B=rotl(B^A,A)+y;
}
return A^B;
it is reasonably fast and pass all the tests I have. It pass any test also
with:
for(int i=0; i<3; i++)
Cristiano
Thomas Pornin
> Thanks, RC5 look very well suited indeed.
> To use a counter mode to generate random numbers, I have to use only a part
> of the output bits otherwise I can't get any number a second time in the
> stream? Or is it worthless for any practical purpose?
To get really good random when applying counter mode, you should use a
block cipher with a big enough block size to make the question
irrelevant. For instance, if you use a 128-bit block cipher, the fact
that a given number does not repeat in the stream is not noticeable
until a few billions of gigabytes have been generated. With a 64-bit
block cipher such as RC5, you get into trouble (i.e. detectable bias)
after about 2^32 blocks (that's 32 gigabytes). Depending on your
application, this may or may not be a problem.
Other than block ciphers used with counter mode, there are other
encryption primitives called "stream ciphers" which are _not_ as
versatile as block ciphers, but which are optimized for what you look
for (namely, generating pseudo-random bytes) and conceptually quite
faster. The most well-known is RC4 (also called "Arcfour" because the
name "RC4" is a trademark -- but the algorithm itself is not patented).
It is quite fast on software platforms (including 8-bit processors),
very easy to implement, and widely used. Unfortunately, it has a number
of cryptographic weaknesses, including some biases which allow an
attacker to distinguish RC4 from a pure random source with as low as one
gigabyte of output. There again, depending on your application, this may
or may not be a problem. A description of RC4 is available there:
http://em.wikipedia.org/wiki/RC4
Although RC4 is already faster than what you would get with AES, there
are better and faster algorithms, with no known bias. The eSTREAM
project has gathered a number of such algorithms; see:
http://www.ecrypt.eu.org/stream/
Intellectual property status is specified for all candidates and most
of them are free for any use; besides, source code is provided.
--Thomas Pornin
Marc Battyani
"Cristiano" <cristi...@NSquipo.it> wrote
> Marc Battyani wrote:
[...]
>>> I think RC5 in CTR mode should be very good for you.
>> BTW it's patented though. Are there some unpatented alternatives?
>
> Yes, I wrote this:
>
> static unsigned long A=__rdtsc(),B=time(0),y=A+B;
> for(int i=0; i<5; i++) {
> y=y*2147001325L+715136305L;
> A=rotl(A^B,B)+y; B=rotl(B^A,A)+y;
> }
> return A^B;
>
> it is reasonably fast and pass all the tests I have. It pass any test also
> with:
> for(int i=0; i<3; i++)
Thanks. I will look at this.
Are there some constraints for the value of y or is any low quality sequence
generator ok?
Did you test this with the random numbers test suites like TestU01 ?
Marc
Marc Battyani
"Thomas Pornin" <por...@bolet.org> wrote
Thanks for the information, this seems very interesting.
Marc
Cristiano
> "Cristiano" <cristi...@NSquipo.it> wrote
>> Marc Battyani wrote:
>>> "Cristiano" <cristi...@NSquipo.it> wrote
> [...]
>>>> I think RC5 in CTR mode should be very good for you.
> [...]
>>> BTW it's patented though. Are there some unpatented alternatives?
>>
>> Yes, I wrote this:
>>
>> static unsigned long A=__rdtsc(),B=time(0),y=A+B;
>> for(int i=0; i<5; i++) {
>> y=y*2147001325L+715136305L;
>> A=rotl(A^B,B)+y; B=rotl(B^A,A)+y;
>> }
>> return A^B;
>>
>> it is reasonably fast and pass all the tests I have. It pass any
>> test also with:
>> for(int i=0; i<3; i++)
>
> Thanks. I will look at this.
> Are there some constraints for the value of y or is any low quality
> sequence generator ok?
I used a counter for A and B=A (the "worst case" initialization) and the
output sequence passed all the tests even with "for(int i=0; i<3; i++)".
I always use y=A+B, but I think that any y should be good (you have 96 bits
of seeding space).
> Did you test this with the random numbers test suites like TestU01 ?
I use an improved version of RaBiGeTe:
http://www.webalice.it/cristiano.pi/rabigete/
Cristiano
Cristiano
> Thanks for the information, this seems very interesting.
If you think that the state of the RC5 is small, you could be interested in
RC6.
Cristiano
Cristiano
> Marc Battyani wrote:
>> It seems that they have no good equidistribution properties according
>> to this paper:
>> http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
>>
>> Looks like xorgens might be better:
>> http://wwwmaths.anu.edu.au/~brent/pd/rpb224.pdf
>
> They both fail some tests at moderately high dimensions and don't
> meet your requirements.
I was wrong, sorry. xorgens perform very well (I tested the version with
n=4096).
Cristiano