1
$\begingroup$

I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$.

I utilize the properties of modular arithmetic and horner's method for computing polynomials to get the following procedure.

s=0
for i=0...n-1
    s = (((s mod m)*(128 mod m)) mod m + string[i] mod m) mod m
return s

However, for $m>128$, some mod calculations simplify and our largest possible value is 128*(m-1). Thus to avoid overflow we should have

$128(m-1) \leq 2^{32}-1$

$m \leq 2^{25} + 127/128$

What am I doing wrong here?

$\endgroup$

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.