Random Numbers

Pseudo-random integers in Magma are generated using the Monster random number generator of G. Marsaglia [Marsaglia, 2000] (see also [Marsaglia and Zaman, 1991] and [Marsaglia, 1992]). The period of the Monster generator is \(2^{29430} - 2^{27382}\) (approximately \(10^{8859}\)), and the generator passes all of the stringent tests in Marsaglia’s Diehard test suite [Marsaglia, 1995]. Throughout the following text, the word ‘random’ is used to mean ‘pseudo-random’.

Random(a, b): RngIntElt, RngIntElt -> RngIntElt

A random integer lying in the interval \([a, b]\), where \(a\leq b\).

Random(b): RngIntElt -> RngIntElt

A random integer lying in the interval \([0, b]\), where \(b\) is a non-negative integer. Because of the good properties of the underlying Monster generator, calling Random(1) is a good safe way of producing a sequence of random bits.

RandomBits(n): RngIntElt -> RngIntElt

A random integer \(m\) such that \(0 \leq m < 2^n\), where \(n\) is a small non-negative integer. Thus, \(m\) has \(n\) random bits with a probability of 1/2 for each bit. The function always returns \(0\) when \(n=0\).

RandomPrime(n: parameter): RngIntElt -> RngIntElt

Proof: BoolElt                    Default: true

A random prime integer \(m\) such that \(0 < m < 2^n\), where \(n\) is a small non-negative integer. The function always returns \(0\) for \(n=0\) or \(n=1\). A rigorous method will be used to check primality, unless \(m > 3317044064679887385961981\) and the optional parameter Proof is set to Proof := false, in which case the result indicates that \(m\) is a probable prime (of order 20).

RandomPrime(n, a, b, x: parameter): RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt

Proof: BoolElt                    Default: true

Tries up to \(x\) iterations to find a random prime integer \(m\) congruent to \(a\) modulo \(b\) such that \(0 < m < 2^n\). If successful, the function returns true and the integer \(m\), otherwise false. The integer \(n\) must be larger than 0, \(a\) must lie between 0 and \(b-1\) and \(b\) must be larger than \(0\). A rigorous method will be used to establish primality, unless \(m > 3317044064679887385961981\) and the optional parameter Proof is set to Proof := false, in which case the result indicates that \(m\) is a probable prime (of order 20).

RandomConsecutiveBits(n, a, b): RngIntElt, RngIntElt -> RngIntElt

A integer \(m\) such that \(0 \leq m < 2^n\), and the binary expansion of \(n\) consists of consecutive strings of zeros or ones each of random length in the range \([a \ldots b]\).