Мне любопытно, есть ли способ хранить хэш из нескольких множеств целых чисел, который в идеале имеет следующие свойства: Использует пространство O (1) Его можно обновить, чтобы отразить вставку или удаление за время O (1). Две идентичные коллекции (т. Е. Коллекции, имеющие одинаковые элементы с...
Википедия определяет вторую атаку прообразом как: учитывая фиксированное сообщение m1, найдите другое сообщение m2, такое что hash (m2) = hash (m1). Википедия определяет атаку столкновением как: найдите два произвольных разных сообщения m1 и m2, таких что hash (m1) = hash (m2). Единственное...
Часто говорят, что при использовании алгоритма MD5 для подписания некоторой произвольной информации общий секрет должен быть в конце.
При реализации фильтра Блума традиционный подход требует нескольких независимых хеш-функций. Кирш и Митценмахер показали, что на самом деле вам нужно только два, а остальные можно сгенерировать как линейные комбинации. Мой вопрос: в чем на самом деле разница между двумя хэш-функциями и одной с...
Рассмотрим простой односвязный список в чисто функциональной обстановке. Его похвалы пели с горных вершин и будут продолжать петь. Здесь я расскажу об одной из его сильных сторон и о том, как ее можно распространить на более широкий класс чисто функциональных последовательностей, основанных на...
В хеш-таблицах, которые разрешают коллизии линейным зондированием, для обеспечения ожидаемой производительности необходимо и достаточно, чтобы хеш-функция была из 5-независимого семейства. (Достаточность: «Линейное зондирование с постоянной независимостью», Паг и др. , Необходимость: «О...
Если шаров равномерно размещены в n корзинах случайным образом, то в самой тяжелой загруженной корзине с высокой вероятностью будет O ( lg n / lg lg n ) шариков. В «Сложности простого хэширования табуляции» Патрашку и Торуп упоминают, что «границы Черноффа-Хёффдинга для приложений с ограниченной...
Существует ли класс алгоритмов хеширования, теоретический или практический, такой, чтобы алгоритм в классе можно было считать «рефлексивным» согласно определению, данному ниже: hash1 = algo1 ("текст ввода 1") hash1 = algo1 («входной текст 1» + hash1) Оператор + может быть конкатенацией или любой...
Безопасность SHA-1 обсуждалась с тех пор, как алгоритм обнаружения столкновений был впервые опубликован в CRYPTO 2004 и впоследствии был улучшен. В Википедии перечислено несколько ссылок , однако, похоже, что последнее исследование, опубликованное (и позднее отозванное) по этому вопросу, было в...
Я ищу хэш-функцию над множествами H (.) И отношением R (.,.), Чтобы, если A входит в B, то R (H (A), H (B)). Конечно, R (.,.) Должно легко проверяться (постоянное время), а H (A) должно вычисляться за линейное время. Одним из примеров H и R является: ЧАС( А ) = ⋁x ∈ A1 < < ( ч ( х...
Я прочитал немного о следующих структурах данных: Бэгвелла идеальные попытки хэша Динамические хеш-таблицы Ларсона Красно-черные деревья Патриция деревья ... и я уверен, что есть много других. Я очень мало видел в том, для чего каждый из них лучше подходит, или почему я бы выбрал одно из другого....
Я ищу структуру данных, то есть в основном дерево карт, где карта в каждом узле содержит несколько новых элементов, а также элементы в карте своего родительского узла. Под картой здесь я подразумеваю карту программирования с ключами и значениями, например карту в STL или dict в python. Например,...
Википедия - SHA-2 говорит SHA-224 идентичен SHA-256, за исключением того, что: начальные значения переменных от h0 до h7 различны, и выход строится путем пропуска h7. RFC3874 - 224-битная односторонняя хэш-функция: SHA-224 говорит Использование другого начального значения гарантирует, что усеченное...
При интерпретации ключей как натуральных чисел мы можем использовать следующую формулу. h(k)=⌊m(kAmod1)⌋h(k)=⌊m(kAmod1)⌋\begin{equation} h(k) = \lfloor m (kA\bmod{1}) \rfloor \end{equation} Что мне трудно понять, так это то, как мы выбираем значение A, где: 0<A<10<A<1\begin{equation} 0...
Вот два семейства хеш-функций на строках x⃗ =⟨x0x1x2…xm⟩x→=⟨x0x1x2…xm⟩\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle: За ppp премьер и xi∈Zpxi∈Zpx_i \in \mathbb{Z_p}, h1a(x⃗ )=∑aiximodpha1(x→)=∑aiximodph^1_{a}(\vec{x}) = \sum a^i x_i \bmod pдля . Dietzfelbinger et al. в «Полиномиальные хеш-функции...