Відбитки пальців Рабіна

Схема відбитків пальців Рабіна — є методом для реалізації відбитків пальців з використанням поліномів над скінченним полем. Її запропонував Міхаель Ошер Рабін.

Система

Враховуючи n-ий ряд m₀,...,m_n-1, ми розглядаємо його як многочлен степеня n-1 над скінченним полем.

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

Тоді ми обираємо довільний незвідний многочлен $p(x)$ зі степенем k над скінченним полем, і ми визначаємо, що ідентифікаційна мітка m є залишком $r(x)$ після поділу $f(x)$ за допомогою $p(x)$ над скінченним полем, який можна розглядати як многочлен степеня k − 1 або як k-те число.

Застосування

Багато реалізацій алгоритму Рабіна — Карпа використовують всередині своєї послідовності відбитки пальців Рабина.

Система "лексикографічного пошуку у ширину" (LBFS) від Массачусетського технологічного інституту MIT використовує відбитки пальців Рабіна для реалізації блоків, стійких до зміни розміру. Основна ідея полягає в тому, що файлова система обчислює криптографічний геш кожного блоку в файлі. Для збереження при переказах між клієнтом і сервером вони порівнюють свої контрольні суми і тільки блоки передачі, чиї контрольні суми відрізняються. Але однією з проблем цієї схеми є те, що одна вставка на початку файлу призведе до того, що кожна контрольна сума буде змінюватися, якщо використовуються блоки фіксованого розміру (наприклад, 4 КБ). Отже, ідея полягає в тому, щоб вибрати блоки не на основі конкретного зсуву, а скоріше за деякою властивістю блоку. LBFS робить це, пересуваючи 48-байтове вікно над файлом і обчислюючи Відбитки пальців Рабіна кожного вікна. Коли низькі 13 біт відбитків пальців дорівнює нулю LBFS називає ці 48 байт точкою зупинки і завершує поточний блок і починає новий. Оскільки результат відбитків пальців Рабіна є псевдовипадковим, ймовірність будь-якого заданого 48 байта, що є кінцевою, становить $2^{-13}$ (1 в 8192). Це має ефект стійких до зміщення блоків змінних розмірів. Будь-яка хеш-функція може бути використана для поділу довгого файлу на блоки (поки криптографічна геш-функція використовується для знаходження контрольної суми кожного блоку): але Відбитки пальців Рабіна є ефективним котковим гешем, оскільки обчислення відбитків пальців Рабіна околуB може повторно використати деякі обчислення відбитків пальців Рабіна області A коли околи A та B перетинаються.

Зауважте, що це проблема, подібна до проблеми, з якою зіткнулася rsync.

Дивись також

• Алгоритм шинглів
• Коткий геш

Зовнішні посилання

• Andrei Z. Broder (1993). Some applications of Rabin's fingerprinting method: 143—152. Процитовано 12 вересня 2011.
• David Andersen (2007). Exploiting Similarity for Multi-Source Downloads using File Handprints. Процитовано 12 квітня 2007.
• Ross N. Williams (1993). "A painless guide to CRC Error detection algorithms".