ラビン指紋

ラビンフィンガープリンティング方式（別名多項式フィンガープリンティング）は、有限体上の多項式を使用してフィンガープリンティングを実装する方法です。これはマイケル・O・ラビンによって提案されました。^[1]

nビットのメッセージm ₀ ,..., m _{n -1}が与えられた場合、それを有限体GF(2)上の次数n -1の多項式として見なします。

${\displaystyle f(x)=m_{0}+m_{1}x+\ldots +m_{n-1}x^{n-1}}$

次に、 GF(2)上のk次の既約多項式を ランダムに${\displaystyle p(x)}$選び、メッセージmのフィンガープリントを、GF(2)上のmで割った余りと定義します。これは、 k − 1次の多項式またはkビットの数として見ることができます。 ${\displaystyle r(x)}$${\displaystyle f(x)}$${\displaystyle p(x)}$

Rabin-Karp アルゴリズムの多くの実装では、内部的に Rabin フィンガープリントが使用されます。

MIT のLow Bandwidth Network Filesystem ( LBFS) は、Rabin フィンガープリントを使用して、可変サイズのシフト耐性ブロックを実装しています。^[2] 基本的な考え方は、ファイルシステムがファイル内の各ブロックの暗号ハッシュを計算することです。クライアントとサーバー間の転送を節約するために、チェックサムを比較し、チェックサムが異なるブロックのみを転送します。ただし、この方式の問題の 1 つは、固定サイズ (例: 4 KB) のブロックが使用されている場合、ファイルの先頭に 1 回挿入するとすべてのチェックサムが変更されることです。そのため、特定のオフセットではなく、ブロックの内容の何らかのプロパティに基づいてブロックを選択するという考え方です。LBFS は、ファイル全体に 48 バイトのウィンドウをスライドさせ、各ウィンドウの Rabin フィンガープリントを計算することでこれを行います。フィンガープリントの下位 13 ビットがゼロの場合、LBFS はその 48 バイトをブレークポイントと呼び、現在のブロックを終了して新しいブロックを開始します。Rabin フィンガープリントの出力は疑似ランダムであるため、任意の 48 バイトがブレークポイントである確率は(1/8192) です。これには、シフト耐性のある可変サイズのブロックの効果があります。長いファイルをブロックに分割するために任意のハッシュ関数を使用できます (各ブロックのチェックサムを見つけるために暗号化ハッシュ関数が使用される限り) 。ただし、領域 A と領域 B が重複している場合、領域 B の Rabin フィンガープリントの計算で領域 A の Rabin フィンガープリントの計算の一部を再利用できるため、Rabinフィンガープリントは効率的なローリングハッシュです。 ${\displaystyle 2^{-13}}$

これはrsyncが直面する問題に似ていることに注意してください。^{[例が必要]}

• W-シングル
• ローリングハッシュ

• Andrei Z. Broder (1993) 「Rabin のフィンガープリント法のいくつかの応用」 pp. 143–152 。2011年 9 月 12 日閲覧。
• David Andersen (2007)。「ファイル ハンドプリントを使用したマルチソース ダウンロードの類似性の活用」。2007 年 4 月 12 日閲覧。
• Ross N. Williams (1993)。「CRC エラー検出アルゴリズムの簡単なガイド」