Речь шла про обычный полиномиальный хеш.

Для идеального вы правы.

Полиномиальные хеши ИМХО не очень качественные. Надо как-то еще биты перемешивать. Да и еще диапазон величин такого хеша должен быть простым числом, что не очень удобно в большинстве случаев.

Хеш всегда по модулю берется

Там уже мало зависит что-то от того, что это полином

То есть полином в поле GF(p) не полином?))

Я, к сожалению, не знаю про поля. При чем это тут?

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

Ну если есть значимый шанс, что хеш обратится в 0, то вообще нет смысла в полиномиальной хешировании

Предполагается, что 2^k сильно больше n. Человек же не про теорию спрашивал

Человеку не понравилось, что на кф ему все советуют полиномиальный хеш, вы сказали, что коллизии не зависят от размера входных данных, что для полиномиальных хешей (как минимум) неправда, что я вам и ответил.

Согласен, я не прав

Тут важно понимать, в каком порядке стоят кванторы и в каком смысле считается вероятность.

Если фиксировать основание многочлена, а входные данные будут случайны, то вероятность коллизии всегда будет 1/M независимо от их величины, потому что у случайного многочлена в среднем один корень (лёгкое доказательство: из многочленов P(x)*x+0, P(x)*x+1, ..., P(x)*x+(M-1) ровно один зануляется на данном конкретном значении x).

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

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

Вопрос со звёздочкой: какое будет семейство, если мы говорим, например, об md5?

Добрый вечер, подскажите с чего и где начать изучения алгоритмов :)

Проще всего книгу купить в магазине.

А какую?

Любую по наличию. Не слежу за литературой.

Купи то, не знаю что)