Дискретная математика. Ерош И.Л - 135 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

135
ключом Алисы. Если Боб решает послать секретное сообщение m Али
се, он придумывает некоторое целое число k, вычисляет a º g
k
mod P и
передает Алисе пару чисел b º m·y
k
mod P и a º g
k
mod P. Алиса возво
дит а в известную только ей степень x и решает сравнение
mod mod .
xk
xkx
bmg
Pm P
ag
11
(6.3)
В результате Алиса читает переданное ей сообщение m.
Пример. Пусть P = 113. Возьмем g = 3. Это число является первооб
разным корнем по модулю 113. Пусть Алиса выбрала x = 59. Вычис
лим y º 3
59
mod 113 º 86 mod 113.
Открытыми ключами являются P = 113, g = 3 и y = 86. Секрет
ным ключом Алисы является число x = 59. Боб хочет послать сек
ретное сообщение Алисе в виде числа m = 92. Боб придумывает чис
ло k = 37, вычисляет a º 3
37
mod 113 º 24 mod 113 и b º 92· 86
37
º
7 mod 113 и посылает Алисе два числа a = 24 и b = 7. Алиса вычисляет
59
7
24
mod 113 º
7
75
mod 113 º 92 mod 113. Полученное сообщение
полностью соответствует отправленному.
6.2.2. Линейные коды для коррекции ошибок
при передаче сообщений
Одним из классов кодов, обнаруживающих или исправляющих
ошибки при передаче сообщений в каналах связи, являются линей
ные коды. В качестве входного алфавита используются полиномы
конечного поля Галуа GF(q), где q = p
h
, p – простое число, h – целое.
Если V
n
– векторное пространство размерности n над полем GF(q),
то подпространства размерности k пространства V
n
называются pич
ными линейными кодами длины n с k информационными символа
ми или (n, k)кодами. При p = 2 эти коды называются групповыми
кодами.
Пример 1. Пусть число разных передаваемых символов равно 2
n–1
,
например, при передаче двоичных кодов десятичных цифр можно
взять n = 5. Образуем двоичные последовательности вида (x
1
, x
2
, x
3
, …,
x
n–1
) и сопоставим каждую последовательность одному из передавае
мых символов. Сформируем еще один символ x
n
по следующему пра
вилу: x
n
= x
1
Å x
2
Å x
3
Å…Å x
n–1
, где операция «Å» означает сложение
по модулю 2. Если при передаче сообщений произошла ошибка в каком
либо одном разряде, то сумма x
n
Å x
1
Å x
2
Å x
3
Å…Å x
n–1
станет четной,
если была изначально нечетной, или наоборот. Такая проверка позволя
ет обнаружить одиночную ошибку (все ошибки нечетной кратности).

Страницы