Melissa O'Neill

From the Github repo: "Created by Daniel Cota after he fell down the PRNG rabbit-hole by circumstance." I understand how that can happen. Wondering how this PRNG compares to PCG PRNGs that also claim to be "simple fast space-efficient statistically good algorithms" and "hard to predict" [0]. In any case, it's good to see the excellent work being accomplished in this space. [0] https://www.pcg-random.org/

https://www.pcg-random.org/ PCG's statistical quality is "excellent" but chacha20's just "good"?

PCG generators are very good, very fast, and decently random, don't suffer (AFAIK) from bad seeds like Mersenne Twister, mix well, have small state, and have selectable periods of about any size. They are vastly better than LCGs. I use a 64 bit one and a 128 bit one for all sorts of work. These are not crypto, so don't use them for that. For non-crypto I have seen no better PRNG than these (and I've followed and written on this space for a long time). Code available on github. http://www.pcg-random.org/

MT19937 is probably not the best PRNG out there, but the nice thing about it is that, for a long time, there was a pretty strong consensus among programmers that it was the PRNG to use. It’s a better choice than a simple LCG, which is what programmers tend to use if they’re not using MT. There are a lot of crypto-strong RNGs out there (AES on OFB mode? Counter Mode? SHA-3 in SHAKE128 or SHAKE256? Salsa20 or ChaCha? Or, do what I do and use RadioGatún[32]), so not much standardization on that front. With non crypto, we have in this thread already mentioned PCG ( http://www.pcg-random.org/ ), JKISS32, xoroshiro, and Vigna’s generators. There are others. Again, not much standardization.

One candidate worth considering is http://www.pcg-random.org/

The best advice of all I've seen in the comments here. The PCG page: http://www.pcg-random.org/ contains a nice comparison table.

The page has no discussion of prior art like PCG[1], and no results from standard tests like Diehard[2] or TestU1[3]. It might be good, but I'd stick with proven alternatives. [1]: https://www.pcg-random.org/ [2]: https://en.wikipedia.org/wiki/Diehard_tests [3]: https://simul.iro.umontreal.ca/testu01/tu01.html

I agree, but https://www.pcg-random.org/ still advertizes PCG as "challenging" to predict, and critizises other RNGs as predictable and insecure.

I'm not sure which PRNG is used here, but some PRNGs have regularities in the lower bits. This is e.g. the case for classical LCGs and the xoroshiro*+ family of PRNGs: > If, however, one has to generate only 64-bit floating-point numbers (by extracting the upper 53 bits) xoshiro256+ is a slightly (≈15%) faster generator with analogous statistical properties. For general usage, one has to consider that its lowest bits have low linear complexity and will fail linearity tests (https://prng.di.unimi.it/) > When m = 2k there is a further problem. The period of the bth bit of an LCG (where bits are numbered from the right, starting at one) is 2b , thus although the period is 2k, only the high bits are good and the lower order bits exhibit a clear repeating pattern. (https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf)

There's the xoroshiro family, and there's the PCG family: https://www.pcg-random.org

That needs some conditions: * original Fisher-Yates is slow; Knuth's variation is what makes it fast * Fisher-Yates relies on "generate integer in range", which is often implemented badly (with bias, or with unnecessary slowness). See the PCG blog for the best-known solution. https://www.pcg-random.org/posts/bounded-rands.html

Use PCG: https://www.pcg-random.org/ Here is a stand-alone implementation of PCG32 in Go: package pcg32 type Src [2]uint64 func New(bits1, bits2 uint64) *Src { return &Src {bits1, bits2 | 1} } func (s *Src) Uint32() uint32 { var ( x = s[0] y = uint32(x >> 59) z = uint32((x>>18 ^ x) >> 27) ) s[0] = s[1] + x*6364136223846793005 return z>>y | z<<(-y&31) } func (s *Src) LessThan(n uint32) uint32 { for min := -n % n; ; { r := s.Uint32() if r >= min { return r % n } } }

In the context of that sentence though, it doesn’t make any sense. PCG is a PRNG, not a library for generating distributions. In fact, the PCG documentation uses the distributions from <random>: [1]. If people want to use PCG, that’s perfectly fine, it’s a great library. My point is, there’s nothing wrong with the PRNGs in <random>, they work great. Mersenne Twister is not state of the art anymore, but I guarantee you that unless you’re doing something truly insane, neither the throughput nor the statistical properties of MT is gonna be your bottleneck. [1]: https://www.pcg-random.org/using-pcg-cpp.html

I don't think this will work on PCG. "pcg32, which has state-space size of 2^127 (2^64 period × 2^63 streams) and produces 32-bit outputs." https://www.pcg-random.org/predictability.html That said, The PCG author does not recommend to use it for cryptography. "Although it is less trivial to predict than many mainstream generators, that does not mean it should be considered crypographically secure. Exactly how hard it is to break different members of the PCG family is unknown at this time." https://www.pcg-random.org/other-rngs.html

There's a bunch of analysis written by the PCG folks bashing Xoroshiro as well [1]. I think that for most normal use cases with randomized state, Xoroshiro is quite good. It only requires a single 64b add which is amazingly efficient. [1] https://www.pcg-random.org/posts/xoshiro-repeat-flaws.html

PCG and LCG (permuted/linear congruential generator) seem much stronger. This is one of my favorite presentations on the subject https://www.youtube.com/watch?v=45Oet5qjlms&t=2s and this matrix breaks it down well https://www.pcg-random.org/index.html

Just use PCG or XorShift* (in non-cryptographic contexts), they avoid almost all of the pitfalls while still having almost all of the low-overhead benefits https://www.pcg-random.org/

Its slow, large, and statistically worse than modern PRNGs- and jumping ahead takes longer and a more complicated algorithm. Even a truncated 128-bit LCG has far better properties. See https://www.pcg-random.org/index.html The homepage might come across as a a little overzealous (for example ChaCha quality listed as good rather than excellent), but generally has good points.

"Awful" was maybe hyperbole; mea culpa. I should have said: it's not great compared to other options available today. It shouldn't be your first choice anywhere. In short: * It has a huge state (~2kB per instance); compare 128-bit LCG at 128 bits or even a cryptographic PRF like Chacha at 64 bytes. This is a factor of 128x larger overhead (or 32x bigger than Chacha!) and hurts, say, L1 cache of more important data, especially with multiple instances. * It has mediocre statistical properties (fails TestU01 BigCrush, fails PractRand). (128-bit LCG passes both.) * And it has mediocre performance. (In the PCG benchmark, pg. 35: ~2.17 ns/op vs 128/64 LCG at ~1.05 ns/op. In that diagram, labelled "MCG" — but MCGs are just a subset of LCGs.) Ref: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf See also: https://en.wikipedia.org/wiki/Mersenne_Twister#Disadvantages

This looks pretty interesting and may well be an improvement over PCG[1]. For non-simulation purposes, however, using a fast-key-erasure[2] ChaCha20 or AES-256-CTR RNG has served me well enough, and doesn't leave me worrying if maybe someone could abuse the RNG for whatever purposes (e.g. cheating in a game by using RNG manipulation). [1] https://www.pcg-random.org/ [2] https://blog.cr.yp.to/20170723-random.html

Professor O'Neill (mentioned in the article) has written a PRNG [1]. The jury is still out on how powerful it is in general. There continue to be fights between what it means to be random for cryptographic purposes vs. numerical analysis purposes. That said, the PDF on that site that serves as a writeup for PCG contains a nice discussion of the links between the size of the state held and the strength of the algorithm, including a discussion of the state of the art for crypto- and non-crypto- PRNGs. [1] http://www.pcg-random.org/

Here's the site for the random number generator.[1] It's basically a simple linear congruential random number generator (well known, but not very good) fed into a mixer. The mixer is new. Most of the analysis is about the LCG or the final output. The suggested mixer is just output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122); That's simple, and the insight in this paper is that something that simple helps a lot. I would have thought that you'd want a mixer where changing one bit of the input changes, on average, half the bits of the output. The mixer above won't do that. DES as a mixer would probably be better, but it's slower. The new result here is that something this simple passes many statistical tests. This isn't crypto-grade; both that mixer and a LCG generator are reversible with enough work. [1] http://www.pcg-random.org/

You would probably enjoy checking out http://pcg-random.org/ it's got all that (tldr: powerful PRNG using very clever combination of simple permutation families), and a bunch of other useful properties. Also, no glossing over what exactly it does not (provably) do. It's not claiming to be cryptographically secure, for instance.

As an outsider to the field, I really enjoyed reading this paper: http://www.pcg-random.org/paper.html It's advocating for a particular new kind of PRNG, but it also includes a lot of great explanations and citations for more reading.

What research went into choosing XorShift128+? (Paper is apparently http://arxiv.org/pdf/1404.0390.pdf, which makes it seem like this still has quite a few failures on randomness tests.) Were any PRNG experts consulted? Did these folks consider http://www.pcg-random.org ? This talk was great http://www.pcg-random.org/posts/stanford-colloquium-talk.html HN discussions of PCG Random: 1) https://news.ycombinator.com/item?id=9887548 2) https://news.ycombinator.com/item?id=10544943

> Using /dev/urandom is not a good thing. It's only needed to get secure random numbers (CSPRGs) very slowly. https://gist.github.com/sarciszewski/f7bd4c0358a44321787b http://3v4l.org/j330O mt_rand() performs worse than CSPRNGs, funny enough Using a strong PRF we can take a 128-bit seed and turn it into an endless stream of random numbers. If /dev/urandom drains entropy, that's a bug that your OS should fix. > Everybody should know by now that the first bits are good, and the last bits horrible. That's why you should not use modulo %, but rshift or better use Melissa E. O'Neill's PCG, which uses the first good bits to improve the latter worse bits. http://www.pcg-random.org/ Yeah, there is no pgc_random() function in PHP though.

Using /dev/urandom is not a good thing. It's only needed to get secure random numbers (CSPRGs) very slowly. You'll drain it so that the apps which really need it will be out of seeds. To get random numbers fast, you need to use the good bits of a PRG based on an LCG. Everybody should know by now that the mersenne twister is not only bad, but also slow. Everybody should know by now that the first bits are good, and the last bits horrible. That's why you should not use modulo %, but rshift or better use Melissa E. O'Neill's PCG, which uses the first good bits to improve the latter worse bits. http://www.pcg-random.org/

Learn more about PCG here: https://www.pcg-random.org/

Thanks! It appears that Wikipedia has led me astray. The article in the top-level comment states, "if the generator is modified to return only the high 32 bits, then it passes BigCrush with zero failures." Following through to the document Wikipedia cites, I'm unable to find the original source for that claim. I suppose I'll look again after I have my coffee. Ah. Found it. From the PCG paper, "also of note, RanQ1[42] and XorShift* 64/32 are essentially the exact same generator, yet the former fails the test suite and the latter passes. The difference is that the former markets itself as a 64-bit generator and fails because its low-order bits are weak, whereas the latter only returns the top 32 bits." The claim of zero Big Crush failures also appears in Figure 2. http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf I suppose the next question is if the claim is wrong or I screwed up the implementation.

The information in the above post is a merger of like, 20 different sources of information. Your standard cryptographic books from any undergraduate program will tell you about the basics of confusion / diffusion, but I don't think the concept is very difficult at all. Invertibility is hugely important but not discussed very much. It seems like crypto-experts 'obviously' know about it so they just don't talk about it? Knuth and Bob Jenkins both talked about the importance of invertibility to random number generators. EDIT: Invertibility is the basis of bijective / 1-to-1 and onto permutation functions. To be fair, I think everyone discusses the concept but maybe with different words. Here's Jenkin's discussion on (non-crypto) hash functions, including a few paragraphs on "invertibility" (or "funnels" as they put it): http://www.burtleburtle.net/bob/hash/doobs.html The "pcg-random" generator also has a large discussion on invertibility. Honestly, one of the best writeups on the subject, and I felt like my IQ went up severely after reading the paper end-to-end: https://www.pcg-random.org/paper.html -------- The study of the invertibility of (data XOR (rotate-right data) XOR (rotate-left data)) is covered in many blogposts. https://marc-b-reynolds.github.io/math/2017/10/13/XorRotate.html The study of invertibility in general was covered by Lemire: https://lemire.me/blog/2016/08/09/how-many-reversible-integer-operatio… ----- So as you can see,…