new PRNG's

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|

new PRNG's

Albert Chan
Xorshift PRNG's had been removed from http://xoshiro.di.unimi.it

Instead, Vigna have some newer (better?) PRNG's
Seems all of them uses bits rotation.

https://groups.google.com/forum/m/#!topic/prng/ytEzece0_tI

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Albert Chan
Reading Vigna latest xoshiro paper (section 11, conclusion),
next version of Lua will use xoshiro256** for math.random.

Is it true ?
Lua 5.4 ?

http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

KHMan
On 5/5/2018 12:08 PM, Albert Chan wrote:
> Reading Vigna latest xoshiro paper (section 11, conclusion),
> next version of Lua will use xoshiro256** for math.random.
>
> Is it true ?
> Lua 5.4 ?
>
> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf

IMHO, math.random is similar in purpose to C standard library's
random function. It's pseudo-random, that's about it. It does not
promise any quality specifications.

Are there serious flaws that disqualifies the current
implementation from this purpose?

Is there a requirement for cryptographic-quality randomness? Is
that a good idea? For what applications? If for crypto/security,
is it normal for a base programming language library to embrace
such capabilities? Shouldn't we use well-established libraries
instead? If we crunch crypto in pure Lua, wouldn't a timing attack
be easy?

I just don't see the point of this topic going on and on and on.

--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Dirk Laurie-2
2018-05-05 9:23 GMT+02:00 KHMan <[hidden email]>:

> On 5/5/2018 12:08 PM, Albert Chan wrote:
>>
>> Reading Vigna latest xoshiro paper (section 11, conclusion),
>> next version of Lua will use xoshiro256** for math.random.
>>
>> Is it true ?
>> Lua 5.4 ?
>>
>> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
>
>
> IMHO, math.random is similar in purpose to C standard library's random
> function. It's pseudo-random, that's about it. It does not promise any
> quality specifications.
>
> Are there serious flaws that disqualifies the current implementation from
> this purpose?
>
> Is there a requirement for cryptographic-quality randomness? Is that a good
> idea? For what applications? If for crypto/security, is it normal for a base
> programming language library to embrace such capabilities? Shouldn't we use
> well-established libraries instead? If we crunch crypto in pure Lua,
> wouldn't a timing attack be easy?
>
> I just don't see the point of this topic going on and on and on.

+1.

A language whose standard math library has been stripped of functions
available on any scientific calculator (viz. asinh, acosh, atanh) dare
make no pretence of up-to-the minute standards for mathematical
software.

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Albert Chan
In reply to this post by KHMan

On May 5, 2018, at 3:23 AM, KHMan <[hidden email]> wrote:

On 5/5/2018 12:08 PM, Albert Chan wrote:
Reading Vigna latest xoshiro paper (section 11, conclusion),
next version of Lua will use xoshiro256** for math.random.
Is it true ?
Lua 5.4 ?
http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf

IMHO, math.random is similar in purpose to C standard library's random function. It's pseudo-random, that's about it. It does not promise any quality specifications.

Are there serious flaws that disqualifies the current implementation from this purpose?

I just want to check if Vigna's claim is correct.
It would be bad if he just use Lua to promote xoshiro256**

This is from his xoshiro paper, conclusion (section 11)

The combination of xoroshiro/xoshiro and suitable scramblers provides a wide range of high- quality and fast solutions for pseudorandom number generation. Parallax has embedded xoroshiro128** and xoroshiro32++ in their recently designed Propeller 2 microcontroller; xoroshiro116+ is the stock generator of Erlang, and the next version of the popular embedded language Lua will sport xoshiro256** as stock generator. 


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

KHMan
On 5/5/2018 7:28 PM, Albert Chan wrote:

