Is it possible to test 15-bit PRNG with the library TestU01?

Question

The library TestU01 inconvenient for generators that don't produce 32-bit outputs. But is it possible to somehow test say a 15-bit generator with it? How could that be done?

For instance, the generator included in the book ``The C Programming Language'' by Brian Kernighan and Dennis Ritchie is a 15-bit generator. Is there any way to test it against the TestU01 library?

For example, I could take 2 numbers from the generator and concatenate its bits, giving me a number with 30 bits. I still need 2 more bits to make 32 bits. I can get these two last one from another number from the generator (and ignore the 13 bits left of the third number). But this is changing the generator. It's a different thing now.

Answer 1

It can be taken groups of 32 samples of 15 bits, and turned each into 15 samples of 32 bits, either by transposition, or concatenation then splitting.

The best of the two method depends on the nature of the test, and TestU01 has several tests (as test suites do). If in doubt, use both methods. Should any valid test consistently fail more than predicted by its P-value, the generator has been demonstrated broken.

As always: absent any information on the generator tested, passing a statistical test gives zero insurance about its suitability for cryptographic purposes.

---

For instance, the generator included in the book The C Programming Language by Brian Kernighan and Dennis Ritchie is a 15-bit generator.

/* rand: return pseudo-random integer in 0..32767 */
int rand(void);

A 15-bit wide output can be cryptographically OK, but this generator's narrow key (an int) makes it a no-no from a cryptographic standpoint, even when we consider only its interface to set the key:

/* srand: set seed for (rand) */
void srand(unsigned int seed);

---

Further, when we consider the details of the implementation

unsigned long int next = 1;

/* rand: return pseudo-random integer in 0..32767 */
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

/* srand: set seed for (rand) */
void srand(unsigned int seed)
{
    next = seed;
}

we note that

• Only the low-order 31 bits of next and seed matter to the output, even when intand long are much wider (since next * 1103515245 + 12345 gets truncated to some number of low-order bits of the mathematically accurate result when it overflows; bits of next diffuse on the left only; and those above 31 do not make it to the result of rand).
• Among these operative 31 bits of next, 15 are known from one output, making it trivial to perform a brute-force search of the other 16 bits to recover the full state from 3 consecutive output. And there are even simple methods avoiding enumeration, thus scaling the generator from 31-bit to 256-bit would not make it secure.

Thus this particular generator is totally weak from a cryptographic perspective. Yet it still gets a pass from many statistical tests (including Ent applied to a few kilobytes of its output); and a scaled-up version of that generator would pass even more tests for all practical sizes.

Due to the particular structure of this generator, the best way to demonstrate that it is weak from the results of a byte-oriented Chi-squared test like Ent might be to keep the low-order 8 bits of each 15-bit output, and throw away the rest. But that's not a general rule, it depends a lot on the generator, and also on the test.

Answer 2

This one?

Generators of this form are called linear congruential generators. You can test them but by inspection you can see that it will fail a serious randomness test quite spectacularly. 32 bit numbers mod $2^{15}$ aren't well distributed in $n$ dimensions. They're useless cryptographically even if they were unbiased as the state can be easily discovered by looking at the output sequence. And the small 32 bit state results in short output cycles.

However, had it been a good quality generator of fairly compact code, you could just drop the higher bits. Speed would be sufficient. All of the bits in a good (CS)PRNG are independent of one another, so I'd just test the lowest eight. That's not really changing the generator due to the bit independence (of a good one).