How to extend a hash function to manipulate longer integers?
I believe Schrage's method is exactly what you are looking for.

But for a general method of computing $ax + b \bmod m$ where $a, b, x, m$ all fit in a single CPU word and all are unsigned values I can quickly explain a method. I assume a CPU word has size $2^w$ and overflow is just modulo $2^w$.

First, computing $x + y \mod m$. Reduce $x, y \mod p$ (not necessary if you already know $x, y &lt; p$). Then, if $y \geq m - x$, overflow would occur. So in that case we compute $x + y - m$, otherwise simply $x+y$. In C++:

// Compute (x + y) % m, assumes x, y &lt; m.
uint64_t addmodu64(uint64_t x, uint64_t y, uint64_t m) {
    return x + y - m * (y &gt;= m - x);
}


Then, computing $xy \bmod m$ can be done by multiplication through repeated addition in $O(\log x)$ additions. We can repeatedly apply the following identity:

$xy \equiv (2\lfloor{x\over2}\rfloor + (x\bmod 2))y \equiv 2y\lfloor{x\over2}\rfloor + y(x\bmod 2) \mod m$

This gives a recursive function:

// Compute (x * y) % m, assumes x, y &lt; m.
uint64_t mulmodu64(uint64_t x, uint64_t y, uint64_t m) {
    if (x == 0) return 0;
    uint64_t y2 = addmodu64(y, y, m);
    uint64_t r = mulmodu64(y2, x/2, m);
    if (x % 2) r = addmodu64(r, y, m);
    return r;
}


This is just for demonstration purposes, for a fast implementation you want to convert this to a loop without any calls.

Finally, computing $(ax + b \bmod p) \mod m$ then is as simple as addmodu64(mulmodu64(a, x, p), b, p) % m.