Random Number Generators with Period Divisible by

a Mersenne Prime^{∗}

Richard P. Brent Computing Laboratory University of Oxford, UK

ICCSA@rpbrent.co.uk

Paul Zimmermann LORIA/INRIA Lorraine 615 rue du jardin botanique

BP 101, 54602 Villers-lès-Nancy France Abstract

∗Invited talk at ICCSA 2003, Montreal, 21 May 2003.

Copyright \begin{matrix}c \\ ◯ \end{matrix}2003, the authors. ICCSA03t

Pseudo-random numbers with long periods and good statistical properties are often required for applications in computational finance, numerical integration, physics, simulation, etc. We consider the requirements for good uniform random number generators, and describe a class of generators whose period is a Mersenne prime or a small multiple of a Mersenne prime. These generators are based on primitive or “almost primitive” trinomials, that is trinomials having a large primitive factor. They enable very fast vector/parallel implementations with excellent statistical properties.

Outline

• Requirements for RNGs

• Linear Congruential RNGs

• Generalized Fibonacci RNGs

• Ordering of triples

• Combining generators

• Comments on some available RNGs • Initialization

• Irreducible and primitive trinomials • Almost primitive trinomials

• Application to RNGs

Introduction

Pseudo-random number generators (RNGs) are widely used in simulation. A program running on a fast computer or cluster of PCs might use 10^{9} random numbers per second for many hours. Small correlations or other deficiencies could easily lead to spurious results. In order to have confidence in the results of simulations, we need to have confidence in the statistical properties of the random numbers used.

Some Requirements

• Uniformity. This is the easiest requirement to achieve, at least when considered over the whole period.

• Independence. d-tuples should be uniformly and independently distributed in d-dimensional space (say for d ≤ 6). Subsequences (e.g. odd/even) of the main sequence should be independent.

• Long Period. The period (length of a cycle in the random numbers generated) should be large, certainly at least 10^{12} and preferably much larger (say at least 10^{24}).

A few years ago, the generator RANU2 in the SSL II library on the Fujitsu VP2200 had period 2^{31} and ran through a complete cycle in less than one minute! This and similar generators are obsolete and should be avoided.

Requirements continued

• Statistical Tests. The generator should appear random when subjected to any “natural” statistical test (i.e. one which does not depend on a detailed knowledge of the algorithm used to generate the “random” numbers) using an amount of computation comparable to that in applications (say 10^{12} operations).

There are many statistical tests. Here are a few examples:

– Marsaglia’s “birthday spacings” test.

– Shchur, Heringa and Blöte’s 1D random-walk test.

– A test on orderings of triples (u_{n}, u_{n−i}, u_{n−j}) for 0 < j < i ≤ B, B^{2}/2 ≤ 10^{12} say. This test is designed to detect generators based on 3-term recurrences with lags ≤ B.

– Similarly for k-tuples with B^{k−1}/(k − 1)! ≤ 10^{12}, 3 ≤ k ≤ 7 say.

• Repeatability. For testing and development it is useful to be able to repeat exactly the same sequence as was used in another run, but not necessarily starting from the beginning of the sequence.

Thus, it should be easy to save all the state information required to restart the generator.

• Portability. For testing and development it is useful to be able to generate exactly the same sequences on different machines.

• Disjoint Subsequences. If a simulation is run on a parallel machine or on several independent machines, the sequences of random numbers generated on each machine must be independent (at least with very high probability).

• Efficiency. Only a few arithmetic operations should be required to generate each random number. Procedure call overheads should be minimised (e.g. one call could fill an array with random numbers).

Linear Congruential RNGs

Introduced by D. H. Lehmer in 1948.

U_{n+1} = (aU_{n} + c) mod m

where m > 0 is the modulus, a is the multiplier, and c is an additive constant.

Often m = 2^{w} is chosen as a convenient power of 2. In this case it is possible to get period m. However, w = 32 is not nearly large enough (10^{12} > 2^{39}).

If m is prime and c = 0, we can get period m − 1 by choosing a to be a primitive root.

