On the Use of Reducible Polynomials as Random Number Generators

Abstract

The randomness properties and the hierarchy of correlation coefficients are studied of approximate-maximum-length sequences, for which the characteristic polynomial is a product of several primitive polynomials. The randomness properties are almost the same as for maximum-length sequences characterized by a primitive polynomial with many terms and of the same degree. Reducible characteristic polynomials have acceptable figures of merit and can be of extremely high degree. Since they are also easily constructed and implemented, reducible polynomials are strong candidates for reliable random number generation, especially at the bit rates needed in large-scale Monte Carlo simulations.