Почему по модулю 65521 в алгоритме контрольной суммы Adler-32?

Question

Алгоритм контрольной суммы Adler-32 суммирует по модулю 65521. Я знаю, что 65521 - это наибольшее простое число, которое умещается в 16 бит, но почему важно использовать простое число в этом алгоритме?

(Я уверен, что ответ кажется очевидным, когда кто-то скажет мне, но части мозга с теорией чисел просто не работают. Даже без опыта в алгоритмах контрольной суммы, умный человек, который читает http://en.wikipedia.org/wiki/Fletcher%27s_checksum может объяснить это мне.)

Answer 1

Почему мод премьер использовался для Adler32?

С собственного сайта Адлера http://zlib.net/zlib_tech.html

Однако, Адлер-32 был построен, чтобы минимизировать способы сделать небольшие изменения в данных этот результат в том же контрольном значении, благодаря использованию сумм значительно больше, чем байты и с помощью простое (65521) для модуля. Это в этой области, что некоторый анализ заслужил, но это еще не было сделано.

Основная причина Адлера-32 состоит в том, что Конечно, скорость в программном обеспечении Реализации.

Альтернативой Adler-32 является Fletcher-32, который заменяет модуль 65521 на 65535. Этот документ показывает, что Fletcher-32 лучше для каналов с низкими скоростями случайных битовых ошибок.

Он был использован, потому что простые числа имеют тенденцию иметь лучшие свойства смешивания. Насколько это хорошо, еще предстоит обсудить.

Другие объяснения

Кто-то еще в этой теме приводит несколько убедительные аргументы в пользу того, что модуль простого числа лучше обнаруживать смена битов. Однако, это, скорее всего, , а не , потому что обмен битами происходит крайне редко. Две наиболее распространенные ошибки:

1. Случайные перевороты (1 <-> 0) встречаются везде.
2. Сдвиг битов (1 2 3 4 5 -> 2 3 4 5 или 1 1 2 3 4 5), распространенный в сети

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

Коды исправления ошибок на самом деле предназначены для того, чтобы выдерживать n-битные отклонения. С сайта Адлера:

Правильно построенный CRC-n имеет Хорошее свойство, которое меньше, чем n бит ошибка всегда обнаруживается Это не всегда верно для Адлера-32 - может обнаружить все одно- или двухбайтовые ошибки, но может пропустить некоторые трехбайтовые ошибки.

Эффективность использования простого модуля

Я сделал длинную рецензию по существу на тот же вопрос. Почему по простому модулю?

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Краткий ответ

Мы знаем гораздо меньше о простых числах, чем составные. Поэтому такие люди, как Кнут, начали их использовать.

Несмотря на то, что простые числа имеют меньшую связь с большей частью данных, которые мы хэшируем, увеличение размера таблицы / по модулю также уменьшает вероятность коллизии (иногда больше, чем какая-либо выгода от округления до ближайшего простого числа).

Вот график коллизий в каждой группе с 10 миллионами криптографически случайных целых чисел, сравнивающих мод 65521 против 65535.

Answer 2

Алгоритм Адлера-32 должен вычислять

A = 1 + b1 + b2 + b3 + ...

и

B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...

и сообщить о них по модулю m. Когда m простое число, числа по модулю m образуют то, что математики называют полем . Поля имеют удобное свойство: для любого ненулевого c мы имеем a = b тогда и только тогда, когда c * a = c * b. Сравните таблицу времен по модулю 6, которая не является простым, с таблицей времен по модулю 5, которая:

* 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1

Теперь, часть A вводится в заблуждение всякий раз, когда мы меняем два байта - сложение в конце концов коммутативно. Предполагается, что часть B обнаруживает такую ​​ошибку, но когда m не простое число, больше мест уязвимо. Рассмотрим мод контрольной суммы Адлера 6

1 3 2 0 0 4

У нас A = 4 и B = 1. Теперь рассмотрим замену b2 и b4:

1 0 2 3 0 4

A и B неизменны, потому что 2 * 3 = 4 * 0 = 2 * 0 = 4 * 3 (по модулю 6). Можно также поменять 2 и 5 на тот же эффект. Это более вероятно, когда таблица времен не сбалансирована - по модулю 5 эти изменения обнаруживаются. Фактически, единственный раз, когда простой модуль не может обнаружить единственный обмен, это когда два равных индекса mod m меняются местами (и если m большое, они должны быть далеко друг от друга!). ^ Эта логика также может применяться к взаимозаменяемым подстрокам.

Недостатком использования меньшего модуля является то, что он будет несколько чаще давать сбой на случайных данных; однако в реальном мире коррупция редко бывает случайной.

^ Доказательство: предположим, что мы меняем индексы i и j на значения a и b. Тогда a i + b j = a j + b i, поэтому a i - a j + b j - b i = 0 и (a - b) * (i - j) = 0. Поскольку поле является интегральной областью, из этого следует, что a = b (значения конгруэнтны) или i = j (индексы конгруэнтны).

РЕДАКТИРОВАТЬ: веб-сайт, на который ссылается Неизвестный (http://www.zlib.net/zlib_tech.html), дает понять, что дизайн Adler-32 не был принципиальным. Из-за кода Хаффмана в потоке DEFLATE даже небольшие ошибки могут измените кадрирование (поскольку оно зависит от данных) и вызовите большие ошибки в выводе. Рассмотрите этот ответ как слегка надуманный пример того, почему люди приписывают определенные свойства простым числам.

Answer 3

Короче говоря:

Модуль простого числа обладает лучшими свойствами перетасовки битов, и это именно то, что нам нужно для хэш-значения.

Answer 4

Для совершенно случайных данных, чем больше сегментов, тем лучше.

Допустим, данные каким-то образом неслучайны. Теперь единственный способ, которым неслучайность может повлиять на алгоритм, - это создать ситуацию, когда одни сегменты имеют более высокую вероятность использования, чем другие.

Если число по модулю не простое, то любой шаблон, влияющий на одно из чисел, составляющих модуль, может повлиять на хеш. Поэтому, если вы используете 15, шаблон каждые 3 или 5, а также каждые 15 может вызвать коллизии, в то время как если вы используете 13, паттерн должен быть каждые 13, чтобы вызвать коллизии.

65535 = 3 * 5 * 17 * 257, поэтому шаблон, включающий 3 или 5, может вызвать столкновения, используя это по модулю - если кратные значения 3 были более распространенными по какой-то причине, например, то только сегменты, которые были кратны из 3 будет полезно.

Теперь я не уверен, реально ли это может быть проблемой. Было бы неплохо определить частоту столкновений эмпирически с фактическими данными, которые нужно хэшировать, а не случайными числами. (Например, могут ли числовые данные, связанные с http://en.wikipedia.org/wiki/Benford's_law">Benford's Law или какой-либо другой нерегулярностью, вызвать шаблоны, которые повлияют на этот алгоритм? Как насчет использования кодов ASCII для реалистичного текста?)

Answer 5

Ответ лежит в теории поля. Множество Z / Z_n с операциями плюс время и время - это поле, когда n - простое число (т.е. сложение и умножение по модулю n).

Другими словами, следующее уравнение:

m * x = (in Z/Z_n) 

имеет только одно решение для любого значения m (а именно x = 0)

Рассмотрим этот пример:

2 * x = 0 (mod 10)

Это уравнение имеет два решения: x = 0 И x = 5. Это потому, что 10 не является простым числом и может быть записано как 2 * 5.

Это свойство отвечает за лучшее распределение хеш-значений.

Answer 6

Контрольные суммы обычно используются с целью обнаружения, что две вещи различны, особенно в тех случаях, когда обе вещи не доступны одновременно и в одном месте. Они могут быть доступны в разных местах (например, пакет информации при отправке, в сравнении с пакетом информации при получении) или в разное время (например, блок информации, когда она была сохранена, по сравнению с блоком информации, когда она была прочитана) , В некоторых случаях может быть желательно проверить, могут ли совпадать две вещи, которые хранятся независимо в двух разных местах, без необходимости отправлять фактические данные с одного устройства на другое (например, сравнивая загруженные изображения кода или конфигурации).

Если единственными причинами, по которым сравниваемые вещи не будут совпадать, будет случайное искажение одной из них, то использование простого модуля для контрольной суммы Adler-32, вероятно, не особенно полезно. Однако, если возможно, что одна из вещей могла иметь некоторые «преднамеренные» изменения, внесенные в нее, использование непростого модуля может привести к тому, что некоторые изменения останутся незамеченными. Например, эффекты изменения байта с 00 на FF и изменения другого байта, кратного 257 байтам ранее или позже с FF на 00, будут отменены при использовании контрольной суммы Флетчера, но не при использовании контрольной суммы Adler-32. Маловероятно, что такой сценарий может произойти из-за случайного повреждения, но такие смещающие изменения могут произойти при изменении программы. Маловероятно, что они встречаются с точностью, кратной 257 байтам, но это риск, которого можно избежать с помощью простого модуля (при условии, что, по крайней мере, число байтов в файле меньше, чем модуль)