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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Определение
 
{{Определение
 
|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>}}
 
|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>}}

Текущая версия на 11:44, 1 сентября 2022

Определение:
[math] H_{n, k} = \{ h | h: 2^n \to 2^k \}[/math] называется семейством универсальных попарно независимых хеш-функций, если для [math] \forall x_1, x_2 \in 2^n, x_1 \ne x_2[/math] и [math] \forall y_1, y_2 \in 2^k[/math] и равномерной выборки функции [math] h \in H_{n, k} [/math] будет выполнено [math]P(h(x_1) = y_1 \land h(x_2) = y_2) = \frac{1}{2^{2k}}[/math]


Лемма:
Для любого [math]n \in N [/math] существует [math]H_{n, n}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим функцию [math] h_{a, b} = ((ax+b)\ mod\ p)\ mod\ 2^n[/math] для простого [math]p \in (2^n; 2^{n+1}][/math], любых [math]a, b \in \mathbb{Z}_p[/math], [math]a \ne 0[/math]

Для [math]r=(ax_1+b)\ mod\ p[/math] и [math]s=(ax_2+b)\ mod\ p[/math]

[math] P(r = r_1 \land s = s_1)= \frac{1}{p^2}[/math], где [math]r_1, s_1 \in [0; p)[/math].

Раз [math]p \in (2^n; 2^{n+1}][/math], то можно записать следующую оценку:

[math]\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 [/math]

[math] P(h(x_1)=y_1 \land h(x_2)=y_2) = \frac{1}{2^{2n}}[/math]

[math]h_{a, b} \in H_{n, n}[/math]
[math]\triangleleft[/math]


Теорема:
Для любых [math]n, k \in N[/math] существует [math]H_{n, k}[/math]
Доказательство:
[math]\triangleright[/math]

Построим [math]H_{n, k}[/math] следующим образом:

При [math]n=k[/math] существование [math]H_{n, k}[/math] следует из леммы.

При [math]n \gt k [/math] получим переменную [math] x' [/math] обрезав первые [math]n-k[/math] бит переменной [math]x[/math]. Тогда для переменной [math]x'[/math] существует [math]H_{k, k}[/math], а для [math]x[/math] - соответственно [math]H_{n, k}[/math].

При [math]n \lt k [/math] Сперва получим [math]H_{k, k}[/math]. [math]H_{n, k}[/math] можно получить отбросив у значений хеш-функций из [math]H_{k, k}[/math] первые [math]n-k[/math] бит.
[math]\triangleleft[/math]

См. также

Источники