Редактирование: Семейство универсальных попарно независимых хеш-функций

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
{{Определение
+
==Определение==
|definition=<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется '''семейством универсальных попарно независимых хеш-функций''', если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>}}
+
<tex> H_{n, k} = \{ h | h: 2^n \to 2^k \}</tex> называется семейством универсальных попарно независимых хеш-функций, если для <tex> \forall x_1, x_2 \in 2^n, x_1 \ne x_2</tex> и <tex> \forall y_1, y_2 \in 2^k</tex> и равномерной выборки функции <tex> h \in H_{n, k} </tex> будет выполнено <tex>P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}</tex>
  
{{Лемма
+
==Лемма==
|statement=Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>
+
Для любого <tex>n \in N </tex> существует <tex>H_{n, n}</tex>
|proof= Рассмотрим функцию <tex> h_{a, b} = ((ax+b)\ mod\ p)\ mod\ 2^n</tex> для простого <tex>p \in (2^n; 2^{n+1}]</tex>, любых <tex>a, b \in \mathbb{Z}_p</tex>, <tex>a \ne 0</tex>
 
  
Для <tex>r=(ax_1+b)\ mod\ p</tex> и <tex>s=(ax_2+b)\ mod\ p</tex>
+
===Доказательство===
 +
Функция <tex>h_{a, b} \in H_{n, n}</tex>, где <tex> h_{a, b} = (ax+b)</tex> в поле <tex> \mathbb{F}_{2n}</tex> для любых <tex>a, b \in N</tex>
  
<tex> P(r = r_1 \land s = s_1)= \frac{1}{p^2}</tex>, где <tex>r_1, s_1 \in [0; p)</tex>.
+
==Теорема==
 +
Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>
  
Раз <tex>p \in (2^n; 2^{n+1}]</tex>, то можно записать следующую оценку:
+
===Доказательство===
  
<tex>\frac{1}{p^2} \left(\frac{p}{2^n} \right)^2 \leqslant P(r\ mod\ 2^n = y_1 \land s\ mod\ 2^n=y_2) \leqslant \frac{1}{p^2} \left( \frac{p}{2^n}+1 \right)^2 </tex>
+
Построим <tex>H_{n, k}</tex> следующим образом:
 
 
<tex> P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2n}}</tex>
 
 
 
<tex>h_{a, b} \in H_{n, n}</tex>
 
}}
 
 
 
 
 
{{Теорема
 
|statement=Для любых <tex>n, k \in N</tex> существует <tex>H_{n, k}</tex>
 
|proof=Построим <tex>H_{n, k}</tex> следующим образом:
 
  
 
При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.
 
При <tex>n=k</tex> существование <tex>H_{n, k}</tex> следует из леммы.
  
При <tex>n > k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{k, k}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.
+
При <tex>n < k </tex> получим переменную <tex> x' </tex> обрезав первые <tex>n-k</tex> бит переменной <tex>x</tex>. Тогда для переменной <tex>x'</tex> существует <tex>H_{n, n}</tex>, а для <tex>x</tex> - соответственно <tex>H_{n, k}</tex>.
 
 
При <tex>n < k </tex> Сперва получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить отбросив у значений хеш-функций из <tex>H_{k, k}</tex> первые <tex>n-k</tex> бит.
 
}}
 
 
 
== См. также ==
 
*[[Универсальное семейство хеш-функций]]
 
== Источники ==
 
*[https://ru.wikipedia.org/wiki/%D0%A3%D0%BD%D0%B8%D0%B2%D0%B5%D1%80%D1%81%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%85%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Wikipedia - Универсальное хеширование]
 
  
[[Категория: Хеширование]]
+
При <tex>n > k </tex> получим <tex>H_{k, k}</tex>. <tex>H_{n, k}</tex> можно получить, обрезав значение хеш-функции из <tex>H_{k, k}</tex>, на первые <tex>n-k</tex> бит.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: