pseudo random numbers elementary number theory and its appliations, 2ed, K. Rosen. Addison-Wesley, 1988. middle square method, john von neumann (invent game theory, first computer, atomic bomb) 6139 37687321 6873 linear congruential method x_n+1 == ax_n + c ( mod m ), 0 <= x_n+1 < m m > 0, 2 <= a <= m, 0 <= c <= m, 0 <= x_0 <= m. theorem : the terms of the sequence generated by the linear congruential method are given by x_k == a^k x_0 + c(a^k - 1) / ( a -1 ) (mod m ), 0 <= x_k < m. proof : by mathematical induction. for k = 1 , the formula is obviously true, since x_1 == ax_0 + c ( mod m), 0 <= x_1 < m. Assume that the formula is valid for the k th term, so that x_k == a^k x_0 + c(a^k - 1) / ( a - 1) ( mod m ), 0 <= x_k < m. since x_k+1 == a x_k + c ( mod m), 0 <= x_k+1 < m, we have x_k+1 == a( a^k x_0 + c(a^k -1)/(a-1)) + c == a^(k+1) x_0 + c(a(a^k-1)/(a-1) + 1 == a^(k+1) x_0 + c(a^(k+1) - 1)/(a-1) (mod m) which is the correct formula for the (k+1)th term. This demonstrates that the formula is corrrect for all positive integers k. The period length of a linear congruential pseudo-random number generator is the maximum length of the sequence obtained without repetition. Theorem : The linear congruential generator produces a sequence of period length m if and only if (c,m) =1 , a == 1 (mod p) for all primes p dividing m, and a == 1 (mod 4) if 4 | m. For the proof see Knuth. A special case where c = 0 is called "multiplicative congruential method". x_n+1 == a x_n ( mod m), 0 < x_n+1 < m. or x_n == a^n x_0 (mod m), 0 < x_n+1 < m. For many applications, the generator is used with the modulus m equal to the Mersenne prime M_31 = 2^31 -1. When the modulus m is prime, the maximum period length is m -1, and this is obtained when a is a primitive root of m. To find a primitive root of M_31 that can be used with the good results, we first demonstrate that 7 is a primitive root of M_31. Theorem : The integer 7 is a primitive root of M_31 = 2^31 - 1. Proof : To show that 7 is a primitive root of M_31, it is sufficient to show that 7^((M_31 - 1)/q) =/= 1 ( mod M_31) for all prime divisors q of M_31 -1. With this information we can conclude that ord_(M_31) 7 = M_31 -1. To find factorization of M_31 -1, we note that M_31 - 1 = 2^31 -2 = 2(2^30 - 1) = 2(2^15 - 1)(2^15 + 1) = 2(2^5-1)(2^10+2^5+1)(2^5+1)(2^10-2^5+1) = 2.3^2.7.11.31.151.331 if we show that 7^((M_31 -1 )/q) =/= 1 (mod M_31) for q = 2,3,7,11,31,151,331, then we know that 7 is a primitive root of M_31 = 2147483647. Since 7^((M_31 -1)/2) == 2147483546 =/= 1 (mod M_31) 7^((M_31 -1)/3) == 1513477735 =/= 1 (mod M_31) 7^((M_31 -1)/7) == 120536285 =/= 1 (mod M_31) 7^((M_31 -1)/11) == 1969212174 =/= 1 (mod M_31) 7^((M_31 -1)/31) == 512 =/= 1 (mod M_31) 7^((M_31 -1)/151) == 535044134 =/= 1 (mod M_31) 7^((M_31 -1)/331) == 1761885083 =/= 1 (mod M_31) we see that 7 is a primitive root of M_31. In practice we do not want to use the primitive root 7 as the generator, since the first few integers generated are small. We find a larger primitive root using Corollary 8.4.1. We take a power of 7 where the exponent is relatively prime to M_31 - 1. For instance, since (5,M_31) = 1, Corollary 8.4.1 tells us that 7^5 = 16807 is also a primitive root. Since (13,M_31 -1 ) = 1, another possibility is to use 7^13 == 252246292 (mod M_31) as the multiplier. Corollary 8.4.1 : Let r be a primitive root modulo m where m is an integer, m > 1. The r^u is a primitive root modulo m if and only if (u,@(m)) = 1. Proof : By Theorem 8.4 we know that ord_m r^u = ord_m r/(u,ord_m r) = @(m)/(u,@(m)). consequently ord_m r = @(m), and r^u is a primitive root modulo m, if and only if (u,@(m)) = 1. Theorem 8.4 : If ord_m a = t and if u is a positive integer, then ord_m (a^u) = t / (t,u) Proof : Let s = ord_m(a^u), v = (t,u), t = t_1 v, and u = u_1 v. By Theorem 2.1 we know that (t_1, u_1) = 1. note that (a^u)^t_1 = (a^(u_1 v))^(t/v) = (a^t)^u_1 == 1 (mod m), since ord_m a = t. Hence Theorem 8.1 tells us that s | t_1 On the other hand, since (a^u)^s == 1 (mod m), we know that t | us. Hence t_1 v | u_1 vs, and consequently, t_1 | u_1 s. Since (t_1,u_1) =1 using Lemma 2.3 we see that t_1 | s. now, since s | t_1 and t_1 | s, we conclude that s = t_1 = t/v = t/(t,u). This proves the result.