Сложность в понимании нескольких шагов в доказательстве: «Класс $ \ mathscr {h} _ {p, m} $ of hash Функции универсален"

Question

Я проходил через текстовое введение в алгоритмы Cormen et. al. Там, где я наткнулся на следующий отрывок, касающийся указанных доказательств и шагов, где я испытывал трудности, отмечены $ \ janger $ и $ \ кинжал \ кинжал $ соответственно.

Проектирование универсального класса хеш-функций

$ p $ - это простое число, достаточно большое, чтобы каждый возможный ключ $ K $ Диапазон $ 0 $ на $ p - 1 $ , включительно. Пусть $ z_p $ обозначает множество $ \ {0, 1, ..., p - 1 \} $ , и пусть $ z_p ^ * $ обозначает множество $ \ {1, 2, ..., p - 1 \} $ . Известный предположением, что размер вселенной ключей больше, чем количество слотов $ m $ в таблице хэш, У нас есть $ P> M $ .

Теперь мы определяем хеш-функцию $ h_ {a, b} $ для любого $ a \ in z_p ^ * $ и любой $ b \ in z_p $ :

$ h_ {a, b}= ((a a a, b) \ mod p) \ mod m $ .

Семья всех таких хеш-функций:

$$ \ mathscr {h} _ {p, m}={h_ {a, b}: a \ in z_p ^ *, b \ in z_p \} $ $

---

Теорема: класс $ \ mathscr {h} _ {p, m} $ хэш-функций универсален.

---

Доказательство:

Рассмотрим два отчетных ключей $ K $ и $ l $ от $ z_p $ , чтобы $ k \ neq l $ . Для данной хеш-функции $ h_ {a, b} $ Мы позволяем

$$ r= (ak + b) \ mod p $$ ,

$$ s= (al + b) \ mod p $$ .

Мы впервые отметим, что $ r \ neq s $ . Почему? Соблюдайте, что

$$ r - s= a (k - l) (\ mod p) $$ .

следует, что $ \ neq s $ потому, что $ p $ Prime, а оба $ a $ и $ (k - l) $ - ненулевая модуль $ p $ , и поэтому их продукт также должен быть ненулевым модулем $ p $

Следовательно, во время вычисления любого $ h_ {a, b} $ в $ \ mathscr {h} _ _ _ {p, m} $ , отчетливые входы $ k $ и $ l $ Отличные значения $ R $ и $ S $ Modulo $ P $ ; В «уровню мод P» пока нет столкновений. Более того, каждый из возможных $ p (p - 1) $ выбор для пары $ ( a, b) $ с $ а \ neq 0 $ дает другую полученную пару $ (R, S, S ) $ с $ r \ neq s $ , поскольку мы можем решить для $ a $ и $ b $ Учитывая $ R $ и $ S $ $ ^ \ кинжал $ :

$$ a= ((r - s) ((k - l) ^ {- 1} \ mod p)) \ mod p $$ , < / P >.

$$ b= (r - ak) \ mod p $$ ,

Где $ ((k - l) ^ {- 1} \ mod p) $ обозначает уникальный мультипликативный обратный, модуль p,
class=" Математический контейнер "> $ k - l $ . Поскольку есть только $ P (P - 1) $ Возможные пары $ (r, s) $ с $ Г \ NEQ S $ , существует однозначное соответствие между парами $ (A, B) $ < / Span> с $ a \ neq 0 $ и пары $ (r, s) $ с $ r \ neq s $ . Таким образом, для любой данной пары входов $ k $ и $ l $ , если мы выберем $ (a, b) $ равномерно у случайных из $ z_p ^ * \ rest z_p $ , полученная пара $ (R, S) $ одинаково может быть любая пара отчетных значений модуло p.

Затем следует, что вероятность того, что различные клавиши $ K $ A

ND $ l $ collide равен вероятности, что $ r \ equiv s (\ mod m) $ Когда $ r $ и $ s $ случайным образом выбираются в качестве различных значений модуль $ p $ . Для заданного значения $ r $ , $ p - 1 $ Возможные оставшиеся значения для $ s $ , количество значений $ S $ такое, что $ s \ neq r $ и $ s \ equiv r (\ mod m) $ не более $ ^ {\ \ Dagger \ dagger} $

