From: already5chosen@yahoo.com
On Wed, 07 Jan 2026 08:41:25 -0800
Tim Rentsch wrote:
> Michael S writes:
>
> > On Tue, 23 Dec 2025 17:54:05 -0000 (UTC)
> > antispam@fricas.org (Waldek Hebisch) wrote:
> [...]
> >> There is a paper "PCG: A Family of Simple Fast Space-Efficient
> >> Statistically Good Algorithms for Random Number Generation"
> >> by M. O?Neill where she gives a family of algorithms and runs
> >> several statistical tests against known algorithms. Mersenne
> >> Twister does not look good in tests. If you have enough (128) bits
> >> LCGs do pass tests. A bunch of generators with 64-bit state also
> >> passes tests. So the only reason to prefer Mersenne Twister is
> >> that it is implemented in available libraries. Otherwise it is
> >> not so good, have large state and needs more execution time
> >> than alternatives.
> >
> > I don't know. Testing randomness is complicated matter.
> > How can I be sure that L'Ecuyer and Simard's TestU01 suite tests
> > things that I personally care about and that it does not test
> > things that are of no interest for me? Especially, the latter.
>
> Do you think any of the tests in the TestU01 suite are actually
> counter-indicated? As long as you don't think any TestU01 test
> makes things worse, there is no reason not to use all of them.
> You are always free to disregard tests you don't care about.
>
Except that it's difficult psychologically.
The batteries of test gains position of of authority in your mind.
Well, may be, you specifically are resistant, but I am not. Nor is
Melissa O'Nail, it seems.
To illustrate my point, I will tell you the story about myself.
Sort of confession.
If you had read the rest of this thread (or paid attention to
finer details in the article of O'Nail) then you already know that
mt19937 consistently fails in scomp_LinearComp() subtest of Crush and
BigCrush batteries of Test01. As reported, I "fixed" it by skipping
every 19936th word of mt19937 output. This particular "fix" is benign.
I am sure that it does not make output of generator less random. The
only impact is a bit of slowness, because of the need to manage yet
another modulo counter.
What I did not tell so far is that I tried another "fix". I added
leakage during mt state update. It means that periodically I
forced two LS bits of newly generated state word to be '01', without
affecting the word that goes to tampering and then to output.
And according to Test01 it worked! Flew through all batteries!
Luckily, I was sufficiently self-conscious to understand that I don't
understand nearly enough about algebra of Galois fields to predict all
consequences of my modification. But that's me. I know few people that
are less aware of their limitations.
> > Also, the TestU01 suit is made for generators with 32-bit output.
> > M. O'Neill used ad hoc technique to make it applicable to
> > generators with 64-bit output. Is this technique right? Or may
> > be it put 64-bit PRNG at unfair disadvantage?
>
> As long as the same mapping is applied to all 64-bit PRNGs under
> consideration I don't see a problem. The point of the test is to
> compare PRNGs, not to compare test methods. If someone thinks a
> different set of tests is called for they are free to run them.
>
But Melissa, following advice of L'Ecuyer, and me, following advice of
Melissa, tested 64-bit generators three times - LSW then MSW, only LSW
and only MSW, thus putting them under trice more serious scrutiny than
32-bit counterparts.
> > Besides, I strongly disagree with at least one assertion made by
> > O'Neill: "While security-related applications should use a secure
> > generator, because we cannot always know the future contexts in
> > which our code will be used, it seems wise for all applications to
> > avoid generators that make discovering their entire internal state
> > completely trivial."
> > No, I know exactly what I am doing/ I know exactly that for my
> > application easy discovery of complete state of PRNG is not a
> > defect.
>
> You and she are talking about different things. You are talking
> about choosing a PRNG to be used only by yourself. She is talking
> about choosing a PRNG to be made available to other people without
> knowing who they are or what their needs are. In the second case
> it's reasonable to raise the bar for the set of criteria that need
> to be met.
>
No, this part of her article is a mistake, plain and simple.
He even sort of admitted it couple of years later in her blogg.
In reality, we either need secure PRNG or do not need secure PRNG.
There is no middle ground of "more or less secure insecure PRNGs".
PRNGs she advocates are insecure until proven otherwise by crypto
analysts.
> > Anyway, even if I am skeptical about her criticism of popular PRNGs,
> > intuitively I agree with the constructive part of the article -
> > medium-quality PRNG that feeds medium quality hash function can
> > potentially produce very good fast PRNG with rather small internal
> > state.
>
> After looking at one of the example PCG generators, I would
> describe it as a medium-quality PRNG that feeds a low-quality
> hash. The particular combination I looked at produced good
> results, but it isn't clear which combinations of PRNG and
> hash would do likewise.
>
I tend to like CRC32C for hashing 64 bits into 32 bits; for no reason
apart from that this primitive is available and fast on modern Intel
and AMD CPUs. ARM64 CPUs as well, I think, although less than 100% sure.
> > On related note, I think that even simple counter fed into high
> > quality hash function (not cryptographically high quality, far
> > less than that) can produce excellent PRNG with even smaller
> > internal state. But not very fast one. Although the speed
> > depends on specifics of used computer. I can imagine computer
> > that has low-latency Rijndael128 instruction. On such computer,
> > running counter through 3-4 rounds of Rijndael ill produce very
> > good PRNG that is only 2-3 times slower than, for example, LCG
> > 128/64.
>
> I think the point of her paper where she talks about determining
> how much internal state is needed is to measure the efficacy of
> the PRNG, not to try to reduce the amount of state needed. Based
> on my own experience with various PRNGs I think it's a mistake to
> try to minimize the amount of internal state needed. My own rule
> of thumb is to allow at least a factor of four: for example, a
> PRNG with a 32-bit output should have at least 128 bits of state.
> My latest favorite has 256 bits of state to produce 32-bit
> outputs (and so might also do well to produce 64-bit outputs, but
[continued in next message]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
