Merge pull request #1857 from RaimoNiskanen/raimo/rand-crypto-xoroshiro928

OTP-14461 - New 'rand' algorithm: Xoroshiro928** also for 'crypto'

Implement a new 'rand' algorithm named 'exro928ss' and a new 'crypto' plugin for 'rand' named 'crypto_aes'.

Both are based on Xoroshiro928** which is derived from Xoroshiro1024** modified to use 58-bit words for performance reasons in the Erlang VM.  Xoroshiro1024** has got the Xoroshiro1024 generator and the StarStar scrambler from the 2018 paper "Scrambled Linear Pseudorandom Number Generators" by David Blackman and Sebastiano Vigna.

This generator and scrambler combination shows no systematic weaknesses in standard statistical tests as TestU01(BigCrush) and PractRand, unlike the previously used * and + scramblers in the 'rand' module that exhibit statistical weaknesses for the lowest bits.

The 'crypto' plugin uses AES-256 as scrambler and the Xoroshiro928 as generator, which gives the same very long period and jump functions as for Xoroshiro928**, but a cryptographically secure scrambler gives absolutely no detectable statistical weaknesses regardless of how the generated numbers are used.

The speed of 'exro928ss' is only about 30-50% slower than the default fast 'rand' algorithm, but the state is roughly the double and it produces about 8 times the garbage per iteration.

The speed of 'crypto_aes' is about half (amortized) that of the default fast 'rand' algorithm which is fast and thanks to doing encryption in batches caching the result.  Hence the state is much larger.

1 files changed, 55 insertions, 6 deletions

diff --git a/lib/stdlib/doc/src/rand.xml b/lib/stdlib/doc/src/rand.xml
index 21f680a0ee..25eec216ef 100644
--- a/lib/stdlib/doc/src/rand.xml
+++ b/lib/stdlib/doc/src/rand.xml
@@ -67,6 +67,26 @@
         <p>Xorshift1024*, 64 bits precision and a period of 2^1024-1</p>
         <p>Jump function: equivalent to 2^512 calls</p>
       </item>
+      <tag><c>exro928ss</c></tag>
+      <item>
+        <p>Xoroshiro928**, 58 bits precision and a period of 2^928-1</p>
+        <p>Jump function: equivalent to 2^512 calls</p>
+	<p>
+	  This is a 58 bit version of Xoroshiro1024**,
+	  from the 2018 paper by David Blackman and Sebastiano Vigna:
+	  <url href="http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf">
+	    Scrambled Linear Pseudorandom Number Generators
+	  </url>
+	  that on a 64 bit Erlang system executes only about 30% slower than
+	  the default <c>exrop</c> algorithm but with much longer period
+	  and better statistical properties, and on the flip side
+	  a larger state.
+	</p>
+	<p>
+	  Many thanks to Sebastiano Vigna for his help with
+	  the 58 bit adaption.
+	</p>
+      </item>
       <tag><c>exsp</c></tag>
       <item>
         <p>Xorshift116+, 58 bits precision and period of 2^116-1</p>
@@ -195,8 +215,8 @@ SND0 = math:sqrt(-2 * math:log(R5)) * math:cos(math:pi() * R6)</pre>
     </note>
 
     <p>
-      For all these generators the lowest bit(s) has got
-      a slightly less random behaviour than all other bits.
+      For all these generators except <c>exro928ss</c> the lowest bit(s)
+      has got a slightly less random behaviour than all other bits.
       1 bit for <c>exrop</c> (and <c>exsp</c>),
       and 3 bits for <c>exs1024s</c>.
       See for example the explanation in the
@@ -254,11 +274,32 @@ tests. We suggest to use a sign test to extract a random Boolean value.</pre>
       </desc>
     </datatype>
     <datatype>
-      <name name="exs64_state"/>
-      <desc><p>Algorithm specific internal state</p></desc>
+      <name name="seed"/>
+      <desc>
+	<p>
+	  A seed value for the generator.
+	</p>
+	<p>
+	  A list of integers sets the generator's internal state directly,
+	  after algorithm-dependent checks of the value
+	  and masking to the proper word size.
+	</p>
+	<p>
+	  An integer is used as the initial state for a SplitMix64 generator.
+	  The output values of that is then used for setting
+	  the generator's internal state
+	  after masking to the proper word size
+	  and if needed avoiding zero values.
+	</p>
+	<p>
+	  A traditional 3-tuple of integers seed is passed through
+	  algorithm-dependent hashing functions to create
+	  the generator's initial state.
+	</p>
+      </desc>
     </datatype>
     <datatype>
-      <name name="exsplus_state"/>
+      <name name="exrop_state"/>
       <desc><p>Algorithm specific internal state</p></desc>
     </datatype>
     <datatype>
@@ -266,7 +307,15 @@ tests. We suggest to use a sign test to extract a random Boolean value.</pre>
       <desc><p>Algorithm specific internal state</p></desc>
     </datatype>
     <datatype>
-      <name name="exrop_state"/>
+      <name name="exro928_state"/>
+      <desc><p>Algorithm specific internal state</p></desc>
+    </datatype>
+    <datatype>
+      <name name="exsplus_state"/>
+      <desc><p>Algorithm specific internal state</p></desc>
+    </datatype>
+    <datatype>
+      <name name="exs64_state"/>
       <desc><p>Algorithm specific internal state</p></desc>
     </datatype>
   </datatypes>