$$ \ lceil p / m \ RCEIL - 1 <(((p + m - 1) / m) - 1 $$ $$= (P-1) / m $$ .

Вероятность того, что $ s $ сталкиваются с $ R $ при уменьшении модуля $ m $ не более $ ((p - l) / m) / (p - 1)= 1 / m $ ,

Следовательно, для любой пары отчетных значений $ k, l \ in z_p $ ,

$$ pr \ {h_ {a, b} (k)= h_ {a, b} (l) \} \ leq 1 / m $$

Так что $ \ mathscr {h} _ {p, m} $ действительно универсален.

---

сомнения:

Я не мог понять следующие утверждения в доказательстве:

$ \ Dagger $ : Каждый из возможных $ p (p - 1) $ Выбор для пары $ (a, b) $ с $ А \ neq 0 $ дает другой Результирующая пара $ (r, s) $ с $ r \ neq s $ , поскольку мы можем решить для $ a $ и $ b $ Учитывая $ R $ < / span> и $ s $

Почему, «мы можем решить для $ a $ и $ B $ Учитывая $ r $ и $ S $ " $ \ Предполагается $ «Каждый из возможных $ P (P - 1) $ Выбор для пары $ (A, B) $ С $ А \ Neq 0 $ дает разную полученную пару $ (R, S) $ с $ † \ neq s $ "

---

$ \ dagger \ janger $ : для заданного значения $ r $ , из $ p - 1 $ Возможные оставшиеся значения для $ S $ , количество значений $ S $ такой, что $ S \ Neq r $ и $ s \ equiv r (\ mod m) $ не более $ \ lceil p / m \ RCEIL - 1 $ .

Как мы получаем термин $ \ lceil p / m \ RCEIL - 1 $ ?

Answer 1

Мы хотим показать, что если $ K_1 \ Neq k_2 \ in \ mathbb {z} _p $ Тогда

$ \ pr \ limits _ {(a, b) _ \ mathbb {z} _p ^ * \ turs \ mathbb {z} _p} [ak_1 + b \ equiv ak_2 + b \ pmod m] \ le \ frac {1} {m} $ .

Если оба добавления, так и умножения представляются в $ \ mathbb {z} _p $ .

Начнем с указания того, что если $ \ sim u (z_p ^ *) $ и $ b \ sim u u (Z_p) $ Тогда для всех $ k_1 \ neq k_2 \ in \ mathbb {z} _p $ , $ (ak_1 + b, ak_2 + b) $ равномерно распределен по адресу $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \} $ (т.е. $ h (k_1) $ и $ h (k_2) $ совместно однородные пары с разными записями, где случайность по сравнению с выбором $ h $ ). Это непосредственно от того факта, что для всех $ (C_1, C_2) \ in \ mathbb {z} _p ^ 2 $ с $ c_1 \ neq c_2 $ , следующая система линейных уравнений:

$ \ begin {align *} & ak_1 + b= c_1 \\ & ak_2 + b= c_2 \ end {align *} $

имеет уникальное решение по переменным $ (a, b) \ in z_p ^ * \ turs \ mathbb {z} _p $ . Вычитание второго уравнения от первого выхода $ a (k_1-k_2)= c_1-c_2 $ , поскольку $ K_1-K_2 $ ненулевой, мы можем умножить обе стороны по своему обратному и получить $ a= (k_1-k_2) ^ {- 1} (c_1-c_2) $ Отказ Если $ C_1 \ neq c_2 $ , то это ненулевое решение для $ a $ , и мы можем Экстракт $ b $ из любого из двух уравнений. Таким образом, для каждой пары $ (C_1, C_2) $ с $ C_1 \ NEQ C_2 $ Есть уникальные $ (a, b) \ in z_p ^ * \ turs \ mathbb {z} _p $ такой, что $ \ big ( h_ {a, b} (k_1), h_ {a, b} (k_2) \ big)= (c_1, c_2) $ . Это устанавливает ваш первый вопрос.

Теперь разделите $ \ mathbb {z} _p $ в $ \ lceil p / m \ rceil $ Ведра, $ b_1, ..., b_ {l=lceil p / m \ rceil} $ следующим образом: $ b_1={0,1, ..., m-1 \}, b_2={m, m + 1, ..., 2m-1 \} $ , ..., < Spaness Class="Математический контейнер"> $ b_l={m \ lfloor p / m \ Rfloor, m \ lceil p / m \ rceil + 1, ..., p-1 \} $ . Обратите внимание, что каждое ведро, за исключением последнего размера $ m $ , и никакие два элемента в том же веке - эквивалентные модуль $ m $ . Мы пришли к выводу, что количество разных пар в $ \ {(x, y) \ in \ mathbb {z} _p ^ 2 | x \ neq y \} $ , которые являются эквивалентными модульми $ m $ не более $ p (\ lceil P / M \ RCEIL-1) $ , поскольку после выбора первого элемента вы остались с $ \ NCEIL P / M \ RCEIL-1 $ Элементы на выбор (вы должны выбрать другое ведро, а каждое ведро обеспечивает не более одного кандидата). Напомним, что $ \ big (h_ {a, b} (k_1), h_ {a, b} (k_2) \ big) \ sim u (\ {(x, y) \ В \ mathbb {z} _p ^ 2 | x \ neq \}) $ , поэтому мы, наконец, можем завершить вывод:

$ \ pr \ limits _ {(a, b) _ \ mathbb {z} _p ^ * \ turs \ mathbb {z} _p} \ левый [h_ {a, b} (k_1)= h_ {a, b} (k_2) \ pmod m \ vane]=frac {p (\ lceil p / m \ RCEIL-1)} {p (p-1)} \ le \ frac {1} {m} $

Обратите внимание, что позволяет $ a $ , чтобы взять значение $ 0 $ только облегчает наш анализ, поскольку Теперь $ \ Big (h (k_1), h (k_2) \ big) $ совместно равномерно по адресу $ \ mathbb { Z} _p ^ 2 $ , но есть дополнительная вероятность $ \ frac {1} {p} $ что $ a= 0 $ и наши хэши будут эквивалентными модульми $ m $ , поэтому в этом случае нам придется соглашаться на $ O (\ frac {1} {m}) $ связан на вероятность столкновения.