Linear congruential generators have difficulty passing the spectral test (“Random numbers fall mainly in the planes” – Marsaglia).

Marsaglia and Zaman have introduced “add with carry” and “subtract with borrow” generators, which are essentially linear congruential generators with large moduli of a special form.

Generalized Fibonacci Generators

U_{n} = U_{n−r} θ U_{n−s}

where r and s are fixed “lags” and θ is some binary operator. We always assume 0 < s < r.

For example, the choice of θ = + (mod 2^{w}) which we assume below is convenient on a binary machine. In this case the period is at most

2^{w−1}(2^{r} − 1) ,

and this is attained if x^{r} + x^{s} + 1 is a primitive polynomial over GF(2) and the initial values U_{0}, …, U_{r−1} are not all even.

The case of addition in GF(2), i.e. w = 1, θ = ⊕, gives a linear feedback shift register (LFSR) generator which is easy to implement in hardware. These (and the case w > 1, θ = ⊕) are also called Tausworthe generators.

Problem with Ordering of Triples

If θ = + (mod m), then the orderings of certain triples do not occur with the correct probability (1/6). This is unacceptable if r = 2 (Fibonacci), but it is not so serious if r is large. Neglecting probabilities O(1/m), we have:

Ordering  Probability
U_{n−r} < U_{n−s} < U_{n}  1/4
U_{n−r} < U_{n} < U_{n−s}  0
U_{n−s} < U_{n−r} < U_{n}  1/4
U_{n−s} < U_{n} < U_{n−r}  0
U_{n} < U_{n−r} < U_{n−s}  1/4
U_{n} < U_{n−s} < U_{n−r}  1/4

We can implement a statistical test that gives a significant result for ordering of triples, knowing only that 0 < s < r ≤ B say, with O(B) words of memory, B + O(log B) random number calls, and O(B^{2} log B) overall operations.

The Generating Function

Suppose x_{n} = x_{n−r} + x_{n−s} over any field F, e.g. F = GF(2). We define the generating function

G(t) = ∑_{n≥0} x_{n}t^{n} .

It is easy to see that

G(t) = \frac{G_{0}(t)}{P (t)} ,

where G_{0}(t) is a polynomial of degree (at most) r − 1 defined by the initial values x_{0}, …, x_{r−1}, and

P (t) = 1 − t^{s} − t^{r}

is defined by the recurrence.

The generating function can be used to obtain various theoretical results (expected values, correlations, etc).

Improving a Generator by Decimation

If (x_{0}, x_{1}, …) is generated by a 3-term recurrence, we can obtain a (hopefully better) sequence (y_{0}, y_{1}, …) by defining y_{j} = x_{jp}, where p > 1 is a suitable constant. In other words, use every p-th number and discard the others. (“Decimation” refers to p = 10.)

Consider the case w = 1 (i.e. Tausworthe generators). If p = 2, the y_{j} satisfy the same 3-term recurrence! However, if p = 3 we do get an improvement. Using generating functions, it is easy to show that the y_{j} satisfy a 5-term recurrence. For example, if

x_{n} = x_{n−1} ⊕ x_{n−127} ,

so P (t) = 1 + t + t^{127}, then then expanding P (t)P (wt)P (w^{2}t), where w^{3} = 1, and replacing t^{3} by u, shows that

y_{n} = y_{n−1} ⊕ y_{n−43} ⊕ y_{n−85} ⊕ y_{n−127} .

An improvement (suggested by Lüscher) over simple decimation is decimation by blocks.

Combining Generators by Addition

We can combine some number K of generalized Fibonacci generators by addition (mod 2^{w}). If each component generator is defined by a primitive trinomial

T_{k}(x) = x^{r_{k}} + x^{s_{k}} + 1 ,

with distinct prime degrees r_{k}, then the combined generator has period

2^{w−1} ∏_{k=1}^{K}(2^{r_{k}} − 1)

and satisfies a 3^{K}-term linear recurrence.

