316
ЛЕММА A.16 Зафиксируем положительное целов N и допустим, что q
≤√2N элементов y1, . . . , yq выбираются случайно равномерно и независимо, из
множества, размера N . Тогда вероятность того, что существуют различ-
ные i, j при yi = yj составляет не менее
ДОКАЗАТЕЛЬСТВО Напомним, что коллизия означает, что существуют
различные i, j при yi = yj . Пусть Coll обозначает это событие.
Пусть NoColli
будет событием, которое не является коллизией между y1, . . . , yi; то есть, yj
ƒ=
yk для всех j < k ≤ i. Тогда NoCollq = tChoell является событием, когда
никакой коллизии вообще нет.
Если NoCollq происходит, то NoColli также должно происходить для всех i
≤ q.
Таким образом,
Pr[NoCollq]=Pr[NoColl1]•Pr[NoColl2|NoColl1]• • •Pr[NoCollq| NoCollq−1].
Теперь, Pr[NoColl1] = 1, поскольку y1 не может иметь коллизии с собой. Кро-
ме того, если событие NoColli происходит, то {y1, . . . , yi} содержит i различные
значения; таким образом, вероятность того, что yi+1 имеет коллизию с одним из
этих значений равна i и, следовательно, вероятность того, что yi+1 не имеет кол-
лизии с каким-либо из этих значений, равна1 −i/N. Это означает i Pr[NoColli+1 |
NoColli] = 1 − N , и,
таким образом,
Поскольку i/N < 1 для всех i мы имеем 1 − i/N ≤ e−i/N (согласно неравенству
A.3) и, таким образом,
Мы
приходим к выводу, что
используя неравенство A.4 на последнем шаге (обратите внимание, что q(q −
1)/2N < 1).
317
*Конечные поля
Мы используем конечные поля в книге только эпизодически, но включили их
определение и некоторые основные факты для полноты картины. Более под-
робную информацию можно найти в любом учебнике по абстрактной алгебре.
Достарыңызбен бөлісу: