\Section{Хеширование}{22 апреля}{Михаил Шавкунов}  
\Subsection{Хеши, теория}


\begin{Lm}

Количество корней случайного многочлена степени n над полем вычетов по модулю p. Ответ: 1.
	\begin{proof}
		У нас была лемма: $\forall a$ с вероятностью $\frac{1}{p}$ $a$ будет корнем многочлена. Всего чисел в поле: $p$.
		Поэтому имеем $N$ многочленов, $\frac{N}{p}$ пар, где $a$ -- корень.  \\ Т.е. фиксируем пару <a, p>. 
		Считаем количество корней: $\frac{\frac{N}{p} \cdot p}{N} = 1$. Взяли количество пар, где $a$ -- корень, умножили на количество чисел в поле и разделили на общее количество многочленов. 
	\end{proof}

\end{Lm}

На лекции было замечено, что мы пользуемся простотой модуля. Пример: пусть мы имеем многочлен $x^{64}$ по модулю $2^{64}$. Любое четное число является корнем этого многочлена. Таким образом, оно имеет аж $2^{63}$ корней, нам бы хотелось быть иметь 1 корень. Поэтому мы с большой долей вероятности тыкаемся в корень этого многочлена, т.е. какой-то символ в строке не особо вносит какой-то вклад. Т.е. меняем его и получаем другую строку, а хеш у нее такой же. 


\begin{Lm}

Зафиксируем пару <p, M>. Тогда рассмотрим вероятность : \\ $Pr = 1 - \frac{n(n - 1)}{2} \cdot Pr[Hash(s_1) == Hash(s_2)].$ \\
Тогда $Pr \leqslant \frac{|s|}{M}$ при фиксированных строчках и при случайных строчках имеем: $Pr = \frac{1}{M}$ \\
Т.е. это по сути вероятность совпадения хешей у двух строк одинаковой длины.
	\begin{proof}

		Рассмотрим разность строк $s_1$ и $s_2$ по модулю $p$ : $(s_1 - s_2)(p) == 0$. $p$ выбирается случайно.
		С какой вероятностью p является корнем многочлена? У нас многочлены выбираются случайно, значит по предыдущей лемме у них один корень в среднем.
		Тогда из предыдущих лемм у нас уже есть на это оценки. На лекции лемма, через которую следует первое утверждение обозначалась первой леммой. В конспекте у Никиты это Lm 31.2.4. Вторая лемма -- лемма 3 в лекции и в конспекте у Никиты она тоже идет следующей.

	\end{proof}
\end{Lm}

Замечание: несмотря на утверждение леммы, на практике мы имеем $\frac{1}{M}$.

\Subsection{Что есть в C++}

Напоминание в C++ есть unordered\_set<string> -- хеш таблица строк. Вычисляет хеш(ключ) и по нему уже запихивает в таблицу.

\begin{code}
std::hash<string> h;
auto p = h(s); 
\end{code}
Полиномиальный хеш, работает за длину строки. 
Т.к. работает в 32-ом режиме, есть коллизии.

\Subsection{Строка Туэ-Морса} 

Построим строку, на которой падает модуль $2^k$. Т.е. какое бы случайное $p$ мы бы не брали, все будет плохо. Хешом у нас будет: $\sum s_i \cdot p^i$ $mod$ $M.$ 
Где $M = 2^k, s_i \in \{0, 1\}$  \\

Два определения строки Туэ-Морса :

\begin{itemize}

\item s[i] = \_\_builtin\_popcount(i) mod 2. Т.е. количество единичных битов в двоичной записи числа i. \_\_builtin\_popcount(i) -- встроенная функция языка С++.
\item Строим рекурсивно. $s_n = s_{n - 1} + not$ $s_{n - 1}$. not -- инвертирование битов в строке s.

\end{itemize}

База: $s_0 = 0.$\\
Далее имеем следующее: $s_1 = 01, s_2 = 0110, s_3 = 01101001$ и тд. \\

