The Rabin-Karp string search algorithm is often explained using a rolling hash function that only uses multiplications and additions:
:,where is a constant, and are the input characters (but this function is not a Rabin fingerprint, see below).

In order to avoid manipulating huge values, all math is done modulo . The choice of and is critical to get good hashing; in particular, the