From: antispam@fricas.org   
      
   Michael S  wrote:   
   > I experimented a bit more (in fact, more like a lot more) with   
   > test batteries of L’Ecuyer. It led me to conclusion that occasional   
   > failure in the either middle or big battery means nothing.   
   > Sometimes even cripto-quality PRNG does not pass one or another test.   
   > Then you try to reproduce it and see that with any other seed that you   
   > try a failure does not happen.   
   > All in all, it makes me more suspect of PRNGs that consistently pass   
   > both batteries with various seed. I start to see it as a sign of   
   > PRNG being rigged to pass tests.   
      
   Well, that depends on the tests and threshhold in the tests.   
   Some tests when fed with trurly random source will produce produce   
   very small variation of the results.  With generous threshhold   
   such test will essentially never fail for trurly random source.   
   OTOH when expected variation of the results is larger and   
   threshhold is tight, then trurly random source will fail the   
   test from time to time.  And if you test long enough you should   
   be able to estimate probability of failure and possibly compare   
   is with theoretical result if available.   
      
   To say the truth, I do not know what failures of crypto-quality PRNG   
   means.  It may mean that the test is of tight kind that is supposed   
   to fail from time to time for trurly random source.  Or it may mean   
   to PRNG improves cypto part at cost of statistics.  That is   
   non-uniform distribution of the output is not a problem in   
   crypto applications.  Simply for crypto purposes future output   
   should be not predictable from current and past output only.   
   And slightly non-uniform distribution can increase probablity   
   of test failure enough that you can observe such failures.   
      
   BTW: You mentioned using counter and hardware AES128 round.   
   Given cheap AES128 round I would try 128-bit state and AES128   
   round as state update.  I do not know if hardware AES128 is   
   fast enough to make it wortwhile, but using AES128 round as a   
   state update should be much better than scrambling a counter.   
      
   > Said above does not apply to scomp_LinearComp() failures of mt19937.   
   > Those failures are very consistent. I just don't consider them   
   > significant for my own use of PRNGs or for any other uses of PRNG that   
   > I personally ever encountered.   
   >   
   > Overall an experience strengthened my position that general wisdom,   
   > previously shared by O'Neil herself, got it right: in absence of the   
   > special considerations people should select mt19937 and especially   
   > mt19937-64 as their default PRNGs of choice.   
   > Looking closer, apart from its properties of randomness and apart from   
   > huge period   
      
   Huge period alone is easy.  AFAICS matrix variants of LCG can   
   easily get quite large periods.  I did not test matrix LCG,   
   but on statistical tests they should be essentially as good   
   as multiprecision LCG, but should be cheaper to implement.   
      
   Just to be clear, I mean equation x_{n+1} = Ax_n + b, wher x_n   
   is a vector reprezenting n-th state, A is a matrix and b is a   
   vector.  Matrix A may be somewhat sparse, that is have limited   
   number of non-zero entries, and some entries my be simple, like   
   1 or -1.  With proper choice of a and b period should be   
   comparable with number of availalable states.   
      
   I see no reason to go for very long periods, already 512 bits   
   of state allow perids which in practice should be indistingushable   
   from infinite period.   
      
   > (which does not matter for me) I started to appreciate for   
   > mt19937 for the following properties that I was not aware before:   
   > - it does not use multiplier. So good fit for embedded systems that   
   >   have no (or very slow) multiplier HW.   
      
   Biggest MCU with no hardware multiplier that I have has 2kB RAM.   
   I do not want mt19937 on such a machine.  64-bit multiplication   
   on 8-biter with hardware multiplier may be slow, so 64-bit LCG   
   (and improvements based on it) may be slow.  But multiplication   
   nicely spreads out bits, so it is not clear to me if there is   
   equally good cheaper alternative.  If needed I would investigate   
   matrix LCG, they may be slightly cheaper.   
      
   > - algorithm is very SIMD-friendly, so optimized implementations can be   
   >   very very fast on modern x86 and ARM64 hardware.   
      
   Just size of the state puts limit how fast it can be.  And size of   
   the state means that it will compete for cache with user data.   
   BTW: AFAICS matrix LCG can be SIMD friendly too.   
      
   > The latter property also means that very fast FPGA implementation is   
   > easily possible as long as designer is willing to through at it   
   > moderate amount of logic resources.   
   >   
   > Said above does not mean that PCG generators of O'Neil have no place.   
   > Intuitively, they appear not bad. But the theory is unproven, optimized   
   > implementation is likely slower that optimized mt19937, claimed   
   > "security" advantages are nonsense as admitted later by O'Neil herself.   
   > And, as said above, I no longer trust her empirical methodology, based   
   > on work of L’Ecuyer.   
   > So, PCG generators are valuable addition to the toolbox, but not good   
   > enough to change my default.   
      
   I agree that ATM it is not entirely clear if PCG-s are as good as   
   suggested by tests.  But I am surprised by your opinion about   
   speed, I did not analyze deeply either of them, but PCG-s are way   
   simpler, so I would expect them to be faster.   
      
   --   
                                 Waldek Hebisch   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)