2
$\begingroup$

Back in the ancient times, we used 997 * modulo 1000000 to generate pseudorandom numbers. Each number became the seed for the next number. It was fast, it wasn't too bad statistically, and was useful for many problems we ran on programmable calculators like the HP-41.

My problem: given a six-digit random number, is it possible to calculate the previous random number from which it was generated? If so, how? What if only five digits are retained instead of six?

|cite|improve this question
$\endgroup$
1
$\begingroup$

Yes.

If $a_{n+1}=997a_n\bmod 1000000$, then $a_n=444333a_{n+1}\bmod 1000000$. This is because $997\cdot 444333=443000001$.

If the last digit of $a_{n+1}$ is unknown, you obtain 10 possible values of $a_n$ accordingly, one differing from the next by $1003$ (why?)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for that! Note that the last digit is limited to (1, 7, 9, 3), (2, 4, 8, 6), (0), or (5), depending on what the initial seed was. Likewise, the last two digits are limited or orbits with periods of 1, 4, or 20. The 997 * generator has a period of 50,000 if the initial seed is 1. See the HHC 2018 web site. Anderen von Deutschland werden dort sein. $\endgroup$ – richard1941 May 9 '18 at 20:12
  • $\begingroup$ Now I see that an initial seed of 1 and a multiplier of 997 modulo 1000000 generates set of integers that satisfy all of the axioms for a GROUP, and 444333 is the inverse of 997. Since it is a group, we can learn a lot more about the structure. Thanks again for pointing me to increased knowledge. $\endgroup$ – richard1941 May 10 '18 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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