GNU libc uses the following pseudo-random number generator: $$(\mathit{state} \times 1,103,515,245) + 12,345 \pmod {2^{31}}$$ where state is the result of the previous call to the generator.

My questions are:

  1. What are PRNGs using this algorithm - possibly using different numerical constants - called?

  2. Assume that this generator has the maximum possible period. What is its period?

  3. Given the result of a call to this PRNG, show how to obtain the result of the previous call symbolically?

For the last question it is not required to perform any numerical calculation.

This question was in my cryptology final-exam and I could not solve it and could not find the answer in internet, slides or books. I am really curious about the answers. I would appreciate if someone explain it to me.

up vote 6 down vote accepted

These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^{31}$ in that case).

Finding the previous value is a matter of inverting the iteration: $(\text{state} - 12345) \cdot 1103515245^{-1} \bmod 2^{31}$.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.