4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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