Because the speed of the combined generator decreases like 1/K, we would probably take K ≤ 3 in practice. The case K = 2 seems to be better (and more efficient) than “decimation” with p = 3.

Combining By Shuffling

Suppose we have two pseudo-random sequences X = (x_{0}, x_{1}, …) and Y = (y_{0}, y_{1}, …). We can use a buffer V of size B say, fill the buffer using the sequence X, then use the sequence Y to generate indices into the buffer. If the index is j then the random number generator returns V [j] and replaces V [j] by the next number in the X sequence [Knuth, Algorithm M].

In other words, we use one generator to shuffle the output of another generator. This seems to be as good (and about as fast) as combining two generators by addition. B should not be too small.

Combining By Shrinking

Coppersmith et al suggested using one sequence to “shrink” another sequence.

Suppose we have two pseudo-random sequences (x_{0}, x_{1}, …) and (y_{0}, y_{1}, …), x_{i}, y_{i} ∈ GF(2). Suppose y_{i} = 1 for i = s_{0}, s_{1}, … Define a sequence (z_{0}, z_{1}, …) to be the subsequence (x_{s_{0}}, x_{s_{1}}, …) of (x_{0}, x_{1}, …). In other words, one sequence of bits (y_{i}) is used to decide whether to “accept” or “reject” elements of another sequence (x_{i}). This is sometimes called “irregular decimation”.

Combining two sequences by shrinking is slower than combining the sequences by ⊕, but is less amenable to analysis based on linear algebra or generating functions, so is preferable in applications where the sequence needs to be unpredictable (e.g. in cryptography – see Menezes et al, §6.3).

Comments on Some Available RNGs

Many implementations of linear congruential generators are available. They usually have a period which is too short and do not give good d-dimensional uniformity for d > 3 (Marsaglia).

Marsaglia dislikes Tausworthe RNGs because they fail the “birthday spacings” test. He recommends add/subtract with carry/borrow (“Very Long Period”) generators, but these may also fail the birthday spacings test or the gap test.

Shchur, Heringa and Blöte showed that generalized Fibonacci generators based on primitive trinomials of small degree fail a 1D random-walk test. To avoid this, we suggest using large degree and/or combining at least two generators. (This idea is certainly not original – it has been suggested by many people, although not so often used in practice.) We give some examples later.

Blocking of Output

It is easy to vectorise both linear congruential and generalised Fibonacci RNGs. This is only useful if batches of random numbers are generated together. Thus, the interface to a library routine should allow an array of random numbers to be returned. This comment applies even on a scalar workstation, because returning an array of random numbers reduces subroutine-call overheads.

Initialization

Using the theory of generating functions (or, less efficiently, linear algebra), it is possible to “skip ahead” n terms in the sequence for a generalized Fibonacci RNG in O(log n) arithmetic operations. The idea is similar to that of forming n-th powers by squaring and multiplication.

This technique allows us to guarantee that different seeds give different sequences for all practical purposes (e.g. use segments of the full sequence separated by more than 10^{18} numbers).

This facility is useful for performing independent simulations on a serial computer, or on each processor of a parallel computer.

Lazy Initialization

Consider a generalized Fibonacci RNG based on a primitive trinomial of degree r, using addition mod 2^{w}. There are W = 2^{r(w−1)}(2^{r} − 1) ways to initialize r words of w bits so that not all words are even. Each cycle has length L = 2^{w−1}(2^{r} − 1). Thus there are

C = W/L = 2^{(r−1)(w−1)}

distinct cycles. Provided w ≥ 2 and r is not too small, C is very large.

If we initialize the RNG twice using an independent RNG (e.g. a linear congruential generator), it is extremely unlikely that the two sequences will be in the same cycle. In fact, the probability is 1/C = 2^{−(r−1)(w−1)}. Thus, in practice this “lazy” method of initialization is adequate whenever we want to generate different random sequences (e.g. on different processors of a parallel computer).

Summary

• The class of generalized Fibonacci RNGs is attractive because of the potential for speed, long period, and good statistical properties.