>
> On May 5, 2018, at 3:23 AM, KHMan wrote:
>
>> On 5/5/2018 12:08 PM, Albert Chan wrote:
>>> Reading Vigna latest xoshiro paper (section 11, conclusion),
>>> next version of Lua will use xoshiro256** for math.random.
>>> Is it true ?
>>> Lua 5.4 ?
>>> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
>>
>> IMHO, math.random is similar in purpose to C standard library's
>> random function. It's pseudo-random, that's about it. It does
>> not promise any quality specifications.
>>
>> Are there serious flaws that disqualifies the current
>> implementation from this purpose?
>
> I just want to check if Vigna's claim is correct.
> It would be bad if he just use Lua to promote xoshiro256**
>
> This is from his xoshiro paper, conclusion (section 11)
> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
>
> The combination of xoroshiro/xoshiro and suitable scramblers
> provides a wide range of high- quality and fast solutions for
> pseudorandom number generation. Parallax has embedded
> xoroshiro128** and xoroshiro32++ in their recently designed
> Propeller 2 microcontroller; xoroshiro116+ is the stock generator
> of Erlang, and the next version of the popular embedded language
> Lua will sport xoshiro256** as stock generator.

Personal opinion: Sounds like cheerleading to me. Don't bet your
life savings on it. :-) :-p


--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia



Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Roberto Ierusalimschy
In reply to this post by KHMan
> >Is it true ?
> >Lua 5.4 ?
> >
> >http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf

That is our plan.


> IMHO, math.random is similar in purpose to C standard library's
> random function. It's pseudo-random, that's about it. It does not
> promise any quality specifications.
>
> Are there serious flaws that disqualifies the current implementation
> from this purpose?

Yes. First, it is not portable. The C standard library 'rand' is so bad
that POSIX has another one. Lua uses that other one in POSIX systems,
but not in other platforms. That is, in some non-POSIX platforms
math.random can be really bad. Second, it does not generate 64-bit
numbers, which is strange now that Lua has 64-bit integers as its "main"
numeric type. (It is also a little weird that random floats do not have
all bits random. Someone complained about that not so long ago on the
list.)


> Is there a requirement for cryptographic-quality randomness? Is that
> a good idea? For what applications? If for crypto/security, is it
> normal for a base programming language library to embrace such
> capabilities? Shouldn't we use well-established libraries instead?
> If we crunch crypto in pure Lua, wouldn't a timing attack be easy?

There is no requirement at all for cryptographic-quality randomness,
quite the opposite. We will not announce it as such and will not
argue about it. We chose that algorithm because it has a very simple
implementation and good statistical (from a "pseudo-randomness" point
of view) quality. It is hard to get much simpler than that:

static Rand64 nextrand (Rand64 *state) {
  Rand64 res = rotl(state[1] * 5, 7) * 9;
  Rand64 t = state[1] << 17;
  state[2] ^= state[0];
  state[3] ^= state[1];
  state[1] ^= state[2];
  state[0] ^= state[3];
  state[2] ^= t;
  state[3] = rotl(state[3], 45);
  return res;
}


> I just don't see the point of this topic going on and on and on.

We also don't see the point.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

KHMan
On 5/7/2018 12:27 AM, Roberto Ierusalimschy wrote:

>>> Is it true ?
>>> Lua 5.4 ?
>>>
>>> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
>
> That is our plan.
>
>
>> IMHO, math.random is similar in purpose to C standard library's
>> random function. It's pseudo-random, that's about it. It does not
>> promise any quality specifications.

My apologies for the ambiguity here and there. The likelihood is
that I was not oblivious to the Lua 5.4.0 work1 discussion and
here I was not trying to say that Lua should still use C stdlib's
random function or anything like that. I was trying to make a
connection between Lua's math.random and C standard library's
random function in terms of what is offered, which is not much and
nothing very specific.

So if anyone was planning to _rely_ on certain quality
characteristics that happened to be present in the upcoming
implementation (but is not actually guaranteed), then they'd
better be very careful about doing so.

By "the current implementation" below I meant what was presented
in the ongoing discussion. Poor writing/editing that.


>> Are there serious flaws that disqualifies the current implementation
>> from this purpose?
>
> Yes. First, it is not portable. The C standard library 'rand' is so bad
> that POSIX has another one. Lua uses that other one in POSIX systems,
> but not in other platforms. That is, in some non-POSIX platforms
> math.random can be really bad. Second, it does not generate 64-bit
> numbers, which is strange now that Lua has 64-bit integers as its "main"
> numeric type. (It is also a little weird that random floats do not have
> all bits random. Someone complained about that not so long ago on the
> list.)
[snip snip snip]

