Почему по модулю 65521 в Адлере 32 алгоритма контрольной суммы?
Небольшой вариант ответа Шона Чина , который также затрагивает последующую проблему , поднятую mpouncett - накладывает часы , минуты и секунды с ведущими нулями, чтобы все 3 элемента использовали 2 места (более соответствует спецификации для этих полей в strftime ):
from string import Template
class DeltaTemplate(Template):
delimiter = "%"
def strfdelta(tdelta, fmt):
d = {"D": tdelta.days}
hours, rem = divmod(tdelta.seconds, 3600)
minutes, seconds = divmod(rem, 60)
d["H"] = '{:02d}'.format(hours)
d["M"] = '{:02d}'.format(minutes)
d["S"] = '{:02d}'.format(seconds)
t = DeltaTemplate(fmt)
return t.substitute(**d)
Вот тест некоторые выборочные значения:
from datetime import timedelta
for seconds in [0, 1, 59, 60, 61, 3599, 3600, 3601]:
print strfdelta(timedelta(0, seconds), '%H:%M:%S')
А вот и вывод:
00:00:00
00:00:01
00:00:59
00:01:00
00:01:01
00:59:59
01:00:00
01:00:01
4 ответа
Почему для Adler32 использовался mod Prime?
С собственного веб-сайта Адлера http://zlib.net/zlib_tech.html
Однако Adler-32 был построен, чтобы минимизировать способы внести небольшие изменения в данные которые приводят к тому же контрольному значению, за счет использования сумм значительно больше байтов и с помощью простое число (65521) для модуля. Это в этой области заслужено, но еще не было сделано.
Основная причина появления Адлера-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 бит в ошибка всегда обнаруживается. Это не всегда верно для Адлера-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 простое, числа по модулю 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 эти изменения обнаруживаются. Фактически, единственный случай, когда простой модуль не может обнаружить одиночный обмен, - это когда два равных индекса по модулю 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 (индексы совпадают).
EDIT: веб-сайт, на который ссылается Неизвестный ( http://www.zlib.net/zlib_tech.html ), дает понять, что конструкция Адлера-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 для реалистичного текста?)
s Закон или какая-то такая нерегулярность вызывает закономерности, которые могут повлиять на этот алгоритм? Как насчет использования кодов ASCII для реалистичного текста?) s Закон или какая-то такая нерегулярность вызывает закономерности, которые могут повлиять на этот алгоритм? Как насчет использования кодов ASCII для реалистичного текста?)