Modular Rank and Linear-Complexity Tests for Pseudorandom Number Generators
This work provides a new testing method for detecting linearity in pseudorandom generators over larger fields, addressing a gap in existing test suites.
The authors introduce modular rank and linear-complexity tests for pseudorandom number generators that are linear over larger fields, and implement them in a Rust program called modlin. modlin detects statistical bias in all current CERN's ROOT's implementations of the MIXMAX generator within minutes, where no standard test had previously reported failure.
Standard batteries of tests for pseudorandom number generators (such as dieharder, the NIST suite, and TestU01) provide two empirical tests for linearity, the binary rank and linear-complexity tests. Both operate over the field $\mathbf F_2$, and thus detect generators that are linear over $\mathbf F_2$. However, generators can be linear over a larger field, as in the case of congruential generators, single-modulus multiple-recursive recurrences, and of matrix generators such as MIXMAX. We introduce a modular version of the rank and linear-complexity tests, and provide modlin, a Rust program that implements it efficiently for fields of prime size. modlin can detect in minutes statistical bias in all current CERN's ROOT's implementations of the MIXMAX generator, for which no standard statistical test failure has been reported before.