--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia



Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Albert Chan
In reply to this post by Roberto Ierusalimschy
On May 6, 2018, at 12:27 PM, Roberto Ierusalimschy <[hidden email]> wrote:

>>> Is it true ?
>>> Lua 5.4 ?
>>>
>>> http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf
>
> That is our plan

Xoshiro256** is VERY new PRNG

This is the only blog I found:

http://www.pcg-random.org/posts/a-quick-look-at-xoshiro256.html



Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Roberto Ierusalimschy
In reply to this post by KHMan
> By "the current implementation" below I meant what was presented in
> the ongoing discussion. Poor writing/editing that.
>
>
> >>Are there serious flaws that disqualifies the current implementation
> >>from this purpose?

If I understood your last message correctly, you are asking why
to change from xorshift128plus to xoshiro256**. xorshift128plus
does not have any serious (or non-serious) flaws for our purpose,
despite what some pundits may say. Nevertheless, some pundits will
complain about xorshift128plus (they already did), which generates
noise (e.g., "avoid the lower bits"). The implementation of xoshiro256**
is basically as simple as xorshift128plus, and avoids the noise.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

KHMan
On 5/7/2018 5:00 AM, Roberto Ierusalimschy wrote:

>> By "the current implementation" below I meant what was presented in
>> the ongoing discussion. Poor writing/editing that.
>>
>>
>>>> Are there serious flaws that disqualifies the current implementation
>>> >from this purpose?
>
> If I understood your last message correctly, you are asking why
> to change from xorshift128plus to xoshiro256**. xorshift128plus
> does not have any serious (or non-serious) flaws for our purpose,
> despite what some pundits may say. Nevertheless, some pundits will
> complain about xorshift128plus (they already did), which generates
> noise (e.g., "avoid the lower bits"). The implementation of xoshiro256**
> is basically as simple as xorshift128plus, and avoids the noise.

Yes, that is more or less correct. I was too brief.

By math.random's intent, any number of good PRNGs should qualify.
But if some new paper pops up from security researchers detailing
a flaw or weakness in one of the PRNGs being discussed, then it
ought to be brought to attention by the community.

Absent such flaws, one or more PRNGs qualifies, and one would
presumably be chosen at the pleasure of Team Lua. A focus on the
output quality in terms of crypto randomness tests may extend too
far into quality concerns that is not specified by math.random. A
pursuit of the 'bestest' implementation by the community here is
laudable, but it seems a little like a pursuit of perfection that
can be grasped only fleetingly.

What is the perfect choice for today may change in the future.
Security research will progress and a few years down the line, who
knows what may turn up. Weak keys, exploits, better algos, etc.

(Many things that need really high-quality random numbers may not
need PRNGs that much these days. E.g. about all IoT chips with
crypto hardware will feature a true random number generator.)

--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Roberto Ierusalimschy
> Absent such flaws, one or more PRNGs qualifies, and one would
> presumably be chosen at the pleasure of Team Lua. A focus on the
> output quality in terms of crypto randomness tests may extend too
> far into quality concerns that is not specified by math.random. A
> pursuit of the 'bestest' implementation by the community here is
> laudable, but it seems a little like a pursuit of perfection that
> can be grasped only fleetingly.
>
> What is the perfect choice for today may change in the future.
> Security research will progress and a few years down the line, who
> knows what may turn up. Weak keys, exploits, better algos, etc.
>
> (Many things that need really high-quality random numbers may not
> need PRNGs that much these days. E.g. about all IoT chips with
> crypto hardware will feature a true random number generator.)

The problem seems to be that you are viewing the base case as
xorshift128plus, while we see the base case as 'rand'/'random'.