Хотим найти для какой длины строки случится коллизия. Рассмотрим \\ $Hash(s_i) == Hash(\overline s_i)$ для достаточно большого i. Когда так произойдет? \\
Смотрим на разность $Hash(s_1) - Hash(\overline s_i) = 0$ \\ 
Это есть следующее: $\sum\limits_{j = 0}^{2^i - 1} p^j \cdot t_j$, где $t_j \in \{+1, -1\}$ -- соответствующий коэффициент. \\
Это равно $-(1 - p)(1 - p^2) \dots (1 - p^{2^i -1})$. Здесь i множителей. Понимать этот переход скорее всего нужно в обратную сторону. А именно, раскроем все скобки. Каждое слагаемое есть уникальная комбинация то что стоит в скобках. Т.е. мы из каждой скобки взяли единицу или степень двойки $p$. Таким образом итоговое слагаемое есть $p$ в какой-то степени. Эта степень есть сумма степеней двоек. А это двоичная запись какого-то числа, каждое число уникальное, получаем нужную сумму $p$-шек. \\
Далее нужно заметить, что $Hash(s_i) == Hash(\overline s_i)\cdot (1 - p^{2^i - 1})$ =  $Hash(s_{i + 1}) == Hash(\overline s_{i + 1})$. Т.к. $s_i - \overline s_i = s_{i - 1}\overline s_{i - 1}s_{i - 1}$ это расписано по определению. \\
Т.е. если мы введем функцию $f_i$ -- разность соотвествующих хешей, то она будет устроена так: $f_i = f_{i - 1} \cdot (1 - p^{2^i - 1})$ поскольку $|s_{i - 1}| = 2^{i - 1}$\\
Пусть $p$ -- четно. Тогда как было разобрано выше, это плохой хеш, поскольку начиная с некоторого места оно занулится. Т.е. у нас модуль -- степень двойки, а $p$-шка -- в какой-то большой степени, по этому модулю будет равно 0. Поэтому рассмотрим более содержательный случай с нечетным $p$. \\
Заметим, что  $(1 - p^4) = (1 - p^2)(1 + p^2) = (1 - p)(1 + p)(1 + p^2)$ \\
Каждая из скобок четная, т.е. имеет 1, 2, 3... i четных сомножителей. \\
Получаем $1 + 2 + \dots + i = \frac{i(i + 1)}{2}$. Мы хотим, чтобы $k \leqslant \frac{i(i + 1)}{2}$ это следует из неравенства: $\sqrt{2k} \leqslant i$. \\
Поэтому при $k$ = 64. $\sqrt{128} \leqslant i$. Значит, $i = 12$. $2^{i} = 4096$. Т.е. это длина строки на которой модуль упадет.

\Subsection{Алгоритм Капуна}

Построим антитест для фиксированной пары <p, M>. Пусть у нас алфавит будет состоять из единиц и нулей. $|s_1| = |s_2| = n$. Хотим $Hash(s_1) == Hash(s_2)$.  \\
Перейдем к разности.  $0 = Hash(s_1) - Hash(s_2) = \sum p^j \cdot t_j, где t_j \in \{-1, 0, +1\}.$ \\
Т.е. имеем некоторую сумму $p^i$, идея в том, чтобы найти коэффициенты такие, что эта сумма равна нулю по модулю M. \\
Положим $A_0 : \{p^0, p^1, \dots, p^{n-1}\}$. Если $A_0$ содержит ноль, тогда тест у нас есть.\\
А именно: пусть $p^i = 0$ $mod$ $M$, для некоторого i. \\
Тогда тест такой : строка $s_1 = 0\dots0\dots0$. И строка $s_2 = 0\dots1\dots0$. Эти строки различаются в i-ой позиции, в остальных совпадают.\\
Если нуля в множестве $A_i$ нет, тогда построим множество $A_{i + 1}$. Множество $A_i$ мы воспринимаем как массив, поэтому отсортируем по возрастанию. \\
Далее $A_{i + 1} = \{A_i[1] - A_i[0], A_i[3] - A_i[2] \dots\}$.  $|A_{i + 1}| = \frac{|A_i|}{2}$. Размер нового множества уменьшился в два раза. \\
Если у нас получилось 0 в множестве $A_i$ тогда мы победили. Почему? Представим себе полное бинарное дерево. Каждый лист которого есть уникальная степень $p$.\\
Тогда напишем на ребре +1, если соединяем вершину с левым сыном и -1 если соединяем с правым. Корень дерева имеет высоту $i + 1$. Что означают эти странные цифры на ребрах? Собственно, они служат для определения коэффициента соответствующего $p^j$. Конкретнее: рассмотрим путь от корня до листа, перемножим числа на пути и получим с каким коэффициентом мы берем каждое $p^j$. Почему это так? Мы же имеем $A_i[a] - A_i[a - 1] = 0$. Что такое $A_i[a]$? Это то что мы взяли со знаком +1, а $A_i[a - 1]$ со знаком минус. Это соотвествует двум ребрам в дереве, для этих двух вершин уже все посчитано, мы просто поменяли знак там, где нужно.\\ 

