# Identifying the type of algorithm for a PRNG that uses modular multiplication and addition

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.

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