I finally found some time to investigate this. I think it warrants a detailed response. In places I will repeat what others have pointed out, but I wanted something that ties together the various threads as best I can discern them.
I'm not certain what is meant by the Rule 30 RNG having "an extremely small effective size". Possibly it refers to taking bits only from the middle column? That is in fact what it does, or at least did the last time I looked at the implementation code. That is relatively less speed efficient than other RNGs but does give pseudorandom sequences of high quality. More on that in a bit.
I see the claim: "ExtendedCA: What is this? Apparently hasn't been tested." The documentation states
The cellular automaton used by "ExtendedCA" produces an extremely high level of randomness. It is so high that even using every single cell in output will give a stream of bits that passes many randomness tests, in spite of the obvious correlation between one cell and five previous ones.
I will give a bit more detail on this matter. In house testing has shown ExtendedCA passing all Diehard and BigCrush tests. One test has a p-value around .993, with all others in the range .01-.99. Moreover some correlation testing has been done that is outside of the tests in TestU01 (the Crush suite).
The Rule 30 generator is almost as good as this in terms of the Big Crush suite. I want to address specifically the following comment: "Rule30CA: Low quality (Meier & Staffelbach 1991, Sipper & Tomassini 1996)"
I have not yet managed to locate a copy of that first article. I did find some explanation of it in a more recent paper by Lacharme, Martin, and Sole (see refs below). I gather the issue is strictly of cryptographic usage, where (un)predictability is more important than (pseudo)randomness. They indicate that it may be possible to reconstruct part of the initial configuration given the stream of middle column bits. While this is out of my area, I will concede that this might be problematic for that type of use. That said, let me also remark that the initial configuration part reconstructed is from the left half set of columns. If one has a look at the Rule 30 output from a very specific one bit initial cell, as seen in the "Structure and properties" section in Rule 30's Wikipedia article, one will observe considerably more regularity on the left side than the right. This leads me to suspect that knowing the leftmost initial bits will not be of general help in full reconstruction of the middle column. But again, I'm no expert on this.
Pseudorandomness is an entirely different matter. As I mentioned above, Rule 30 actually tests quite well in this regard. So let me take up the matters under discussion in Sipper & Tomassini (1996). It is important to understand what exactly is their claim. They tested using not just the center column, but all columns, of the various RNGs. Used in this way, Rule 30 is indeed quite bad. That's why it does not get used in this way. I note that the authors point out that this is the actual use (first paragraph of section 2). They also state quite clearly (section 4):
The relatively low results obtained by the rule 30 CA may be due to the fact that we considered N random sequences generated in parallel, rather than the single one considered by Wolfram.
The point, I think, was not that they were claiming Rule 30 generator is bad when properly used, but rather that they were able to find ones that operate more efficiently in terms of how many bits can be used per iteration.
As mentioned in another response and comments thereto, they then (section 5) state (emphasis mine):
It seems safe to say at this point that our co-evolved generators are at least as good as the best available CA randomizers.
Here is the point. They tested against the suite by Knuth which, at the time of that writing, was "best practice". The Marsaglia Diehard test suite showed up also in 1996 so it may be no surprise they were not aware of it. The l'Ecuyer Crush tests were not around for several more years. Later analysis, as indicated in the paper by Seredynski, Bouvry, and Zumaya (linked to by a comment to this query, see below for another link), indicates that a related evolved CA-based generator, by Tomassini and Perrenoud (see below for ref), does not fare terribly well on Diehard. While I do not know if this is also the case for the Sipper and Tomassini RNG, I will speculate that the Sipper/Tomassini generator would be no better, and perhaps worse, since (going by dates of publication) it was very likely developed a few years earlier. The upshot is that the Rule 30 and ExtendedCA RNGs are, by the standards of current testing, quite sound. Some of the others that showed up in the earlier literature apparently fall short.
Some other pseudorandom remarks.
(From comments)
[T]he ExtendedCA generator is just a simplified version of CA30 so is likely to suffer from the same problems."
It may have similar problems but it is not a simplified version of Rule 30. It uses a neighborhood of five noncontiguous cells (this is indicated in the first paragraph describing it from the documention I referenced above).
Reading about the evolution methods used to construct nonuniform CA-based RNGs leads me to think they should not of necessity work well. That is to say, they might, but one has to be lucky. Here is my reasoning. First, as best I can tell, they select based on an entropy condition that will be satisfied even better by a low discrepancy sequence generator. Such sequences have excellent qualities e.g. for quasi-Monte-Carlo integration. But they are quite far from random. Second is that the winners of each "round" (in the sense of evolutionary methods) are heavily dependent on what I'll call "the kindness of neighbors". So there is no compelling reason to believe that a local rule that seemingly works well will continue to do so if its neighbors change. This is a general problem with evolutionary methods that have such linkage between genes or their equivalent units. Such methods do in practice still often give good results, due to the effect of co-evolution amongst neighbors. But still...
(From comments):
Now remember that Rule 30 was introduced for the purpose of crypto, so this is a reasonable avenue to check.
I cannot myself give an accurate accounting of the historical origins of Rule 30 applications. For what it is worth, here is what Stephen Wolfram writes in his 2002 NKS tome.
"I originally studied rule 30 in the context of basic science, but I soon realized that it could serve as the basis for practical random sequence generation and cryptography, and I analyzed this extensively in 1985. (Most but not all of the results from my original paper are included in this book, together with various new results.) In 1985 and soon thereafter a number of people (notably Richard and Carl Feynman) tried to cryptanalyze rule 30, but without success. From the beginning, computations of spacetime entropies for rule 30 (see page 960) gave indications that for strong cryptography one should not sample all cells in a column, and in 1991 Willi Meier and Othmar Staffelbach described essentially the explicit cryptanalysis approach shown on page 601. Rule 30 has been widely used for random sequence generation, but for a variety of reasons I have not in the past much emphasized its applications in cryptography."
I hope this is of some use for understanding the qualities of the CA-based RNGs in Mathematica.
Here are some references.