• Generators based on 3-term recurrences are the fastest. They can (and should) be combined to give generators with better statistical properties.

• In order to find such RNGs with known (large) period, we need to find suitable (primitive or almost primitive) trinomials. This is the topic of the remainder of this talk.

Definitions

From now on we consider polynomials over GF(2). For the sake of brevity, we won’t repeat this statement every time!

Recall that, for polynomials u, v over GF(2), 2u = 2v = 0. This implies that u − v = u + v and (u + v)^{2} = u^{2} + v^{2}.

We say that a polynomial P (x) is reducible if it has nontrivial factors; otherwise it is irreducible.

If P (x) is irreducible of degree r > 1, then GF(2^{r}) ≈ Z_{2}[x]/(P (x)). If x is generator for the multiplicative group of Z_{2}[x]/(P (x)), then we say that P (x) is primitive.

Since the multiplicative group has order 2^{r} − 1, we need to know the complete factorization of 2^{r} − 1 in order to test if an irreducible polynomial is primitive. However, if r is a Mersenne exponent, i.e. 2^{r} − 1 is prime, then irreducibility implies primitivity.

Some Well-Known Results

The following results can be found in texts such as Lidl, Menezes et al. Here μ is the Möbius function, and ϕ is Euler’s phi function.

1. x^{2^{n}} + x is the product of all irreducible polynomials of degree d|n. For example,

x^{8} + x = x(1 + x)(1 + x + x^{3})(1 + x^{2} + x^{3}) .

2. Let J_{n} be the number of irreducible polynomials of degree n. Then

∑_{d|n} dJ_{d} = 2^{n} and J_{n} = \frac{1}{n} ∑_{d|n} 2^{d}μ(n/d) .

In particular, if n is prime then J_{n} = (2^{n} − 2)/n.

3. The number of primitive polynomials of degree n is P_{n} = ϕ(2^{n} − 1)/n ≤ J_{n}.

In particular, if n is a Mersenne exponent, then P_{n} = J_{n} = (2^{n} − 2)/n.

The Reciprocal Polynomial

If P (x) = ∑_{j=0}^{r} a_{j}x^{j} is a polynomial of degree r, with a_{0} ≠ 0, then

P_{R}(x) = x^{r}P (1/x) = ∑_{j=0}^{r} a_{j}x^{r−j}

is the reciprocal polynomial. Clearly P (x) is irreducible (or primitive) iff P_{R}(x) is irreducible (or primitive).

In particular, if

P (x) = 1 + x^{s} + x^{r} , 0 < s < r

is a trinomial, then the reciprocal trinomial is

P_{R}(x) = 1 + x^{r−s} + x^{r} .

If it is convenient, we can assume that s ≤ r/2 (else consider the reciprocal trinomial).

When applied to random number generation, the reciprocal polynomial generates the sequence in reverse order.

Irreducible Trinomials

For applications such as random number generation, we want irreducible (or better, primitive) polynomials of high degree r and with a small number of nonzero terms. Hence, we restrict attention to trinomials of the form

P (x) = P_{r,s}(x) = 1 + x^{s} + x^{r} , 0 < s < r .

Swan’s Theorem

Swan (1962) determines the parity of the number of irreducible factors by an argument involving the discriminant (actually, Swan’s Theorem is a rediscovery of 19th century results).

If r is an odd prime, then Swan’s theorem implies that P_{r,s}(x) has an even number of irreducible factors (and hence is reducible) if r = ±3 mod 8 and s ≠ 2 or r − 2.

The condition on s can not be omitted, e.g. x^{29} + x^{2} + 1 is irreducible.

Some Primitive Trinomials

In Table 1 we give a table of primitive trinomials x^{r} + x^{s} + 1 where r is a Mersenne exponent (i.e. 2^{r} − 1 is prime). We assume that 0 < 2s ≤ r (so x^{r} + x^{r−s} + 1 is not listed).

Results for r < 756839 are given by Heringa et al. [11]. We have confirmed these results.

