Рандомизированный протокол связи. Часть 2
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”
Написать комментарий
RCE.SU рекомендует!
Поделиться
Свежие записи
- Видеокурсы по JAVA
- Наша компания займется созданием самого лучшего проекта – лендинг пейдж
- Как создать галерею Pixabay в Joomla
- Мы предлагаем создание сайтов с уникальной структурой и функционалом, разработанных под конкретные задачи клиента!
- Сайты для покупки-продажи недвижимости
- Enext.ua – копания по производству электротехнического оборудования
- Преимущества продвижения сайта в поисковых системах
- Анализ ключевых слов на новом уровне
- JOOMLA? Это как раз то, что вам было нужно!
[…] Продолжение в «Рандомизированный протокол связи. Часть 2″. […]