The GLIBC random number generator

Question

I have a PRNG presentation tomorrow, and have to present how rand() function works.

I found a website that describes just what i need, but, as I'm a beginner in C, i have several questions.

Firstly, the site is http://www.mscs.dal.ca/~selinger/random/

My questions are:

• Why are first thirty numbers mod (2^31) - 1, and the rest are mod 2^32 (from the 34th) (connection with sizeof(int))?
• Is there any particular reason for why is the 30th number last that goes mod (2^31) - 1, why not go with 31 or 29?
• Why are r0...r343 thrown away?
• Why is the least significant bit of ri+344 thrown away?
• Why is 16807 chosen as the multiplier?

I know that there are alot of questions about PRNG, but i could not find answers to this questions.

I will present this topic in front of my class, and surely somebody will ask one of these questions, and I need some backup. Thank you.

Answer 1

After some research, i found out that this specific numbers (16807 and 2^31 - 1) are there for creating a full period, that is, generating all the numbers between 0 and 2^31 - 1 before any of these numbers appear again. Note, that 2^31 - 1 is a Mersenne prime, and 16807 is a primitive root mod(p); see Fermat-Euler theorem - this is far beyond my reach

Answer 2

Given a seed the function first populate an array of 34 unsigned longs using an LCG with modulus (2^31) - 1. Any LCG could have been used. This array is used for a LFSR generator with tabs at 3 and 31 using addition modulo 2^32. The output of this LFSR is post-processed by doing a right shift to discard the least significant bit.

The first 344 values are discarded to improve the quality of the numbers in case the original state of the array had too little entropy (imagine a case where almost all the numbers were zero). Given that the output of the LFSR satisfies r_{i} = r_{i-3} + r_{i-31} mod 2^32 a relation holding for the least significant bit as well, the function mask this by discarding the least significant bit. The shifting also guarantees that the output of rand is a positive integer as required by the standard.

Answer 3

You might read this for the construction of a pseudo-random generator, you have all answers in it.

What period is choose for the LCG, what multiplier is chosen etc...:

http://en.wikipedia.org/wiki/Linear_congruential_generator

http://en.wikipedia.org/wiki/Pseudo-random_number_generator