Как повысить точность отпечатков пальцев Рабина

Question

Ниже приведена очень быстрая и элегантная Java-реализация отпечатка пальца Рабина https://github.com/themadcreator/rabinfingerprint

Однако самый большой многочлен, который может использоваться в оптимизированной реализации, составляет 54 бита.

Я хочу уменьшить вероятность ошибки.

Рабин [1] предлагает два способа снизить вероятность ошибки: • Вероятность неправильного вывода будет уменьшена при увеличении значения k. Это потребует большей длины слова. • Вероятность также можно снизить, используя два разных неприводимых многочлена P1(t) и P2(t) одинаковой степени k. Затем алгоритм запускается дважды путем чередования шагов, один раз с P1(t) и другой раз с P2(t). Поскольку вероятности ошибки являются независимыми.... (из CMPUT690 Term Project)

Если я запускаю алгоритм дважды, как мне объединить 2 отпечатка пальца, не подрывая мою цель уменьшить вероятность ошибки?

• просто добавить или несколько 2 отпечатков пальцев?
• использовать вывод первого прогона в качестве базового отпечатка второго прогона?

Мне не ясно, что такое "этапы чередования". Мне нужно сохранить отпечаток как 64-битный номер.

Благодарю.

Answer 1

Ты не можешь Рабин предлагает дважды запустить алгоритм с разными неприводимыми полиномами, а затем объединить выходные данные, что даст вам 108 бит в вашем случае. Дело в том, что нет способа сжать это до 64 бит, не отбрасывая большую часть уменьшения ошибок: по принципу "голубиных отверстий" абсолютная наименьшая вероятность ошибки, на которую вы могли бы рассчитывать с любым алгоритмом,

• около 1/2^56, когда вы используете 56-битный отпечаток
• около 1/2^64 при использовании 64-битного отпечатка
• около 1/2^128 при использовании 128-битного отпечатка

и поскольку алгоритм Рабина приближается к этим границам, переход от 54 до 64-битного отпечатка пальца даст не более ~2^10 = ~1000-кратное уменьшение ошибки.

Однако, если это улучшение стоит вашего времени, лучше всего рассчитать два 54-битных отпечатка пальца, отбросить 20 бит высшего порядка из каждого из них (чтобы получить два 32-битных отпечатка пальца), а затем объединить их, чтобы получить 64 отпечаток пальца.