What is present today in the latest release of Lua is 'rand'/'random',
not xorshift128plus. xorshift128plus went only into a working version.
If we see the base case as 'rand'/'random', which is what Lua
programmers have now, I guess we agree that it is a good idea to
change. If we are going to change, and there are competing options 1 and
2 where 2 is slightly better than 1, why to change to 1?

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Albert Chan
> What is present today in the latest release of Lua is 'rand'/'random',
> not xorshift128plus. xorshift128plus went only into a working version.
> If we see the base case as 'rand'/'random', which is what Lua
> programmers have now, I guess we agree that it is a good idea to
> change. If we are going to change, and there are competing options 1 and
> 2 where 2 is slightly better than 1, why to change to 1?
>
> -- Roberto
>

+1

As noted on the first post of this thread, Xorshift128+ had been
REMOVED from Vigna's site (i.e. NOT recommended anymore)

So, option 1 is off the table.


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

KHMan
In reply to this post by Roberto Ierusalimschy
On 5/7/2018 9:19 PM, Roberto Ierusalimschy wrote:

>> Absent such flaws, one or more PRNGs qualifies, and one would
>> presumably be chosen at the pleasure of Team Lua. A focus on the
>> output quality in terms of crypto randomness tests may extend too
>> far into quality concerns that is not specified by math.random. A
>> pursuit of the 'bestest' implementation by the community here is
>> laudable, but it seems a little like a pursuit of perfection that
>> can be grasped only fleetingly.
>>
>> What is the perfect choice for today may change in the future.
>> Security research will progress and a few years down the line, who
>> knows what may turn up. Weak keys, exploits, better algos, etc.
>>
>> (Many things that need really high-quality random numbers may not
>> need PRNGs that much these days. E.g. about all IoT chips with
>> crypto hardware will feature a true random number generator.)
>
> The problem seems to be that you are viewing the base case as
> xorshift128plus, while we see the base case as 'rand'/'random'.
>
> What is present today in the latest release of Lua is 'rand'/'random',
> not xorshift128plus. xorshift128plus went only into a working version.
> If we see the base case as 'rand'/'random', which is what Lua
> programmers have now, I guess we agree that it is a good idea to
> change. If we are going to change, and there are competing options 1 and
> 2 where 2 is slightly better than 1, why to change to 1?

There is no problem, only a minor impedance matching issue in
communications. All is good. :-) :-P


--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

GrayFace-2
In reply to this post by Roberto Ierusalimschy
On Пн 07.05.18 20:19, Roberto Ierusalimschy wrote:
> What is present today in the latest release of Lua is 'rand'/'random',
> not xorshift128plus.

What about LuaJIT's PRNG? Having the same PRNG would be good for
compatibility.
"LuaJIT uses a Tausworthe PRNG with period 2^223 to implement
math.random() and math.randomseed()."


Best regards,
Sergey "GrayFace" Rozhenko,                 mailto:[hidden email]


Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Albert Chan

> On May 8, 2018, at 5:06 AM, Sergey Rozhenko <[hidden email]> wrote:
> What about LuaJIT's PRNG? Having the same PRNG would be good for compatibility.

Compatibility with LuaJIT ?
Should it be the other way around ?

> "LuaJIT uses a Tausworthe PRNG with period 2^223 to implement math.random() and math.randomseed()."

Tausworthe PRNG is old (1991), and will fail linearity test.
(It look like xorshift+ without the plus "scrambler")

LuaJIT's implementation also have problem with range bias.
(It just use 52 bit random float to calculate math.random(n,m))

https://github.com/aerospike/luajit/blob/master/src/lib_math.c




Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Roberto Ierusalimschy
In reply to this post by GrayFace-2
> On Пн 07.05.18 20:19, Roberto Ierusalimschy wrote:
> >What is present today in the latest release of Lua is 'rand'/'random',
> >not xorshift128plus.
>
> What about LuaJIT's PRNG? Having the same PRNG would be good for
> compatibility.
> "LuaJIT uses a Tausworthe PRNG with period 2^223 to implement
> math.random() and math.randomseed()."

I am no expert about PRNG, but according to some experts (the guys
who created xoroshiro, xorshift, etc.), "Our main 64-bit proposal for
an all-purpose, rock-solid generator is xoshiro256**". Moreover, it has a
quite simple implementation. What would be the "credentials" for
Tausworthe?

