Rabin fingerprint
The Rabin fingerprinting scheme is a method for implementing fingerprints using polynomials over a finite field. It was proposed by Michael O. Rabin.[1]
Scheme
Given an n-bit message m0,...,mn-1, we view it as a polynomial of degree n-1 over the
We then pick a random irreducible polynomial of degree k over GF(2), and we define the fingerprint of the message m to be the remainder after division of by over GF(2) which can be viewed as a polynomial of degree k − 1 or as a k-bit number.
Applications
Many implementations of the Rabin–Karp algorithm internally use Rabin fingerprints.
The Low Bandwidth Network Filesystem (LBFS) from MIT uses Rabin fingerprints to implement variable size shift-resistant blocks.[2] The basic idea is that the filesystem computes the
Note that this is a problem similar to that faced by
See also
References
- ^ Michael O. Rabin (1981). "Fingerprinting by Random Polynomials" (PDF). Center for Research in Computing Technology, Harvard University. Tech Report TR-CSE-03-01. Retrieved 2007-03-22.
- David Mazières"A Low-bandwidth Network File System"
External links
- Andrei Z. Broder (1993). "Some applications of Rabin's fingerprinting method". pp. 143–152. Retrieved 2011-09-12.
- David Andersen (2007). "Exploiting Similarity for Multi-Source Downloads using File Handprints". Retrieved 2007-04-12.
- Ross N. Williams (1993). "A painless guide to CRC Error detection algorithms".