From: already5chosen@yahoo.com
On Wed, 7 Jan 2026 10:51:16 -0000 (UTC)
antispam@fricas.org (Waldek Hebisch) wrote:
> 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.
Yes, there are many stable tests. But there are also many unstable
tests in Crash/BigCrash batteries. I can't say if the ratio is 50:50 or
75:25, but it is not 90:10.
svaria_WeightDistrib() and swalk_RandomWalk1() appear most unstable.
You feed them with particular pseudo-random vector (100,000,000 points)
and the test fails. Then you shift the vector by just one point, to the
left or to the right. And it passes, often not just passes, but produces
a result that is not even close to the margin.
> And if you test long enough you should
> be able to estimate probability of failure and possibly compare
> is with theoretical result if available.
>
Long enough in this case is very damn long.
> 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.
>
It depends on what one considers fast.
My expectations, trained by LCGs and esp. by optimized MT, are rather
high. [On relatively modern Intel and AMD hardware] generators that do
feedback through even a single AES round (with another round for
post-processing) do not meet my expectations.
At best, fully inlined and after significant effort of removing all
non-necessary bottlenecks, such generators produce one output word per
4-5 clock cycles. More naive implementations with state read from
memory and stored back to memory on each iteration, are much slower
than that, easily takes over 10 clocks per iteration.
For comparison, a counter that goes through 5 rounds of AES without
feedback runs at 3 clocks per word when inlined and at 3.5 clocks per
word via function call.
It seems that given today's hardware limitations the only way to get
really fast PRNG with the state updated through AES round is by running
several chains interleaved. Preferably no less than 4 chains. Which
increases size of basic PRNG state to 512 bits + some more for state
management.
Another problem is that when all state bits go through AES then I can
not prove that the period of PRNG is really high. I can't even be sure
that it does not enter very short loop at some stage of its life. I
understand that it is highly unlikely, but don't like uncertainty.
Running half of the state through AES and taking another half from
counter solves it, but at cost of need for better diffusion in
post-processing (temper) state of generator. If more than 32 bits of
output produced per iteration, I would not feel good if tempering
consists of just one round of AES. I would want two rounds at least.
May be, better option is to do something like that:
interleave N times {
prnd_out = AES1R(state.w128);
state.w128 = AES1R(state.w128) ^ state.counter64;
state.counter64 = state.counter64 + 1;
}
I am still not 100% sure that the long period is guaranteed with such
arrangement, but I am far more sure of it than in case of original
arrangement.
However, it is far from simple and the state is not very small. So, the
question is "Why bother"? What's wrong with much simpler scheme that
takes 64-bit counter and runs it through 5 AES rounds? Or even 6 round
if being paranoid?
The only downside that I can see is that this simple robust scheme is
more dependent on high throughput of AES units which is not necessarily
available on somewhat older hardware.
> > 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.
>
Didn't I agree with that in the very next statement?
[continued in next message]
--- SoupGate-Win32 v1.05
* Origin: you cannot sedate... all the things you hate (1:229/2)
|