Do you have the code for this generator? Does it generate 64-bit numbers?
Is it easy to implement it even if the compiler does not support 64-bit
integers?

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Rodrigo Azevedo
2018-05-08 12:49 GMT-03:00 Roberto Ierusalimschy <[hidden email]>:
> On Пн 07.05.18 20:19, Roberto Ierusalimschy wrote:
> >What is present today in the latest release of Lua is 'rand'/'random',
> >not xorshift128plus.
>
> What about LuaJIT's PRNG? Having the same PRNG would be good for
> compatibility.
> "LuaJIT uses a Tausworthe PRNG with period 2^223 to implement
> math.random() and math.randomseed()."

I am no expert about PRNG, but according to some experts (the guys
who created xoroshiro, xorshift, etc.), "Our main 64-bit proposal for
an all-purpose, rock-solid generator is xoshiro256**". Moreover, it has a
quite simple implementation. What would be the "credentials" for
Tausworthe?

Do you have the code for this generator? Does it generate 64-bit numbers?
Is it easy to implement it even if the compiler does not support 64-bit
integers?

-- Roberto

 
Just an update of a real-world application. I'm working on a scientific stochastic code that "can" use the default PRNG of luajit and lua-5.4.0-work1 (don't worry!). Compared to luajit, lua-5.4.0-work1 exhibits a higher convergence rate, which is a symptom of a (maybe) better PRNG. Moreover,  luajit is "only" 60% faster (no I/O bound) than lua-5.4.0-work1, which makes me think about forgetting luajit forever.

Many thanks,
--
Rodrigo Azevedo Moreira da Silva
Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Hartmut Henkel
On Tue, 8 May 2018, Rodrigo Azevedo wrote:

> Just an update of a real-world application. I'm working on a
> scientific stochastic code that "can" use the default PRNG of luajit
> and lua-5.4.0-work1 (don't worry!). Compared to luajit,
> lua-5.4.0-work1 exhibits a higher convergence rate, which is a symptom
> of a (maybe) better PRNG. Moreover,  luajit is "only" 60% faster (no
> I/O bound) than lua-5.4.0-work1, which makes me think about forgetting
> luajit forever.

Just a remark, if good convergence rate is needed, e. g. for Monte Carlo
simulation or integration, Halton or Sobol "low-discrepancy" sequences
may perform better than PRNG and can be used as drop-in replacements. E.
g.,

local halton = function (index, base)
-- from en.wikipedia.org/wiki/Halton_sequence
  local result = 0
  local f = 1
  local i = index
  while i > 0 do
    f = f / base
    result = result + f * (i % base)
    i = math.floor(i / base)
  end
  return result
end

Regards, Hartmut
Reply | Threaded
Open this post in threaded view
|

Re: new PRNG's

Dirk Laurie-2
2018-05-08 23:53 GMT+02:00 Hartmut Henkel <[hidden email]>:

> On Tue, 8 May 2018, Rodrigo Azevedo wrote:
>
>> Just an update of a real-world application. I'm working on a
>> scientific stochastic code that "can" use the default PRNG of luajit
>> and lua-5.4.0-work1 (don't worry!). Compared to luajit,
>> lua-5.4.0-work1 exhibits a higher convergence rate, which is a symptom
>> of a (maybe) better PRNG. Moreover,  luajit is "only" 60% faster (no
>> I/O bound) than lua-5.4.0-work1, which makes me think about forgetting
>> luajit forever.
>
> Just a remark, if good convergence rate is needed, e. g. for Monte Carlo
> simulation or integration, Halton or Sobol "low-discrepancy" sequences
> may perform better than PRNG and can be used as drop-in replacements. E.
> g.,
>
> local halton = function (index, base)
> -- from en.wikipedia.org/wiki/Halton_sequence
>   local result = 0
>   local f = 1
>   local i = index
>   while i > 0 do
>     f = f / base
>     result = result + f * (i % base)
>     i = math.floor(i / base)
>   end
>   return result
> end

For integration, lattice methods (which superficially look like linear
congruential PRNGs but are designed to run over a complete cycle of
relatively small period) are worth a try.

12