I am reading on a specific operation, how it should be done in order to avoid overflow during multiplication.
The operation is:
$$( A * \text{state} ) \% M;$$
This is susceptible to overflow.
The modified operation that does not have this pitfall is:
$$A(\text{state}(\bmod{Q})) - R(\text{state}/Q) + M\delta(\text{state})$$
$Q$ and $R$ are the quotient and remainder of $M/A$.
$\delta$ evaluates to 0 or 1 depending on the subtraction of the first 2 terms.
This $R (\text{state}/Q)$ is low limit/bound but I don't know the tag.
I don't get how these expressions are equivalent i.e. produce the same result.
Could you please help me?