The entries for r < 3021377 have been checked by running at least two different programs on different machines.

During this checking process, the entry with

r = 859433, s = 170340

was found. This was surprising, because Kumada et al. [14] claimed to have searched the whole range for r = 859433. It turns out that Kumada et al. missed this entry because of a bug in their sieving routine!

Some Primitive Trinomials cont.

In Table 1, x^{r} + x^{s} + 1 is primitive over GF(2). The entries for r = 132049 are by Heringa et al. Smaller primitive trinomials are listed in Heringa’s paper and the references given there. The second entry for r = 859433 is from Kumada et al.. The other seven entries were found by Brent, Larvala and Zimmermann.

\begin{matrix}r & s \\ 132049 & 7000, 33912, 41469, 52549, 54454 \\ 756839 & 215747, 267428, 279695 \\ 859433 & 170340, 288477 \\ 3021377 & 361604, 1010202 \\ 6972593 & 3037958 \end{matrix}

Table 1: Primitive trinomials

Almost Primitive Trinomials

There is a large gap between some of the Mersenne exponents r for which primitive trinomials exist. For example, there are none in the interval 859433 < r < 3021377, even though there are three Mersenne exponents in this interval. This is because Swan’s theorem rules out about half of the Mersenne exponents – it rules out most exponents of the form r = ±3 mod 8. The usual solution is to consider pentanomials (five nonzero terms) instead of trinomials, but a faster alternative is to use almost primitive trinomials. Definition. We say that a polynomial P (x) is almost primitive with exponent r and increment δ < r if P (x) has degree r + δ, P (0) ≠ 0, and P (x) has a primitive factor of degree r.

Almost Primitive Trinomials cont.

For example, the trinomial x^{16} + x^{3} + 1 is almost primitive with exponent 13 and increment 3, because

x^{16} + x^{3} + 1 = (x^{3} + x^{2} + 1)D(x),

where

D(x) = x^{13} +x^{12} +x^{11} +x^{9} +x^{6} +x^{5} +x^{4} +x^{2} +1

is primitive.

In Table 2 we list some almost primitive trinomials. In fact, we give at least one for each Mersenne exponent r < 10^{7} for which no primitive trinomial of degree r exists. The search is complete for r < 2976221.

r  δ  s  f
13  3  3  7
19  3  3  7
61  5  17  31
107  2 8, 14, 17  3
2203  3  355  7
4253  8  1806  255
1960  85
9941  3  1077  7
11213 6  227  63
21701 3 6999, 7587 7
86243 2  2288  3
216091 12  42930  3937
1257787 3  74343  7
1398269 5  417719  21
2976221 8 1193004  85

Table 2:

Some almost primitive trinomials over GF(2). x^{r+δ} + x^{s} + 1 has a primitive factor of degree r; δ is minimal; 2s ≤ r + δ; the period ρ = (2^{r} − 1)f.

A Larger Example

We already considered the almost primitive trinomial x^{16} + x^{3} + 1. Here we give an example with higher degree: r = 216091, δ = 12. We have

x^{216103} + x^{42930} + 1 = S(x)D(x),

where

S(x) = x^{12} + x^{11} + x^{5} + x^{3} + 1,

and D(x) is a (dense) primitive polynomial of degree 216091. The factor S(x) of degree 12 splits into a product of two primitive polynomials,

x^{5} + x^{4} + x^{3} + x + 1 and
x^{7} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1.

The contribution to the period from these factors is f = LCM(2^{5} − 1, 2^{7} − 1) = 3937.

Use of Almost Primitive Trinomials in RNGs

If T (x) = x^{r+δ} + x^{s} + 1 is almost primitive with exponent r, we can use the corresponding linear recurrence

U_{n} = U_{n−r−δ} + U_{n−s} mod 2^{w}

as a generalized Fibonacci random number generator. The period will be a multiple of 2^{r} − 1 (usually a multiple of 2^{w−1}(2^{r} − 1)) provided U_{0}, …, U_{δ} are odd. The condition ensures that a recurrence with lags ≤ δ (corresponding to the degree-δ factor of T (x)) is not satisfied.

