Number Theory/32-bit Linear congruential generator

On 32-bit computers, pseudorandom numbers are generated using a linear congruential generator with base b = 40,014 and modulus m = 2,147,483,563 = 231 − 85. As the modulus m = 2,147,483,563 is a prime number, it follows from Fermat's little theorem that for any integer x such that x is not divisible by 2,147,483,563, It also follows that the multiplicative order of x modulo 2,147,483,563 must be either 2,147,483,562 or one of its proper divisors. The base b = 40,014 is a Primitive root modulo n primitive root modulo 2,147,483,563, so this sequence has the full period length of 2,147,483,562. Modular arithmetic For any prime number p, Fermat's little theorem guarantees that every integer x not divisible by p satisfies the following congruence: For example, for the prime number p = 13 and base x = 2, we substitute these values into the equation: 212 = 4,096. Fermat's little theorem predicts that this number is congruent to one modulo 13. Indeed, it is: 4,096 = 13 × 315 + 1, so In a prime modulus, any integer has at most two square roots. The congruence has only the trivial solutions a = ± 1 modulo p. For example, the only square roots of unity modulo 13 are 1 and 12. This is not true for composite moduli; for example, there are four square roots of unity modulo 15: 1, 4, 11, and 14. Since 2,147,483,563 is a prime number, for any x not congruent to zero modulo 2,147,483,563: Likewise, half of 2,147,483,562 is 1,073,741,781, so either or . Since 40,014 is a primitive root, it is not a quadratic residue, so . As a result, this value marks the halfway point of the cycle. Scientific Calculator Function The Texas Instrument calculator TI-30X IIS has a built-in pseudorandom number generator that uses the value of "rand" in the memory storage, accessible by pressing "MEMVAR." To change the value of "rand", store an integer to this variable by pressing "STO", pressing the left arrow button once, and pressing "ENTER." Once an integer is stored to this variable, it will usually stay put, changing when and only when a pseudorandom number is generated. Whenever a pseudorandom number is generated, the "rand" value will change according to the formula: (New Integer) = 40,014 × (Current Integer) modulo 2,147,483,563. To generate a pseudorandom number, press "PRB" and use "RAND" or "RANDI." Note that, here, "RAND" is in all caps, to distinguish between the integer variable in the memory storage. "RAND" is a pseudorandom decimal number between zero and one, calculated by dividing the new "rand" value by 2,147,483,563. For example, if rand = 500,000,000, then RAND = Texas Instrument calculators round off decimals to the nearest billionth, displaying nine digits beyond the decimal; in this case, this is displayed as 0.232830653. RANDI is a function that takes two arguments: RANDI(a, b) generates a pseudorandom integer between a and b, inclusive. Properties The first term of the cycle is one, and every term after that is calculated by multiplying by 40,014 and taking the remainder modulo 2,147,483,563. Second term: 40,014 Third term: 40,014 × 40,014 = 1,601,120,196 Fourth term: 1,346,387,765 because Fifth term: 439,883,729 because The sequence of random numbers repeats every 2,147,483,562 terms. The multiplicative inverse of 40,014 is 2,082,061,899 because . The number 2,082,061,899 is the last term of the cycle, after which the cycle starts again from the beginning. The last 5 terms of the cycle can be viewed by storing the number 77,872,045 as the seed value, designated as "rand" in the calculator's memory storage, then generating 5 random numbers. The negative multiplicative inverse of 40,014 is 65,421,664 because . This marks the halfway point of the cycle. Due to the 9-digit precision setting on the calculator, in which all decimal values are displayed rounded to the nearest billionth, the first value of "RAND" after storing 65,421,664 as the seed value is displayed as equaling 1. Actually, this value is , which is so close to one, differing from one by only 4.66 × 10−10, that it rounds to 1.000000000 when the calculator rounds it to nine decimal places. The number 65,421,664 is the last term of the first half of the cycle. The number 2,147,483,563 − 40,014 = 2,147,443,549 is the first term in the second half of the cycle. Table of values Note: In this table, m = 2,147,483,563. All RAND values are rounded to nine significant figures. Although the scientific calculator truncates 9-digit decimals ending with zero, the final zeroes will be preserved in this table (i.e., "0.123456000", not "0.123456"). n RAND 1 40,014 0.000018633 2 1,601,120,196 0.745579721 3 1,346,387,765 0.626960685 4 439,883,729 0.204836832 5 732,249,858 0.340980425 6 2,127,568,003 0.990726094 7 1,962,667,596 0.913938355 8 707,287,434 0.329356390 9 1,860,990,862 0.866591435 10 1,695,805,043 0.789670791 11 1,904,850,491 0.887015167 12 53,445,315 0.024887415 13 1,814,689,225 0.845030554 14 112,933,431 0.052588729 15 612,891,482 0.285399848 16 2,124,954,851 0.989509251 17 479,214,492 0.223151646 18 407,948,861 0.189965999 19 643,161,691 0.299495513 20 28,884,682 0.013450479 21 445,508,654 0.207456142 22 322,224,693 0.150047571 23 7,553,450 0.003517349 24 1,596,049,480 0.743218485 25 310,212,663 0.144454034 26 394,503,142 0.183704848 27 1,644,535,938 0.765796752 28 1,269,685,686 0.591243494 29 36,906,150 0.017185766 30 1,441,478,319 0.671240676 31 52,437,849 0.024418277 32 156,648,835 0.072945301 33 1,789,446,856 0.833276160 34 1,529,538,438 0.712246866 35 1,816,996,195 0.846104821 36 82,237,802 0.038294962 37 718,590,712 0.334619889 38 1,031,324,961 0.480248128 39 1,392,842,846 0.648593018 40 1,720,212,868 0.801036570 41 1,454,538,876 0.677322472 42 819,059,838 0.381404474 43 1,113,702,789 0.518608295 44 1,271,983,233 0.592313373 45 1,776,642,162 0.827313509 46 263,600,716 0.122748654 47 1,427,272,131 0.664625404 48 689,175,412 0.320922322 49 828,503,285 0.385801922 50 1,026,683,959 0.478086993