Custom RNG : Modular Arithmetic Equation

Asked Nov 26 '20 at 10:45

Active Nov 26 '20 at 11:22

Viewed 37 times

I'm trying to recover the internal state of a custom RNG in order to predict the next state. The formula to compute the next state is as follow :

$nextState = (state * A + B) \mod p$

The value of p is the 9th mersenne prime ( $2^{61}-1$ )

A and B are large static integer ( they don't change between iterations )

I'm able to retrieve the values for the current states, but in order to predict the next one I need to find the values for parameters A and B

I've tried to generalize the equation as : $S_{i+1} = (S_i * A + B) \mod p$

If i understood modulo operation correctly, $S_{i+1}$ is the remainder of $(S_i * A + B) // p$

I don't know where to go from there, any resources or explanation to understand what I should be doing would be really appreciated.

edited Nov 26 '20 at 11:22

asked Nov 26 '20 at 10:45

Babar

1

Welcome to MSE. Please read this text about how to ask a good question. – José Carlos Santos Nov 26 '20 at 10:48
Is it a problem to calculate the remainder of $S_{i+1}$ in mod $p$ ? In other words, do you have a computer to do it? – Matti P. Nov 26 '20 at 11:01
Yes I have a computer but i dont understand what you mean by calculate the remainder of Si+1 in mod p. Si+1 is "something" mod p, so the remainder would be Si+1 ? – Babar Nov 26 '20 at 12:36

0 Answers0