Random Numbers. Sequences Based On Linear Feedback

Table of Contents

1 Introduction

2 Basics in Statistics

2.1 Basic Concepts

2.1.1 Random Events and Frequencies

2.1.2 Probability

2.2 Theory on Testing

2.2.1 Statistical Hypotheses

2.2.2 Statistical Tests

2.2.3 Parameters of Tests

2.2.4 The Power of the Test Revisited

2.3 Summary

3 A Review On Random Numbers

3.1 Random Number Generators in History

3.1.1 Gambling, Tables, and Physical Devices

3.1.2 Transcendent and Irrational Numbers

3.1.3 Arithmetical Procedures

3.2 Usage of Random Numbers

3.2.1 Scientific Fields of Application

3.2.2 Other Fields of Application

3.3 Summary

4 Principles for Random Number Generation

4.1 Properties of Random Numbers

4.1.1 What Is a Random Number Generator?

4.2 On Random Sequences

4.2.1 Infinite Random Sequences

4.2.2 Finite Random Sequences

4.3 Mathematical Properties

4.3.1 Empirical Tests

4.3.2 Theoretical Analysis

4.4 Other Requirements

4.5 Summary

5 On Equidistribution and Transformation of Random Numbers

5.1 Uniform Random Numbers

5.1.1 One-Dimensional Uniform Distribution

5.1.2 Multidimensional Uniform Distribution

5.1.3 On ∞-distributed Uniform Sequences

5.2 Transformation of Uniform Random Numbers

5.2.1 Random Numbers with a Continuous Distribution

5.2.2 Random Numbers with a Discrete Distribution

5.3 Summary

6 Sequences Based On Linear Feedback

6.1 Defining the Linear Feedback

6.2 The Characteristic Polynomial

6.2.1 The Linear Transformation

6.2.2 On the Maximum Period Length

6.3 Sparse Primitive Polynomials

6.3.1 Primitive Trinomials

6.3.2 Primitive Pentanomials

6.3.3 Almost Primitive Trinomials

6.4 Summary

7 Improving Sequences Based on Linear Feedback

7.1 Generalized Feedback Shift Register Generators

7.1.1 Twisted Generators

7.1.2 Tempered Generators

7.2 Other Types of Shift Register Generators

7.2.1 Feedback with Carry Shift Register Generators

7.2.2 Shift Register Generators with Non-Linear Feedback

7.3 Combining Generators

7.3.1 Shuffling the Output

7.3.2 Linear Combination of Generators

7.3.3 Non-Linear Combination of Generators

7.4 Transforming the Output Sequence

7.4.1 Bit Stripping

7.4.2 Shifting

7.4.3 Adding or Taking Precision

7.4.4 Selecting Predefined Output Values

7.5 Summary

8 Conclusion

Objectives & Core Topics

This thesis examines the fundamental principles of random number generation, focusing on the evaluation and improvement of pseudo-random number generators (PRNGs). The central research goal is to understand how algorithms can produce sequences that effectively mimic the properties of truly random numbers, while balancing computational efficiency with statistical rigor.

• Statistical foundations and hypothesis testing for randomness
• Historical evolution and practical applications of random number generators
• Mathematical definition and properties of uniform and equidistributed sequences
• Deep dive into Linear Feedback Shift Register (LFSR) based generators
• Methods for improving generator quality through combination and transformation techniques

Excerpt from the Book

Summary of Chapters

1 Introduction: Provides an overview of the role of randomness in various fields and introduces the challenge of generating pseudo-random numbers on deterministic machines.

2 Basics in Statistics: Summarizes the fundamental concepts of probability and statistical hypothesis testing relevant for evaluating random number generators.

3 A Review On Random Numbers: Explores the history of random number generation, from early physical devices to mathematical and arithmetical approaches.

4 Principles for Random Number Generation: Defines the criteria for random sequences and discusses how mathematical properties can be tested empirically and theoretically.

5 On Equidistribution and Transformation of Random Numbers: Investigates the concept of uniform distribution in one and multiple dimensions, along with techniques to transform these numbers into other desired distributions.

6 Sequences Based On Linear Feedback: Details the theory behind linear feedback shift registers, including the characteristic polynomials that govern their period length.

7 Improving Sequences Based on Linear Feedback: Discusses advanced methods to improve the statistical properties of simple generators, such as combining multiple generators or applying non-linear transformations.

8 Conclusion: Synthesizes the results of the thesis, placing the discussed generation methods into the broader context of scientific needs and future research developments.

Keywords

Random Number Generation, Pseudo-Random Numbers, Statistical Hypothesis Testing, LFSR, Equidistribution, Monte Carlo Methods, Cryptography, Probability Theory, Linear Feedback, Shift Register, Numerical Analysis, Random Sequences, Characteristic Polynomial, Stochastic Simulation, Uniform Distribution

Frequently Asked Questions

What is the primary focus of this thesis?

The work focuses on the generation of pseudo-random numbers, specifically analyzing how algorithms can produce sequences that satisfy statistical requirements for randomness on deterministic computing devices.

What are the core thematic areas covered?

The thesis covers statistical foundations, the historical development of RNGs, mathematical properties of random sequences (such as equidistribution), and various methods for constructing and improving generator algorithms.

What is the primary research goal?

The goal is to provide a comprehensive understanding of PRNG construction, identifying how different classes of generators perform and how their statistical quality can be enhanced.

Which scientific methods are employed?

The research relies on mathematical analysis of generator structures, statistical tests for hypothesis evaluation, and comparative reviews of algorithmic efficiency in generating random variants.

What does the main part of the work address?

The main part systematically builds from statistical basics to specific algorithm classes, particularly focusing on Linear Feedback Shift Registers (LFSRs) and techniques like shuffling, combination, and transformation.

How can this work be characterized by keywords?

It is characterized by terms such as Pseudo-Random Number Generation, LFSR, Equidistribution, Monte Carlo Methods, Statistical Testing, and Cryptography.

What is the significance of the "lattice structure" mentioned in the text?

The lattice structure is a known defect in some pseudo-random number generators, where generated tuples of points fall onto a regular grid (lattice) rather than being truly randomly distributed, potentially impacting simulation results.

What is a "Mersenne prime" in the context of this thesis?

A Mersenne prime is a prime number of the form 2^k - 1. These primes are critical because they dictate the maximum possible period length of sequences generated by linear feedback systems of degree k.