Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
а доказательство? 07.12.02 15:45 Число просмотров: 3505
Автор: SemenU Статус: Незарегистрированный пользователь
|
> А почему бы просто не положить H[i](X) = f(i||X), где f > какая-нибудь фиксированная хэш-функция нужной размерности? > Т.е. приписываем i к данным X слева ("конкатинируем" i и > X), и от всего этого считаем значение f.
Да, подобная идея была в моей голове. Но я не такой спец в этом вопросе, и боюсь я, что не сработает это. Тут все начинает зависеть от f, не так ли?
Например, пусть f(X) = X % P (остаток от деления X на P). Пусть все X одной длины.
i|X обобщим как A*i + B*X.
H[i](X) = (A*i + B*X) % P
Поищем H[n](X) - H[m](X) по модулю P:
((A*n + B*X) % P - (A*m +B*X) % P) = (A*(n-m)) mod P, т.е.
H[n](X) == H[m](X) + (A*(n-m) % P) + t*P, где t 0, 1 или -1
Вобщем нужны функции, которые бы друг через друга очень сложно выражались...
А лучше никак :), только не понятно, что это значит...
Но, определенно, если взять H[i](X) := A % Pi, и Pi попарно различные простые, тогда все намного лучше! Правильно?
Кто нибудь представляет себе, что будет, если f - это MD5? Можно ли выразить
значение MD5(A*x + B) через MD5(x)? Хмм... Сам подумал и кажется, что нет... Или да?
|
|
|