Some Random Number Generators

Although it is easy to suggest bad random number generators, there is no “best” generator. Here are a few possibilities for good generators based on primitive or almost trinomials 1 + x^{s} + x^{r}. (Note our slight change of notation, r ← r + δ.) The memory requirements are stated on the assumption that each random number takes eight bytes.

1. Combine (r, s) = (2976221 + 8, 1193004), and (r, s) = (3021377, 361604) by addition.

The period is greater than 10^{1800000} (!)

The numbers satisfy a 9-term recurrence given by the product

(1 + x^{1193004} + x^{2976229})(1 + x^{361604} + x^{3021377}) .

Uses 46MB of memory and slow to initialise, so this is “overkill”.

Some RNGs continued

2. Combine two generators by shrinking, where the “small” generator uses (say) (r, s) = (3217, 576), and the “large” generator uses (r, s) = (3021377, 361604) and gives single bits (they can be generated a word at a time for efficiency).

The period is 2^{3021376}(2^{3217} − 1) and the memory requirement is 394KB.

3. Combine (r, s) = (1279, 418), (2281, 1029).

The period is > 10^{1000}.

The generator is fast, and uses only 28KB memory. The numbers satisfy a 9-term recurrence, so we expect good statistical properties.

Some RNGs continued

4. Combine (r, s) = (109, 2), (127, 30), and (521, 158) by addition (and perhaps shuffling).

The period is > 10^{227}. Uses only 6KB memory, so should run in cache (important for speed).

The output satisfies a 27-term recurrence (if combined by addition), so expect excellent statistical properties.

5. Combine two of the three generators above (restricted to single bits) by shrinking to obtain a cryptographically strong generator with memory less than 100 bytes (excluding the program). This might be appropriate for implementation in hardware or firmware.

ranut

Many random number generators based on primitive trinomials have been documented in the literature, but the implementations are usually for a fixed trinomial. The choice of this trinomial involves a tradeoff. Larger values of the degree r give generators with better statistical properties, but the space requirements and the time required for initialization increase with r. Thus, the optimal choice of a trinomial depends on the particular application and computing resources available. We have implemented an open-source uniform pseudo-random number generator ranut that automatically selects a primitive or almost primitive trinomial whose degree depends on the size of the working space allocated by the user, and then implements a generalized Fibonacci generator based on that trinomial. We believe that ranut satisfies all the requirements of mentioned earlier. It has been tested with Marsaglia’s Diehard package and no anomalous results have been observed.

Last Words

Many good random number generators in the literature are based on primitive trinomials. However, only a small number of primitive trinomials of large degree are known. By introducing the concept of “almost primitive” trinomials we have roughly doubled the number of possible choices.

References

[1] S. L. Anderson, Random number generators on vector supercomputers and other advanced architectures, SIAM Rev. 32 (1990), 221–251.

[2] R. P. Brent, On the periods of generalized Fibonacci recurrences, Math. Comp. 63 (1994),

389–401. http://www.comlab.ox.ac.uk/oucl/
work/richard.brent/pub/pub133.html

[3] R. P. Brent, Random number generation and simulation on vector and parallel computers (extended abstract), Proc. Fourth Euro-Par Conference, LNCS 1470, Springer-Verlag, Berlin, 1998, 1–20. · · ·/pub185.html

[4] R. P. Brent, Some uniform and normal random number generators, version 1.03 (January 2002).

Available from http://www.comlab.ox.ac.uk/
oucl/work/richard.brent/random.html

[5] R. P. Brent, S. Larvala and P. Zimmermann, A fast algorithm for testing irreducibility of trinomials mod 2 …, Math. Comp. 72 (2003), 1417–1441. · · ·/pub199.html

[6] A. Compagner and A. Hoogland, Maximum-length sequences, cellular automata, and random numbers, J. Computational Physics 71 (1987), 391–428.