Иллюстрация к этому. \\
\includegraphics[scale=0.4]{shavkunov/2.jpg} 

Собственно, мы получили, что хотели : некоторую сумму $p$-шек равную нулю по модулю M. Что с этим делать? Возьмем все $p$-шки со знаком + и оставим их в левой части, $p$-шки со знаком - перенесем в правую часть. Тогда алгоритм такой : смотрим на левую часть, напишем в строке $s_1$ единицу на $i$-ой позиции, если слагаемое $p^i$ присутствует в левой части, иначе напишем 0. Правило для правой части такое же, т.е. правая часть аналогичным образом задает строку $s_2$. Одна из этих строк есть инвертированная версия другой. \\

Пример. Пусть мы получили сумму такую: $p^0 - p^1 - p^2 + p^3 = 0$ $mod$ $M$  $\Longleftrightarrow$ \\
$p^0 + p^3 = p^1 + p^2$ \\
$s_1 = 1001$\\
$s_2 = 0110$ \\

Конец алгоритма. Строгого доказательства этого не было. Поэтому тут некоторые его наброски. \\
Каждый раз при построении множества $A_i$ его размеры уменьшаются в два раза. Что можно сказать о диапазоне чисел? Для $A_0$ диапазон был таким : $0, \dots, M - 1$.\\
Диапазон $A_1 \sim \frac{M}{n + 1}$, где $n$ - количество чисел в $A_0$. Почему так? А фиг его знает. Сережа сказал, что разность соседних случайных чисел до M оценивается именно так.\\
Диапазон $A_2 \sim \frac{M}{(n + 1)(\frac{n}{2} + 1)}.$ И так далее. Для $A_i$ диапазон будет делиться на $\frac{n}{2^{i - 1}} + 1$ \\
На пальцах объяснение такое: диапазон схлопнется быстрее, чем размер множества $A_i$ станет нулем, т.е. для каждой пары <p, M> мы гарантированно можем вычиcлить антихеш тест.\\

Оценим длину строки, которую мы хотим взять.\\

$M \leqslant \frac{n}{1} \cdot \frac{n}{2} \cdot \frac{n}{2} \cdot \frac{n}{4} \cdot \frac{n}{8} \dots$ То что написано справа -- это есть изменение диапазона. Возьмем для простоты $M = 2^m$. \\
Тогда: $n = 2^k = 2^{\sqrt{2m}}$. Про это следует заметить, что длина строки совпадает с длиной строки Туэ-Морса.\\
В общем случае делается так: $M \leqslant \frac{n}{1} \cdot \frac{n}{2} \cdot \frac{n}{2} \cdot \frac{n}{4} \cdot \frac{n}{8} \dots \sim 
\frac{n^{\log n}}{2^{\frac{(\log n)^2}{2}}} =
\frac{2^{(\log n)^2}}{2^{\frac{(\log n)^2}{2}}} = 
2^{\frac{(\log n)^2}{2}} \\ \Longleftrightarrow M = 2^{\frac{(\log n)^2}{2}} \Longleftrightarrow \log M 
= \frac{(\log n)^2}{2} \Longleftrightarrow \log n = \sqrt{2\log M} \Longleftrightarrow n = 2^{\sqrt{2\log M}}$. \\
Подставляя сюда $M = 2^k$ получаем результат, который был выше.

