1
$\begingroup$

(I know that a Rabin fingerprint is not a cryptographic hash, sorry in advance if my question is considered out of topic)

In the paper Some applications of Rabin's fingerprinting method, it is written that implementations should prefix the data to hash by a '1' value.

Does anybody know why?

$\endgroup$

1 Answer 1

2
$\begingroup$

I think that it was to make sure that the leading zeroes in the data to hash are taken into account during the hash. Without the '1' prefix value, those leading zeroes would make the fingerprint stay to zero.

Without the '1' prefix, the following 2 list of bytes would have the same fingerprint:

[42, 5, 3]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 5, 3]
$\endgroup$
2
  • $\begingroup$ Rabin Fingerprints are defined for bitstrings, but 42 does not fit a bit. A better example would be the bitstrings 101 and 00101, which without prefix have identical Rabin fingerprint, but after prefix become 1101 and 100101, which have different Rabin fingerprints (for practical choice of the polynomial). $\endgroup$
    – fgrieu
    Jun 1, 2016 at 11:35
  • $\begingroup$ You are right. I should have mentioned that in my example I used bytes instead of bits. $\endgroup$
    – Vincent
    Jun 6, 2016 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.