查看“︁拉宾指纹”︁的源代码

{{NoteTA
|G1 = IT
|1=zh-hans:有限域; zh-hant:有限體;
}}
'''拉宾指纹'''是一种在[[有限域]]上使用[[多项式]]实现{{tsl|en|Fingerprint (computing)|指纹（计算机）|指纹}}的方法。它是由[[迈克尔·拉宾]]提出的。
<ref>{{cite document |author=[[迈克尔·拉宾]] |title=Fingerprinting by Random Polynomials |publisher=Center for Research in Computing Technology, Harvard University |id=Tech Report TR-CSE-03-01 |year=1981 |url=http://www.xmailserver.org/rabin.pdf |accessdate=2007-03-22 |language=en |archive-date=2007-02-21 |archive-url=https://web.archive.org/web/20070221145951/http://www.xmailserver.org/rabin.pdf |dead-url=no }}</ref>
== 方案 ==

给定一个''n''位消息''m''<sub>0</sub>,...,''m''<sub>n-1</sub>，我们将其视为在[[有限域]][[有限域|GF(2)]]上的''n''-1次多项式。

:<math> f(x) = m_0 + m_1 x + \ldots + m_{n-1} x^{n-1} </math>

然后，我们随机选择一个在GF(2)上的''k次''[[不可约多项式]]{{tmath|p(x)}}，我们将消息''m''的指纹定义为在GF（2）上<math>f(x)</math>除以<math>p(x)</math>的余数<math>r(x)</math>，它可以看作是一个''k''-1次多项式或''k''位数字。

== 应用 ==

[[拉宾-卡普算法]]的许多实现，在内部是使用的拉宾指纹。

麻省理工学院的''低带宽网络文件系统''（LBFS）使用拉宾指纹来实现可变大小的抗移位块。<ref>Athicha Muthitacharoen, Benjie Chen, and David Mazières
 [http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf "A Low-bandwidth Network File System"] {{Wayback|url=http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf |date=20200203064543 }}</ref>

其基本思想是，文件系统计算文件中每个块的[[密碼雜湊函數|加密哈希]]。为了节省客户端和服务器之间的传输，它们比较其校验和，只传输校验和不同的块。但是这种方案有一个问题，就是如果使用固定大小（例如4KB）的块，那么在文件开头的一次插入将导致每个校验和都发生变化。因此，我们的想法是不基于特定的偏移量，而是根据块内容的某些属性来选择块。LBFS通过在文件上滑动48个字节的窗口并计算每个窗口的拉宾指纹来做到这一点。当指纹的低13位为零时，LBFS将这48个字节称为断点，并结束当前块、开始一个新的。由于拉宾指纹的输出是[[伪随机性|伪随机]]的，因此任何给定的48个字节为断点的概率为<math>2^{-13}</math>（8192分之1）。这就有了抗移位可变尺寸块的效果。''任何''[[散列函數|哈希函数]]都可以用于将一个长文件分成多个块（只要随后使用[[密碼雜湊函數|加密哈希函数]]查找每个块的校验和即可）：但是拉宾指纹是一种高效的[[旋转哈希]]，因为当区域''A''和''B''重叠时，区域''B''的拉宾指纹的计算可以重复使用区域''A''的拉宾指纹的部分计算。

请注意，这与[[rsync]]面临的问题相似。

== 参见 ==

* {{tsl|en|W-shingling|W-重迭}}
* [[旋转哈希]]

== 参考文献 ==

<references/>

== 外部链接 ==

* {{cite document |author=Andrei Z. Broder |year=1993 |title=Some applications of Rabin's fingerprinting method |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6172 |accessdate=2011-09-12 |archive-date=2016-03-04 |archive-url=https://web.archive.org/web/20160304112126/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.6172 |dead-url=no }}
* {{cite document |author=David Andersen |year=2007 |title=Exploiting Similarity for Multi-Source Downloads using File Handprints |url=https://www.cs.cmu.edu/~dga/papers/nsdi2007-set-abstract.html |accessdate=2007-04-12 |archive-date=2007-05-16 |archive-url=https://web.archive.org/web/20070516130639/http://www.cs.cmu.edu/~dga/papers/nsdi2007-set-abstract.html |dead-url=no }}
* Ross N. Williams (1993). "[http://www.zlib.net/crc_v3.txt A painless guide to CRC Error detection algorithms]{{Wayback|url=http://www.zlib.net/crc_v3.txt |date=20200430194956 }}".
[[Category:密码学理论]]
[[Category:指纹算法]]