Reverse engineering the seed of a linear congruential generator

The previous post gave an example of manipulating the seed of a random number generator to produce a desired result. This post will do something similar for a different generator.

A couple times I've used the following LCG (linear congruential random number generator) in examples. An LCG starts with an initial value of z and updates z at each step by multiplying by a constant a and taking the remainder by m. The particular LCG I've used has a = 742938285 and m = 2³¹ - 1 = 2147483647.

(I used these parameters because they have maximum range, i.e. every positive integer less than m appears eventually, and because it was one of the LCGs recommended in an article years ago. That is, it's very good as far as 32-bit LCGs go, which isn't very far. An earlier post shows how it quickly fails the PractRand test suite.)

Let's pick the seed so that the 100th output of the generator is today's date in ISO form: 20170816.

We need to solve

a¹⁰⁰z = 20170816 mod 2147483647.

By reducing a¹⁰⁰ mod 2147483647 we find we need to solve

160159497 z = 20170816 mod 2147483647

and the solution is z = 1898888478. (See How to solve linear congruences.)

The following Python code verifies that the solution works.

 a = 742938285 z = 1898888478 m = 2**31 - 1 for _ in range(100): z = a*z % m print(z)

Update: In this post, I kept n = 100 fixed and solved for the seed to give a specified output n steps later. In a follow up post I do the opposite, fixing the seed and solving for n.