# Rabin fingerprint preimage with given length and alphabet

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?

Example:

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

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