Polynomial versus matrix methods for leap-ahead in shift-register type pseudorandom number generators
Michael Mascagni · University of Minnesota Digital Conservancy (University of Minnesota) · 1997
. We compare the cost of polynomial and matrix methods for leaping ahead an arbitrary amount in the period of shift-register based pseudorandom number generators. It is well known that both methods are applicable in the binary shiftregister case. However, for modular shift-registers with moduli other than 2, only the matrix method had been proposed. We present both methods for shift-registers with arbitrary moduli and compare their computational and memory costs. 1. Introduction. The most common method for pseudorandom number generation still remains D. H. Lehmer's linear congruential method. The linear congruential generator (LCG) is based on the following modular first-order linear recursion (1) x n = ax n\\Gamma1 + b (mod M): A generalization of the homogeneous LCG is the modular shift-register given by the recursion (2) x n = a 1 x n\\Gamma1 + a 2 x n\\Gamma2 + \\Delta \\Delta \\Delta + a ` x n\\Gamma` (mod M): This is the equation for a general `th order linear recursion modulo m. Sin...