Сен
26

Рандомизированный протокол связи. Часть 2

Автор Flashback    Рубрики Статьи и обзоры     Теги

R = (CI, СII) (Рандомизированный коммуникационный протокол проверки равенства данных)

Входная ситуация:

СI содержит последовательность х из n битов х — х1 … хn,

СII содержит последовательность у из n битов у — y1 … yn,- Цель: Определить, действительно ли х = у.

Этап 1. Компьютер CI случайно выбирает некоторое простое число р из интервала [2, n2].

{Заметим, что в этом интервале имеется примерно Prim (n2) ~ n2/ln n2 простых чисел. Следовательно,для такого выбора необходимо примерно [log2n2| <= 2 * [log2 n] случайных битов.}

Этап 2. CI вычисляет значение

s = Number(x) mod р

и посылает двоичное представление s и р на компьютер СII.

{Поскольку двоичные представления чисел s и p состоят не более чем из [log2 n2]

битов (s < р < n2), длина такого сообщения не превосходит 4 – [log2n]. }

Этап 3. После прочтения s и p компьютер СII вычисляет значение

q = Number(y) mod р.

Если q <>s, то СII выводит «х <> у».

Если q = s, то СII выводит «х = у».

Проанализируем работу протокола R = (СI, CII). Во-первых, мы посмотрим на сложность – измеряемую числом битов, необходимых для такой коммуникации, – а затем проанализируем надёжность (вероятность ошибки) протокола R.

Единственная информация, передаваемая этим протоколом – двоичные представ­ления натуральных чисел s и p. Как мы уже заметили, s < p < n2, следовательно длина сообщения не превышает

2 *[log2 n2] <=4 * [log2n].

Например, для рассматриваемого нами значения n — 1016 двоичная длина сообщения не превышает 4 * 16 * [log2 10] = 256. Это – очень короткое сообщение, оно может быть передано без каких-либо проблем.

Далее покажем не только то, что для большинства входов (начальных ситуаций) эта рандомизированная стратегия действительно работает – но также и то, что для каждого входа вероятность получения правильного ответа весьма высока. Анализируя вероятность ошибки, мы будем различать две возможности – в зависимости от того, равны ли значения х и у.

Есть 1 комментарий. к “Рандомизированный протокол связи. Часть 2”

Написать комментарий

XHTML: Вы можете использовать эти теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>