Pseudorandomness

Pseudorandomness is a concept in computer science and cryptography that refers to the generation of number sequences that appear to be random, but are generated by a deterministic and repeatable process. These sequences are not truly random because they are completely determined by a small set of initial values, known as the pseudorandom number generator's seed data. Despite this, pseudorandom sequences pass many tests of statistical randomness and can be useful in many practical fields where true randomness is not necessary or feasible.

Overview

Pseudorandom number generators (PRNGs) are algorithms that can automatically create long runs of numbers with good random properties but eventually the sequence repeats exactly. PRNGs are central in applications such as simulations (e.g., for Monte Carlo methods), electronic games (e.g., for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs, and more elaborate algorithms, which do not repeat exactly, are needed.

Properties

Pseudorandomness has two main properties:

• Statistical randomness: A sequence of numbers is statistically random if it passes certain statistical tests of randomness. For example, the frequency of each digit should be approximately equal.

• Unpredictability: A sequence is unpredictable if it is computationally infeasible to predict what the next number will be, given complete knowledge of the prior numbers in the sequence.

Applications

Pseudorandomness is used in many areas of computer science. For example, in cryptography, pseudorandom number generators are used to generate keys for encryption algorithms. In computer graphics, pseudorandom numbers are used to generate procedural textures and shapes. In simulations, pseudorandom numbers are used to simulate complex systems.

See also

• Randomness
• Random number generation
• Cryptographically secure pseudorandom number generator
• Monte Carlo method
• Procedural generation