Just possibly compiler explorer can help here - look at the machine code generated by a compiler. (Various compilers, various target CPUs, whichever options you like.)
https://godbolt.org/

The output is the same

Maybe there's a problem in your loop detector.

oh yes, i find it. My loop dectector count each output char, then "0101" in the output A07E0101, will be on index 4.
i suppose your index will only be 2?

Indeed, when I check at hex digit number 11EC9D07, I see the digits 008AA873 in the output, but they are shifted by one nibble:

The random number generator produced 60, 08, AA, 87, 3F, and that triggers your loop detector, which saw 008AA873 in the output stream.

the problem with your PRNG is always repeating output. With a 32-bit LFSR, the same 32-bit output does not repeat or 1 time maximum. With your PRNG, this is repeated much more, even if the internal state is not the same.

Here's the first real repeat of the 00 8A A8 73 sequence:

But as we compare that with the initial sequence, you can see it's not a loop. It's just a coincidence. The next bytes are different.

yes my loop dectector is able to detect loop in bits. Usually I do research directly on bit strings.

But the consequence is that it finds the same pattern more often. I find that the 4 byte initial pattern only repeats once in the first 4GB of data, which is expected. The 4GB limitation was a design criterion to keep it as small as possible.

A first conclusion is that rng_test is not a good test, it does not detect bit loops. I'm doing a search on the bits themselves and we'll see what happens.

I have always done my tests on LFSRs with bits and not bytes and LFSRs do not repeat. We will see if your PRNG repeats at the bit level.

But there is no loop. There is just a certain 32 bit pattern that repeats. If you check per individual bit, you would expect to see any 32 bit pattern occur, on average, once every 4 billion bits, or 512 million bytes.

Try your loop detector on /dev/random or a known good generator such as chacha 20.

Here's a histogram of how many times repeated 4-byte patterns there are in my random generator with seed=0, after 4GB of data, compared to expected values for perfect random numbers.

Arlet, yes you are right it's patterns not loops.

What i say is that LFSR is based on maths and there is no pattern. For my LFSR 32, the output is 2^32 different patterns. The maths says that and the real world too :

With my LFSR 32, the same pattern is only after 2^32 bits :



With your PRNG :



But you said your PRNG produces 2^32 bytes (4GB) then it's (2^32)*8 bits = 32 Giga-bits :

and with 32 Giga-bits here are the patterns with your PRNG :


The PRNG are building blocks. If they do not meet certain specifications, anything that can be produced on them afterwards may have big problems.

Chacha20 is based on strong maths for building blocks so you can't compare a final encryption system as chacha20 with a building block like your PRNG.

And the other problem is that rng_test don't detect patterns in your PRNG.

From what I understand is that you say that the repetition of patterns in a PRNG is not important. I do not think so. Because if we have patterns then there is linear relationships not foreseen in the algorithm and if we used this PRNG as building block to create an encryption system, then linear cryptanalysis could break it easily.

Correct, and that's not a good thing. If the numbers are truly random, you would expect to get some duplicates. If you take random 32 bit numbers, the chance of getting at least one duplicate grows to 1% even after drawing 10000 numbers. After 80000 numbers, the probability grows to more than 50%. If there's still not a single duplicate after half a million numbers, it's a safe bet to assume that the random number generator is broken.


You can run both through a test tool, such as your loop detector, and compare the differences. I bet you'll see quite similar behavior in number distribution over the first 4GB of output.


Probably, but it was never supposed to be cryptographically secure.