Схема відбитків пальців Рабіна — є методом для реалізації відбитків пальців з використанням поліномів над скінченним полем. Її запропонував Міхаель Ошер Рабін.
Система
Враховуючи n-ий ряд m0,...,mn-1, ми розглядаємо його як многочлен степеня n-1 над скінченним полем.
Тоді ми обираємо довільний незвідний многочлен зі степенем k над скінченним полем, і ми визначаємо, що ідентифікаційна мітка m є залишком
після поділу
за допомогою
над скінченним полем, який можна розглядати як многочлен степеня k − 1 або як k-те число.
Застосування
Багато реалізацій алгоритму Рабіна — Карпа використовують всередині своєї послідовності відбитки пальців Рабина.
Система "лексикографічного пошуку у ширину" (LBFS) від Массачусетського технологічного інституту MIT використовує відбитки пальців Рабіна для реалізації блоків, стійких до зміни розміру. Основна ідея полягає в тому, що файлова система обчислює криптографічний геш кожного блоку в файлі. Для збереження при переказах між клієнтом і сервером вони порівнюють свої контрольні суми і тільки блоки передачі, чиї контрольні суми відрізняються. Але однією з проблем цієї схеми є те, що одна вставка на початку файлу призведе до того, що кожна контрольна сума буде змінюватися, якщо використовуються блоки фіксованого розміру (наприклад, 4 КБ). Отже, ідея полягає в тому, щоб вибрати блоки не на основі конкретного зсуву, а скоріше за деякою властивістю блоку. LBFS робить це, пересуваючи 48-байтове вікно над файлом і обчислюючи Відбитки пальців Рабіна кожного вікна. Коли низькі 13 біт відбитків пальців дорівнює нулю LBFS називає ці 48 байт точкою зупинки і завершує поточний блок і починає новий. Оскільки результат відбитків пальців Рабіна є псевдовипадковим, ймовірність будь-якого заданого 48 байта, що є кінцевою, становить (1 в 8192). Це має ефект стійких до зміщення блоків змінних розмірів. Будь-яка хеш-функція може бути використана для поділу довгого файлу на блоки (поки криптографічна геш-функція використовується для знаходження контрольної суми кожного блоку): але Відбитки пальців Рабіна є ефективним котковим гешем, оскільки обчислення відбитків пальців Рабіна околуB може повторно використати деякі обчислення відбитків пальців Рабіна області A коли околи A та B перетинаються.
Зауважте, що це проблема, подібна до проблеми, з якою зіткнулася rsync.
Дивись також
Посилання
- Michael O. Rabin (1981). Fingerprinting by Random Polynomials (PDF). Center for Research in Computing Technology, Harvard University. Tech Report TR-CSE-03-01. Процитовано 22 березня 2007.
- Athicha Muthitacharoen, Benjie Chen, and "A Low-bandwidth Network File System"
Зовнішні посилання
- 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".
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Shema vidbitkiv palciv Rabina ye metodom dlya realizaciyi vidbitkiv palciv z vikoristannyam polinomiv nad skinchennim polem Yiyi zaproponuvav Mihael Osher Rabin SistemaVrahovuyuchi n ij ryad m0 mn 1 mi rozglyadayemo jogo yak mnogochlen stepenya n 1 nad skinchennim polem f x m 0 m 1 x m n 1 x n 1 displaystyle f x m 0 m 1 x ldots m n 1 x n 1 Todi mi obirayemo dovilnij nezvidnij mnogochlen p x displaystyle p x zi stepenem k nad skinchennim polem i mi viznachayemo sho identifikacijna mitka m ye zalishkom r x displaystyle r x pislya podilu f x displaystyle f x za dopomogoyu p x displaystyle p x nad skinchennim polem yakij mozhna rozglyadati yak mnogochlen stepenya k 1 abo yak k te chislo ZastosuvannyaBagato realizacij algoritmu Rabina Karpa vikoristovuyut vseredini svoyeyi poslidovnosti vidbitki palciv Rabina Sistema leksikografichnogo poshuku u shirinu LBFS vid Massachusetskogo tehnologichnogo institutu MIT vikoristovuye vidbitki palciv Rabina dlya realizaciyi blokiv stijkih do zmini rozmiru Osnovna ideya polyagaye v tomu sho fajlova sistema obchislyuye kriptografichnij gesh kozhnogo bloku v fajli Dlya zberezhennya pri perekazah mizh kliyentom i serverom voni porivnyuyut svoyi kontrolni sumi i tilki bloki peredachi chiyi kontrolni sumi vidriznyayutsya Ale odniyeyu z problem ciyeyi shemi ye te sho odna vstavka na pochatku fajlu prizvede do togo sho kozhna kontrolna suma bude zminyuvatisya yaksho vikoristovuyutsya bloki fiksovanogo rozmiru napriklad 4 KB Otzhe ideya polyagaye v tomu shob vibrati bloki ne na osnovi konkretnogo zsuvu a skorishe za deyakoyu vlastivistyu bloku LBFS robit ce peresuvayuchi 48 bajtove vikno nad fajlom i obchislyuyuchi Vidbitki palciv Rabina kozhnogo vikna Koli nizki 13 bit vidbitkiv palciv dorivnyuye nulyu LBFS nazivaye ci 48 bajt tochkoyu zupinki i zavershuye potochnij blok i pochinaye novij Oskilki rezultat vidbitkiv palciv Rabina ye psevdovipadkovim jmovirnist bud yakogo zadanogo 48 bajta sho ye kincevoyu stanovit 2 13 displaystyle 2 13 1 v 8192 Ce maye efekt stijkih do zmishennya blokiv zminnih rozmiriv Bud yaka hesh funkciya mozhe buti vikoristana dlya podilu dovgogo fajlu na bloki poki kriptografichna gesh funkciya vikoristovuyetsya dlya znahodzhennya kontrolnoyi sumi kozhnogo bloku ale Vidbitki palciv Rabina ye efektivnim kotkovim geshem oskilki obchislennya vidbitkiv palciv Rabina okoluB mozhe povtorno vikoristati deyaki obchislennya vidbitkiv palciv Rabina oblasti A koli okoli A ta B peretinayutsya Zauvazhte sho ce problema podibna do problemi z yakoyu zitknulasya rsync Divis takozhAlgoritm shingliv Kotkij geshPosilannyaMichael O Rabin 1981 Fingerprinting by Random Polynomials PDF Center for Research in Computing Technology Harvard University Tech Report TR CSE 03 01 Procitovano 22 bereznya 2007 Athicha Muthitacharoen Benjie Chen and A Low bandwidth Network File System Zovnishni posilannyaAndrei Z Broder 1993 Some applications of Rabin s fingerprinting method 143 152 Procitovano 12 veresnya 2011 David Andersen 2007 Exploiting Similarity for Multi Source Downloads using File Handprints Procitovano 12 kvitnya 2007 Ross N Williams 1993 A painless guide to CRC Error detection algorithms