Marsaglia's theorem

Last updated October 25, 2021

In computational number theory, Marsaglia's theorem connects modular arithmetic and analytic geometry to describe the flaws with the pseudorandom numbers resulting from a linear congruential generator. As a direct consequence, it is now widely considered that linear congruential generators are weak for the purpose of generating random numbers. Particularly, it is inadvisable to use them for simulations with the Monte Carlo method or in cryptographic settings, such as issuing a public key certificate, unless specific numerical requirements are satisfied. Poorly chosen values for the modulus and multiplier in a Lehmer random number generator will lead to a short period for the sequence of random numbers. Marsaglia's result may be further extended to a mixed linear congruential generator. ^[1]

Main statement

Consider a Lehmer random number generator with

r_{i+1}\equiv kr_{i}\mod m

for any modulus $m$ and multiplier $k$ where each $0<r_{i}<m$ , and define a sequence

u_{1}={\frac {r_{1}}{m}},u_{2}={\frac {r_{2}}{m}},u_{3}={\frac {r_{3}}{m}},\ldots

Define the points

\pi _{1}=(u_{1},\ldots ,u_{n}),\pi _{2}=(u_{2},\ldots ,u_{n+1}),\pi _{3}=(u_{3},\ldots ,u_{n+2}),\ldots

on a unit $n$ -cube formed from successive terms of the sequence of $u$ . With such a multiplicative number generator, all $n$ -tuples of resulting random numbers lie in at most $(n!m)^{1/n}$ hyperplanes. Additionally, for a choice of constants $c_{1},c_{2},\ldots ,c_{n}$ which satisfy the congruence

c_{1}+c_{2}k+c_{3}k^{2}+\cdots +c_{n}k^{n-1}\equiv 0\mod m,

there are at most $|c_{1}|+|c_{2}|+\cdots +|c_{n}|$ parallel hyperplanes which contain all $n$ -tuples produced by the generator. Proofs for these claims may be found in Marsaglia's original paper. ^[2]

Related Research Articles

In number theory, two integers $a$ and $b$ are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides one of $a$ or $b$ does not divide the other. This is equivalent to their greatest common divisor (gcd) being 1. One says also $a$ is prime to $b$ or $a$ is coprime with $b$ .

Quadratic reciprocity Gives conditions for the solvability of quadratic equations modulo prime numbers

In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard statement is:

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage-bit truncation.

A Lagged Fibonacci generator is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the Fibonacci sequence.

In mathematics, the Euler numbers are a sequence E_n of integers defined by the Taylor series expansion

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.

In mathematics, a low-discrepancy sequence is a sequence with the property that for all values of N, its subsequence x₁, ..., x_N has a low discrepancy.

RANDU is a linear congruential pseudorandom number generator (LCG) of the Park–Miller type, which was used primarily in the 1960s and 1970s. It is defined by the recurrence:

Inversive congruential generators are a type of nonlinear congruential pseudorandom number generator, which use the modular multiplicative inverse to generate the next number in a sequence. The standard formula for an inversive congruential generator, modulo some prime q is:

George Marsaglia was an American mathematician and computer scientist. He is best known for creating the diehard tests, a suite of software for measuring statistical randomness.

Gauss's lemma in number theory gives a condition for an integer to be a quadratic residue. Although it is not useful computationally, it has theoretical significance, being involved in some proofs of quadratic reciprocity.

In number theory, a branch of mathematics, Ramanujan's sum, usually denoted c_q(n), is a function of two positive integer variables q and n defined by the formula:

Cubic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x³ ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of the main theorem, which states that if p and q are primary numbers in the ring of Eisenstein integers, both coprime to 3, the congruence x³ ≡ p is solvable if and only if x³ ≡ q is solvable.

In computer science, multiply-with-carry (MWC) is a method invented by George Marsaglia for generating sequences of random integers based on an initial set from two to many thousands of randomly chosen seed values. The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around $to .$

The Lehmer random number generator, sometimes also referred to as the Park–Miller random number generator, is a type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n. The general formula is:

Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x⁴ ≡ p is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x⁴ ≡ p to that of x⁴ ≡ q.

In mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

An approach to nonlinear congruential methods of generating uniform pseudorandom numbers in the interval [0,1) is the Inversive congruential generator with prime modulus. A generalization for arbitrary composite moduli $with arbitrary distinct primes will be present here.$

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, as well as related higher-dimensional objects. Each one is an infinite extension of a finite symmetric group, the group of permutations (rearrangements) of a finite set. In addition to their geometric description, the affine symmetric groups may be defined as collections of permutations of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. These different definitions allow for the extension of many important properties of the finite symmetric groups to the infinite setting, and are studied as part of the fields of combinatorics and representation theory.

References

↑ Greenberger, Martin (October 1961). "An A Priori Determination of Serial Correlation in Computer Generated Random Numbers" (PDF). Mathematics of Computation . 15 (76): 383–389. doi: 10.2307/2003027 . JSTOR 2003027.
↑ Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS . 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi: 10.1073/pnas.61.1.25 . PMC 285899 . PMID 16591687.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Greenberger61-1] Greenberger, Martin (October 1961). "An A Priori Determination of Serial Correlation in Computer Generated Random Numbers" (PDF). Mathematics of Computation . 15 (76): 383–389. doi: 10.2307/2003027 . JSTOR 2003027.

[Marsaglia68-2] Marsaglia, George (September 1968). "Random Numbers Fall Mainly in the Planes" (PDF). PNAS . 61 (1): 25–28. Bibcode:1968PNAS...61...25M. doi: 10.1073/pnas.61.1.25 . PMC 285899 . PMID 16591687.

[1]

[2]