[7] D. Coppersmith, H. Krawczyk and Y. Mansour, The shrinking generator, Proc. CRYPTO’93, LNCS 773 (1994), 22–39.

[8] A. M. Ferrenberg, D. P. Landau and Y. J. Wong, Monte Carlo simulations: Hidden errors from “good” random number generators, Phys. Rev. Lett. 69 (1992), 3382–3384.

[9] GIMPS, The Great Internet Prime Search,

http://www.mersenne.org/

[10] S. W. Golomb, Shift register sequences, Holden-Day, San Francisco, 1967.

[11] J. R. Heringa, H. W. J. Blöte and A. Compagner. New primitive trinomials of Mersenne-exponent degrees for random-number generation, International J. of Modern Physics C 3 (1992), 561–564.

[12] F. James, A review of pseudorandom number generators, Computer Physics Communications 60 (1990), 329–344.

[13] D. E. Knuth, The art of computer programming, Volume 2: Seminumerical algorithms (third ed.), Addison-Wesley, Menlo Park, CA, 1998.

[14] T. Kumada, H. Leeb, Y. Kurita and M. Matsumoto, New primitive t-nomials (t = 3, 5) over GF(2) whose degree is a Mersenne exponent, Math. Comp. 69 (2000), 811–814. Corrigenda: ibid 71 (2002), 1337–1338.

[15] Y. Kurita and M. Matsumoto, Primitive t-nomials (t = 3, 5) over GF(2) whose degree is a Mersenne exponent ≤ 44497, Math. Comp. 56 (1991), 817–821.

[16] R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge Univ. Press, Cambridge, second edition, 1994.

[17] M. Lüscher, A portable high-quality random number generator for lattice field simulations, Computer Physics Communications 79 (1994), 100-110.

[18] G. Marsaglia, Random numbers fall mainly in the planes, Proc. Nat. Acad. Sci. USA 61 (1968), 25-28.

[19] G. Marsaglia, A current view of random number generators, in Computer Science and Statistics: The Interface (edited by L. Billard), Elsevier Science Publishers B. V. (North-Holland), 1985, 3–10.

[20] G. Marsaglia and L. H. Tsay, Matrices and the structure of random number sequences, Linear Algebra Appl. 67 (1985), 147–156.

[21] G. Marsaglia and A. Zaman, A new class of random number generators, Ann. of Appl. Prob. 1 (1991), 462-480.

[22] A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, New York, 1997.

http://cacr.math.uwaterloo.ca/hac/

[23] J. F. Reiser, Analysis of additive random number generators, Ph. D. thesis, Department of Computer Science, Stanford University, Stanford, CA, 1977. Also Technical Report STAN-CS-77-601.

[24] E. R. Rodemich and H. Rumsey, Jr., Primitive trinomials of high degree, Math. Comp. 22 (1968), 863–865.

[25] L. N. Shchur and P. Butera, The RANLUX generator: resonances in a random walk test, May 1998, preprint hep-lat/9805017 available

from http://xxx.anl.gov.

[26] L. N. Shchur, J. R. Heringa and H. W. J. Blöte, Simulation of a directed random-walk model: the effect of pseudo-random-number correlations, Physica A 241 (1997), 579.

[27] W. Stahnke, Primitive binary polynomials, Math. Comp. 27 (1973), 977–980.

[28] R. G. Swan, Factorization of polynomials over finite fields, Pacific J. Math. 12 (1962), 1099–1106.

[29] R. C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965), 201–209.

[30] S. Tezuka, Efficient and portable combined Tausworthe random number generators, ACM Trans. on Modeling and Computer Simulation 1 (1991), 99–112.

[31] I. Vattulainen, T. Ala-Nissila and K. Kankaala, Physical tests for random numbers in simulations, Phys. Rev. Lett. 73 (1994), 2513–2516.

[32] E. J. Watson, Primitive polynomials (mod 2), Math. Comp. 16 (1962), 368–369.

[33] N. Zierler, Primitive trinomials whose degree is a Mersenne exponent, Inform. and Control 15 (1969), 67–69.