Pseudo-Random Number Generation by Staggered Sampling of LFSR
Shûichi Ichikawa
Abstract
Linear Feedback Shift Register (LFSR) is widely used as a simple Pseudo-Random Number Generator (PRNG). In 2009, Gu and Zhang proposed a Leap-ahead LFSR, which applies the feedback polynomial multiple times to achieve a larger generation rate. Though a Leap-ahead LFSR applies the feedback polynomial a fixed number of times, the quality of randomness could be potentially improved by applying the feedback polynomial variable times. This study introduces a Staggered LFSR, where a subordinate LFSR determines the number of feedback polynomial applications for the main LFSR. Our evaluation results demonstrate that a Staggered LFSR exhibits better randomness quality compared to a Leap-ahead LFSR of the same length. Though the subordinate LFSR requires an additional cost, the overhead is minimal. The Staggered LFSR, designed with appropriate parameters, successfully passed both the Diehard test and the NIST SP 800-22 test.