Почему по модулю 65521 в алгоритме контрольной суммы Adler-32?
Алгоритм контрольной суммы Adler-32 суммирует по модулю 65521. Я знаю, что 65521 - это наибольшее простое число, которое умещается в 16 битах, но почему важно использовать простое число в этом алгоритме?
(Я уверен, что ответ будет очевиден, когда кто-то скажет мне, но части мозга с теорией чисел просто не работают. Даже без опыта в алгоритмах контрольной суммы, умный человек, который читает http://en.wikipedia.org/wiki/Fletcher%27s_checksum может объяснить это мне.)
6 ответов
Почему мод премьер использовался для Adler32?
С собственного сайта Адлера http://zlib.net/zlib_tech.html
Однако Adler-32 был сконструирован так, чтобы минимизировать способы внесения небольших изменений в данные, которые приводят к одному и тому же контрольному значению, за счет использования сумм, значительно превышающих байты, и использования простого числа (65521) для модуля. Именно в этой области некоторый анализ заслуживает, но это еще не было сделано.
Основная причина Adler-32, конечно, скорость в реализации программного обеспечения.
Альтернативой Adler-32 является Fletcher-32, который заменяет модуль 65521 на 65535. Этот документ показывает, что Fletcher-32 лучше для каналов с низкоскоростными случайными битовыми ошибками.
Он был использован, потому что простые числа имеют тенденцию иметь лучшие свойства смешивания. Насколько это хорошо, еще предстоит обсудить.
Другие объяснения
Кто-то еще в этой теме делает несколько убедительный аргумент, что модуль простого числа лучше обнаруживать смена битов. Однако, это, скорее всего, не так, потому что обмен битами происходит крайне редко. Две наиболее распространенные ошибки:
- Случайные перевороты (1 <-> 0) встречаются везде.
- Сдвиг битов (1 2 3 4 5 -> 2 3 4 5 или 1 1 2 3 4 5) распространен в сети
Большая часть замены битов вызвана случайными переворотами, которые выглядят как биты.
Коды исправления ошибок фактически разработаны, чтобы противостоять n-битным отклонениям. С сайта Адлера:
Правильно сконструированный CRC-n обладает приятным свойством, заключающимся в том, что ошибка всегда меньше чем n битов. Это не всегда верно для Adler-32- он может обнаружить все одно- или двухбайтовые ошибки, но может пропустить некоторые трехбайтовые ошибки.
Эффективность использования простого модуля
Я сделал длинную рецензию по существу на тот же вопрос. Почему по простому модулю?
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
Краткий ответ
Мы знаем намного меньше о простых числах, чем составные. Поэтому такие люди, как Кнут, начали их использовать.
Хотя это может быть правдой, что простые числа имеют меньшее отношение к большей части данных, которые мы хэшируем, увеличение размера таблицы / по модулю также уменьшает вероятность коллизии (иногда больше, чем какая-либо выгода от округления до ближайшего простого числа).
Вот график коллизий на ведро с 10 миллионами криптографически случайных целых чисел, сравнивающих мод 65521 против 65535.
Алгоритм Адлера-32 предназначен для вычисления
A = 1 + b1 + b2 + b3 + ...
а также
B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...
и сообщить о них по модулю м. Когда 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
А и В неизменны, потому что 2 * 3 = 4 * 0 = 2 * 0 = 4 * 3 (по модулю 6). Можно также поменять 2 и 5 на тот же эффект. Это более вероятно, когда таблица времен не сбалансирована - по модулю 5 эти изменения обнаруживаются. Фактически, единственный раз, когда простой модуль не может обнаружить единственный обмен, это когда два равных индекса mod m меняются местами (и если m большое, они должны быть далеко друг от друга!).^ Эта логика также может быть применена к взаимозаменяемым подстрокам.
Недостаток использования меньшего модуля состоит в том, что он будет несколько чаще выходить из строя на случайных данных; однако в реальном мире коррупция редко бывает случайной.
Доказательство: предположим, что мы меняем индексы i и j на значения a и b. Тогда ai + b j = aj + b i, поэтому ai - a j + bj - b i = 0 и (a - b)*(i - j) = 0. Поскольку поле является интегральной областью, из этого следует, что a = b (значения конгруэнтны) или i = j (индексы конгруэнтны).
РЕДАКТИРОВАТЬ: веб-сайт, на который ссылается Неизвестный ( http://www.zlib.net/zlib_tech.html), дает понять, что дизайн Adler-32 не был принципиальным. Из-за кода Хаффмана в потоке DEFLATE даже небольшие ошибки могут изменить кадрирование (поскольку оно зависит от данных) и вызвать большие ошибки в выводе. Считайте этот ответ слегка надуманным примером того, почему люди приписывают определенные свойства простым числам.
Короче:
Модуль простого числа обладает лучшими свойствами перетасовки битов, и это именно то, что мы хотим для хэш-значения.
Для совершенно случайных данных, чем больше блоков, тем лучше.
Допустим, данные не случайны в некотором роде. Теперь единственный способ, которым неслучайность может повлиять на алгоритм, - это создать ситуацию, когда одни сегменты имеют более высокую вероятность использования, чем другие.
Если число по модулю не простое, то любой шаблон, влияющий на одно из чисел, составляющих модуль, может повлиять на хеш. Поэтому, если вы используете 15, шаблон каждые 3 или 5, а также каждые 15 может вызвать коллизии, в то время как если вы используете 13, шаблон должен быть каждые 13, чтобы вызвать коллизии.
65535 = 3 * 5 * 17 * 257, поэтому шаблон, включающий 3 или 5, может вызвать коллизии с использованием этого модуля - если кратные значения 3 были более распространены по какой-либо причине, например, тогда только сегменты, кратные 3, будут найти хорошее применение.
Теперь я не уверен, реально ли это может быть проблемой. Было бы хорошо определить частоту столкновений эмпирически, используя реальные данные типа, который нужно хэшировать, а не случайные числа. (Например, могут ли числовые данные, относящиеся к http://en.wikipedia.org/wiki/Benford's_law"> закону Бэнфорда, или какие-то подобные шаблоны нерегулярности вызывать этот алгоритм? Как насчет использования кодов ASCII для реалистичного текста?)
Контрольные суммы обычно используются с целью обнаружения того, что две вещи различны, особенно в тех случаях, когда обе вещи не доступны одновременно и в одном месте. Они могут быть доступны в разных местах (например, пакет информации при отправке, в сравнении с пакетом информации при получении) или в разное время (например, блок информации, когда она была сохранена, по сравнению с блоком информации, когда она была прочитана), В некоторых случаях может быть желательно проверить, могут ли совпадать две вещи, которые хранятся независимо в двух разных местах, без необходимости отправлять фактические данные с одного устройства на другое (например, сравнивая загруженные кодовые изображения или конфигурации).
Если единственными причинами, по которым сравниваемые вещи не будут совпадать, будет случайное искажение одной из них, то использование простого модуля для контрольной суммы Adler-32, вероятно, не особенно полезно. Однако, если возможно, что одна из вещей могла иметь некоторые "преднамеренные" изменения, внесенные в нее, использование непростого модуля может привести к тому, что некоторые изменения останутся незамеченными. Например, эффекты изменения байта с 00 на FF и изменения другого байта, кратного 257 байтам ранее или позже с FF на 00, будут отменены при использовании контрольной суммы Флетчера, но не при использовании контрольной суммы Adler-32. Маловероятно, что такой сценарий может произойти из-за случайного повреждения, но такие смещающие изменения могут произойти при изменении программы. Маловероятно, что они будут иметь точное кратное 257 байт, но это риск, которого можно избежать, используя простой модуль (при условии, что, по крайней мере, число байтов в файле меньше, чем модуль)
Ответ лежит в теории поля. Множество 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.
Это свойство отвечает за лучшее распределение хеш-значений.