The Rabin fingerprint looks something like this:

int hash(int[] message){
    int result = c;
    for(int v:message){
        result = result*p+v;
    return result;

for some $c$ and $p$. This may not be the canonical Rabin fingerprint but it's the version I'm familiar with.

So let's say we want to generate a message of length $n$ with some alphabet $A$ which hashes to some value $h$.

$n$ is a constant, so we can set $c$ to $0$ and offset $h$ accordingly. The word size is fixed and determines our modulus. Call that $M$. So we're left with some parameters:

  • $n$, the message length
  • $A$, the alphabet
  • $h$, the desired hash value
  • $p$, the prime used in hashing
  • $M$, the modulus

Assuming $n$ and $A$ are large enough, how can we quickly generate this message?

I'd guess powers of $2$ moduli are easier to work with, so if it can be done quickly for when $M$ isn't a power of $2$, how?


  • $n=16$
  • $A=\text{"abcxyz123"}$ (ASCII)
  • $h=0$
  • $p=3343$
  • $M=2^{20}$

We might get "1ab1xybb2b22z1az" or "ca32y2x2cyzxa3yc".


Your Answer

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

Browse other questions tagged or ask your own question.